免费房地产网站模板,装潢设计公司,鞍山最新通知,wordpress获取文章发表时间题目#xff1a;
你有一个破损的键盘。键盘上的所有键都可以正常工作#xff0c;但有时Home键或者End键会自 动按下。你并不知道键盘存在这一问题#xff0c;而是专心地打稿子#xff0c;甚至连显示器都没打开。当你 打开显示器之后#xff0c;展现在你面前的是一段悲剧的…题目
你有一个破损的键盘。键盘上的所有键都可以正常工作但有时Home键或者End键会自 动按下。你并不知道键盘存在这一问题而是专心地打稿子甚至连显示器都没打开。当你 打开显示器之后展现在你面前的是一段悲剧的文本。你的任务是在打开显示器之前计算出 这段悲剧文本。 输入包含多组数据。每组数据占一行包含不超过100000个字母、下划线、字符“[”或 者“]”。其中字符“[”表示Home键“]”表示End键。输入结束标志为文件结束符EOF。输 入文件不超过5MB。对于每组数据输出一行即屏幕上的悲剧文本。 样例输入 This_is_a_[Beiju]_text [[]][][]Happy_Birthday_to_Tsinghua_University 样例输出 BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University
分析与解答
这题怎么说呢刘汝佳一上来就把链表的核心抛出来了我足足看了两个小时才理解不过利用数组表示单链表也掌握了 0.为了方便起见常常在链表第一个元素之前放一个虚拟节点s[0] 1.光标cur最后一个字符编号last其实只是由于这题homeend的条件限制 如果用数组建立单链表只需要next[i]和s[i] 2.其中next[i]是s[i]连的下一个字符的编号比如 s[0],next[0]3连下一个字符- s[next[0]],next[next[0]] 3.在本题中如果next[i]0说明不知道这个节点连哪个下一个节点如果全部插入完节点遇到next[i]0就意味着这个链表已经结束 所以有如下对链表遍历的方法
for(int inext[0];i!0;inext[i])printf(%c,s[i]);
4.下面说说怎么插入 s[i]对应一个next[i],那么s[i]下一个连的是s[next[i]],next[next[i]] 如果在s[i]后面插入s[j]next[j] 只需next[j]next[i],next[i]j 新节点j先插到后面next[i]的前面再把前面i的后面连的那个节点改为新插入的那个j 5.再来说说本题 a.只需改变s的输出顺序输出s[next[i]] b.多了个[],就是说插入的位置会发生变化怎么办 光标派上用场 先看一般情况s[0]0a1b2c3注意光标的意思假设光标一开始是0你输入a那1就是此时光标的位置假设s[1]a,那我们还没遍历到b的时候next[1]0看不懂得话看上面的黑色重点字体,next[0]1这是在s[0]后面插入s[1](看不懂的话看重新看上面的4)此时如果光标等于最后一个字符的编号比如lastcur初始值是0那么你加了一个字符最后一个字符编号自然需要更新就更新最后一个字符编号然后把光标改成1 再看特殊的 如果碰见[光标跑到0了,把cur改成0 碰见]光标跑到最后一个了数的后面了你们发现了吗最后一个数的下标正好是光标的下标所以curlast 6.悟道是acmer的必经之路多看几个小时就明白了 #include cstdio
#include cstring
const int maxn1000005;
int last,cur,next[maxn];
char s[maxn];int main(){while(scanf(%s,s1)){int nstrlen(s1);lastcur0; next[0]0; for(int i1;in;i){char chs[i];if(ch[) cur0; else if(ch]) curlast; else{ next[i]next[cur]; next[cur]i; if(curlast) lasti; curi; }}for(int inext[0];i!0;inext[i])printf(%c,s[i]);printf(\n);}return 0;
}
