Input

ACCBA
5
1 B
0 A
2 B
4 C
0 A
Output

ABCCBA
AABCCBA

AABBCCBA

A

0 ≤ n ≤ 10^4

0 ≤ 初始珠子数量 ≤ 10^4

`````` #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define pNode Node*
#define pList List*

const int SZ = 1<<20;
struct fastio{   //fast io
char inbuf[SZ];
char outbuf[SZ];
fastio(){
setvbuf(stdin,inbuf,_IOFBF,SZ);
setvbuf(stdout,outbuf,_IOFBF,SZ);
}
}io;

struct Node {
char color;
pNode pred;
pNode succ;

Node() {
}

Node(char c,pNode pred=NULL,pNode succ=NULL):color(c),pred(pred),succ(succ) {

}

void insertAsSucc(char c);

void insertAsPred(char c);
};
void Node::insertAsSucc(char c) {
pNode x = new Node(c,this,this->succ);
this->succ = x;
}

void Node::insertAsPred(char c) {
pNode x = new Node(c,this->pred,this);
this->pred = x;
}
class List {
private:
int size;
pNode trai;

public:
List() {
trai = new Node();
trai->color = '^';
size = 0;
}

pNode insert(int n,char c);
void traverseShow();
void insertBfTrai(char c);
void check(pNode start);
pNode checkB(pNode p);
pNode checkA(pNode p,bool &change);
pNode remove(pNode p);
};
pNode List::remove(pNode p) {  //规定删除后返回前一节点
if(p == this->trai) return p->pred;
pNode q = p->pred;
p->pred->succ = p->succ;
p->succ->pred = p->pred;
delete p;
size--;
return q;
}
void List::check(pNode start) {
bool change = true;  //以下循环的flag
while(change) {
start = checkB(start);
start = checkA(start,change);
}
}
pNode List::checkB(pNode p) {  //从p开始往前（before） 检查
pNode q = p->pred;
int count = 1;
q=q->pred;
count ++;

if(count == 3) {
for(int i=0;i<3;i++) {
p = this->remove(p);
}
count=1;
q=p->pred;
}
}
return q->succ;  //q和p内容不同，q->succ和p内容相同
}
pNode List::checkA(pNode p,bool &change) { //从p开始往后(After)检查
change = false;
if(p==this->trai) return p->pred;
pNode q = p->succ;
int count = 1;
while(q!=this->trai && q->color==p->color) {
count++;
q = q->succ;

if(count == 3) {  //可以消掉
change = true;   //外层循环 可以继续
for(int i=0;i<3;i++) {
p = this->remove(p);
p = p->succ;
}
count = 1;
if(p==this->trai) return p->pred;
q = p->succ;
}
}
return q->pred;
}
void List::insertBfTrai(char c) {  //在尾节点前插入一个节点
pNode p = new Node(c,trai->pred,trai);
trai->pred->succ = p;
trai->pred = p;

size++;
}
pNode List::insert(int n,char c) {  //从第n个位置插入
if(n>this->size) n=this->size;
while(n-- > 0) {
if(p != this->trai)
p=p->succ;
}
p->insertAsSucc(c);
size++;

return p->succ;
}
void List::traverseShow() { //输出整个链表 内容

if(this->size == 0) printf("-");
while((p=p->succ)!=trai) {
printf("%c",p->color);
}
printf("\n");
}

//相关全局量定义
char s[20000];   //<10^4即可
int posi[20000];
char colors[20000];

int main(){
#ifndef _OJ_
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

//data input
gets(s);
int len=strlen(s);
int n;   //insert的操作次数
scanf("%d",&n);
//printf("%d ",len);

pList balls = new List();
for(int i=0;i<len;i++) {
if('A'<=s[i] && s[i]<='Z')
balls->insertBfTrai(s[i]);   //初始状态构建
}

for(int i=0;i<n;i++) {
scanf("%d %c",posi+i,colors+i);  //n行插入操作输入
}
//执行n次操作
for(int i=0;i<n;i++) {
if('A'<=colors[i] && colors[i]<='Z') {
pNode p = balls->insert(posi[i],colors[i]); //取得新插入节点
balls->check(p);   //每插入一个数据，就从插入点开始检查能否消掉
balls->traverseShow();  //输出
}
}

delete balls;
return 0;
}
``````

2个回答

3 年多之前 回复

hihoCoder上的一道关于KMP算法的一道题，题目描述如下： #1015 : KMP算法 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。 这一天，他们遇到了一只河蟹，于是河蟹就向小Hi和小Ho提出了那个经典的问题：“小Hi和小Ho，你们能不能够判断一段文字（原串）里面是不是存在那么一些……特殊……的文字（模式串）？” 小Hi和小Ho仔细思考了一下，觉得只能想到很简单的做法，但是又觉得既然河蟹先生这么说了，就肯定不会这么容易的让他们回答了，于是他们只能说道：“抱歉，河蟹先生，我们只能想到时间复杂度为（文本长度 * 特殊文字总长度）的方法，即对于每个模式串分开判断，然后依次枚举起始位置并检查是否能够匹配，但是这不是您想要的方法是吧？” 河蟹点了点头，说道：”看来你们的水平还有待提高，这样吧，如果我说只有一个特殊文字，你能不能做到呢？“ 小Ho这时候还有点晕晕乎乎的，但是小Hi很快开口道：”我知道！这就是一个很经典的模式匹配问题！可以使用KMP算法进行求解！“ 河蟹满意的点了点头，对小Hi说道：”既然你知道就好办了，你去把小Ho教会，下周我有重要的任务交给你们！“ ”保证完成任务！”小Hi点头道。 提示一：KMP的思路 提示二：NEXT数组的使用 提示三：如何求解NEXT数组 输入 第一行一个整数N，表示测试数据组数。 接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。 其中N<=20 输出 对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。 样例输入 5 HA HAHAHA WQN WQN ADA ADADADA BABABB BABABABABABABABABB DAD ADDAADAADDAAADAAD 样例输出 3 1 3 1 0 这是我按照自己的理解提交的代码： #include<stdio.h> #include<string.h> #include<stdlib.h> int KMP(char *ori,char *pat); int main(void) { char *ori,strori[10001]; char *pat,strpat[1000001]; int n;//测试组数 pat=strpat;//必须初始化 有所指向才行 ori=strori; scanf("%d\n",&n); while(n--) { scanf("%s",pat); scanf("%s",ori); printf("%d\n",KMP(ori,pat)); } return 0; } int KMP(char *ori,char *pat) { char *temp,*p; int num=strlen(pat); int i=0,j=0; int *next; int sum=0; //求出next数组 next=(int *)malloc(num*sizeof(int)); memset((int *)next,0,num*sizeof(int)); p=temp=pat; pat++; while(*pat) { if(*pat==*temp) { *(next+i+1)=j+1; pat++; temp++; j++; } else { pat++; j=0; } i++; } //匹配字符串 pat=temp=p; i=j=0; while(*ori) { if(*ori!=*pat) { ori++; if(i!=0)//表明之前有匹配成功过，但还未完全匹配 { ori=ori-1-*(next+i-1);//ori=ori-i-1+(i-*(next+i-1)); pat=p; i=0; } } else { ori++; pat++; i++; if(*pat=='\0') { sum++; ori=ori-1-*(next+i-1); pat=p; i=0; } } } return sum; } 但每次提交结果都是： Time Limit Exceeded TLE 用户程序运行时间超过题目的限制 怎么优化一下我的代码才能是它AC啊？！求大神指导啊。

oj上的题，为什么过不了？ ``` #include<stdio.h> struct Employee{ char name[10]; float Basic,Variable,Expenditure,Payroll; }; void Sort(struct Employee *p,int n) { struct Employee a; int i,j; for(i=0;i<n;i++) for(j=i;j<n;j++) { if(p[i].Payroll>p[j].Payroll||(p[i].Payroll==p[j].Payroll&&p[i].Basic>p[j].Basic)||(p[i].Payroll==p[j].Payroll&&p[i].Basic==p[j].Basic&&p[i].Variable>p[j].Variable)) { a=p[i]; p[i]=p[j]; p[j]=a; } } } int main() { struct Employee emp[100]; int i,n,Cas=0; while(scanf("%d",&n)!=EOF) { Cas++; for(i=0;i<n;i++) { scanf("%s%f%f%f",emp[i].name,&emp[i].Basic,&emp[i].Variable,&emp[i].Expenditure); emp[i].Payroll=emp[i].Basic+emp[i].Variable-emp[i].Expenditure; } Sort(emp,n); printf("Case #%d:\n",Cas); for(i=0;i<n;i++) printf("%10s%10.2f\n",emp[i].name,emp[i].Payroll); } return 0; } ``` 题目：给定N个职员的信息，包括姓名、基本工资、浮动工资和支出，要求编写程序按照排序规则顺序输出每位职员的姓名和实发工资（实发工资=基本工资+浮动工资-支出）。 排序规则：按照实发工资从小到大排序，如果实发工资相同的则按照基本工资从小到大排序，如果实发工资和基本工资都相同，则按照浮动工资从小到大排序。 注意：main函数已经给定（如下所示）。 请将程序补充完整。 提交时只需要提交自己补充的代码部分，不需要提交给定的main函数的代码部分。

``` #include<stdio.h> #include<string.h> int main() { int len2,len1,i,max,n; while(scanf("%d",&n)!=EOF) { char s1[2000]={0},s2[1000]={0}; gets(s1); gets(s2); len1=strlen(s1); max=0; for(i=1;i<len1;i++)//寻找一串字符中最大的字符 { if(s1[i]>s1[max]) max=i; } len2=strlen(s2); for(i=len1-1;i>=max+1;i--)//将s1字符串中最大字符后面的字符移动len2个位置 { s1[i+len2]=s1[i]; } for(i=max+1;i<=max+len2;i++)//将s2中的字符插入到s1当中 { s1[i]=s2[i-max-1]; } puts(s1); } return 0; } ``` 问题：给定两个字符串s和t，在s字符串中的最大字符后边插入字符串t。 输入：测试数据有多组，每组包含两个字符串s和t，分别占两行，均不超过100个字符。 输出：对于每组测试数据，输出插入后的新字符串，单独占一行。若有多个最大字符，则插在第一个之后。 我试了很多组数据都对了（用的dev c++），但是在学校的oj上还是wa

#include<stdio.h> int main() { int n,j=0,i,s[100]; scanf("%d",&n); while (n!=0) { int a[100]; static int k=0; s[k]=0; for (i=0;i<n;i++) scanf("%d",&a[i]); for (i=n-1;i>0;i--) { if (a[i]+a[i-1]>0||a[i]+a[i-1]==0) s[k]=s[k]+a[i]; } if (a[0]>0) s[k]=s[k]+a[0]; k=k+1; scanf("%d",&n);j=j+1; } for (i=0;i<j;i++) {if (i<j-1)printf("%d\n",s[i]); else printf("%d",s[i]); } return 0; }

C++OJ题目 文件名排序（结构体）

#include <bits/stdc++.h>///安全密码 using namespace std; int main() { char s[55]; while(scanf("%s",&s)!=EOF){ int len =strlen(s); if(len<8){ printf("NO\n"); continue; } bool low= false,up=false,sng=false,num=false; for(int i=0;i<=len;i++){ if(isdigit(s[i]))num=true; else if(islower(s[i]))low=true; else if(isupper(s[i]))up=true; else sng=true; } int cnt=0; if(low)cnt++; if(up)cnt++; if(num)cnt++; if(sng)cnt++; if(cnt>=3)printf("YES\n"); else printf("NO\n"); } return 0; } #include <bits/stdc++.h>///回文串 using namespace std; char s[103]; bool judge(){ int len=strlen(s); for(int i=0;i<len/2;i++){ if(s[i]!=s[len-i-1])return false; } return true; } int main() { int T=1; while(scanf("%s",&s)!=EOF){ if(judge())printf("case%d:yes\n",T++); else printf("case%d:no\n",T++); } }
c++oj问题，程序tle了，不知道是哪里耗时比较多【霍夫曼编码】。
oj 问题描述：https://paste.ubuntu.com/p/3sXYcYfJP3/ 我的代码：https://paste.ubuntu.com/p/bthbV8BBxd/

OJ题目运行错误，本地运行没问题
### 小白求救，运行错误，但找不出问题在哪 在本地成功运行，也测试了好多组数据。但是本人可能欠缺经验，编写程序习惯不好，可能一些细节没注意，导致提交到OJ上去，显示运行错误。我自己又找不到问题。。。跪求大佬帮忙看看 ####题目描述 在n个整数中查找指定数字。 ####输入 输入数据有多组，每组数据包括两行，第一行包含一个整数n(0<n<=100)和n个整数。第二行包含一个整数m表示要查找的关键字。 ####输出 如果在n个整数中有和m相等的输出该整数，如果没有输出null。 ####样例输入 ``` 5 1 2 3 4 5 3 3 10 20 30 100 ``` 样例输出 ``` 3 null ``` 小白的代码： ``` import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] array = new int[100]; while (true) { int cin = sc.nextInt(); for (int i = 0; i < cin; i++) { int inp = sc.nextInt(); array[i] = inp; } int inpp = sc.nextInt(); for (int i = 0; i < cin; i++) { if (array[i] == inpp) { System.out.println(inpp); break; } else if (arr[i] != inpp && arr[i] == arr[cin - 1]) System.out.println("null"); } } } } ``` --- #2019-10-26 问题已解决 while循环的循环条件不能用true,要用hasNext
HDU OJ 1004问题： C语言中有没有可以储存字符串的数组？

http://acm.hdu.edu.cn/showproblem.php?pid=2022 杭电求解2022，带解析的那种，【害羞】
C++ OJ题数字统计 求解

[OJ题][TLE][C语言]关于整数数列的任意连续子数列快速遍历出现TLE的解决方案

Catch the cow(POJ3278) 编译器上没问题, OJ上一直runtime error?
[原题网址](http://poj.org/problem?id=3278 "Catch the cow") 下面是我已经在编译器上通过的代码,但是OJ上始终会RE (使用的是广度优先搜索的方法) ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100000 int n, k, ans; int que[MAX_N+10][2]; int vis[MAX_N+10]; int head, tail; void bfs( int x); void enqueue ( int x, int time); int main(void) { scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n); } printf("%d\n", ans); return 0; } void bfs( int x) { enqueue(x, 0); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; nowtime = que[head][1]; head ++; if( nowx == k) { ans = nowtime; break; } for( i=1; i<=3; i++) { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1); vis[nowx*2] = 1; } } } } void enqueue( int x, int time) { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 一开始查了之后说可能是什么栈空间不够,就尝试了一下动态分配空间 (萌新还没学指针,就在网上照猫画虎贴了进去), 但是数字只要大一点程序就无法输出结果 更改后的代码如下: ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100001 int n, k, ans; //int que[MAX_N+10][2]; /*之前的方案,但同样RE了,可能是空间不足(?),所以尝试如下动态分配的方法*/ //int vis[MAX_N+10]; int head, tail; void bfs( int x, int **que, int *vis); void enqueue ( int x, int time, int **que); int main(void) { int **que; int i, j; int *vis; que = (int**)malloc(sizeof(int*)*MAX_N); //为两个数组分配空间 for( i=0; i<MAX_N; i++) { que[i] = (int*)malloc(sizeof(int)*2); } vis = (int*)malloc(sizeof(int)*MAX_N); scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n, que, vis); //进入深搜 } printf("%d\n", ans); return 0; } void bfs( int x, int **que, int *vis) { enqueue(x, 0, que); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; //队列数据的取出 nowtime = que[head][1]; head ++; if( nowx == k) //结束条件 { ans = nowtime; break; } for( i=1; i<=3; i++) //对三种可能进行遍历 { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1, que); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1, que); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1, que); vis[nowx*2] = 1; } } } } void enqueue( int x, int time, int **que) //队列数据的写入 { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 请教一下大佬们上面RE的原因到底是什么, 还有下面的动态分配有什么问题,感激不尽

Java学习的正确打开方式

linux系列之常用运维命令整理笔录

Python十大装B语法
Python 是一种代表简单思想的语言，其语法相对简单，很容易上手。不过，如果就此小视 Python 语法的精妙和深邃，那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点，并附上详细的实例代码。如能在实战中融会贯通、灵活使用，必将使代码更为精炼、高效，同时也会极大提升代码B格，使之看上去更老练，读起来更优雅。

2019年11月中国大陆编程语言排行榜
2019年11月2日，我统计了某招聘网站，获得有效程序员招聘数据9万条。针对招聘信息，提取编程语言关键字，并统计如下： 编程语言比例 rank pl_ percentage 1 java 33.62% 2 cpp 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7 p...

JDK12 Collectors.teeing 你真的需要了解一下

SQL-小白最佳入门sql查询一

【图解经典算法题】如何用一行代码解决约瑟夫环问题

“狗屁不通文章生成器”登顶GitHub热榜，分分钟写出万字形式主义大作

GitHub标星近1万：只需5秒音源，这个网络就能实时“克隆”你的声音

《程序人生》系列-这个程序员只用了20行代码就拿了冠军

11月8日，由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办，科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。 　　区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力，电力解决了人类基本的生活需求，互联网彻底改变了信息传递的方式，区块链作为构造信任的技术有重要的价值。 　　1...

【技巧总结】位运算装逼指南

【管理系统课程设计】美少女手把手教你后台管理
【文章后台管理系统】URL设计与建模分析+项目源码+运行界面 栏目管理、文章列表、用户管理、角色管理、权限管理模块（文章最后附有源码） 1. 这是一个什么系统? 1.1 学习后台管理系统的原因 随着时代的变迁，现如今各大云服务平台横空出世，市面上有许多如学生信息系统、图书阅读系统、停车场管理系统等的管理系统，而本人家里就有人在用烟草销售系统，直接在网上完成挑选、购买与提交收货点，方便又快捷。 试想，若没有烟草销售系统，本人家人想要购买烟草，还要独自前往药...
4G EPS 第四代移动通信系统