ACM周年回忆录

发表于 Disqus：

开始练ACM已经一年了，经历了很多，成长了很多。是时候将这一年做个总结了。

  • 从高考失利开始（喜闻乐见）

记得当时出成绩的时候，整个人都呆住了，第一感觉是分数查错了。过了好久才接受这个现实。语文95，数学101，理综268，一次考试三科没考好，也算是个奇迹了。后 来查成绩发现语文选择错了好多，作文分极低；数学最后一题没得分，其他大题也都有小错；理综物理大题步骤不全，化学选做涂错题号了。
后来填志愿什么的几乎都交给我父母了，我也没有心情去管了。
初中开始考试有了学校的排名，当时因为学校不是热门初中，随便学学就可以考到年级第一，最差也没出过年级前五名。高中直升青岛二中，青岛市最强高中，没有之一。
二中是个好学校，有着健全的学生组织，丰富的课余活动，学习生活非常充实。可以肯定地说，二中的学生会的能力、课余活动的质量一点不输国内的很多985、211高校（ 好多上了985、211的同学都这么说，我这个成绩显然是去不了了）。
我呢，由于个人问题，太贪玩，高一高二荒废了好多时间，高三才开始补知识。高考前夕，三次模拟考试，都在进步，最后正常发挥可以考到年级100名之前。
最后高考的要是排名的话，感觉怎么说也好年级四五百名了。从小到大我一直感觉自己也算是比较聪明的，这次考不好也不知道为什么，第一次碰上这种事总感觉有点不爽。
不爽了，就想干点什么事，就想等着考研了。

  • 加入ACM协会

开学之后，向一个二中学姐咨询考研的事，问平时参加什么活动有什么用，学姐的大概意思是活动就不要参加了，没有高中的好，如果有什么竞赛就去，对考研和保研都有好处。
后来有次跟兼职辅导员wp谈到了我想考研的事，他跟我说，可以去参加ACM竞赛或者数学建模什么的，对将来有好处。当时我就准备等社团纳新的时候参加一个。
然而，社团纳新那天是周末，因为学校离家近，周末都是回家过，所以不在学校，委托一个同学帮我加了魔方社团，然而，ACM和数学建模的事就忘掉了。回来之后，我想虽然 纳新大会结束了，但说不准还可以加，就要来了两个社团负责人的电话，发了短信，最后ACM协会的cdc学长先回了短信，让我联系gmc学长，gmc学长也很快回了信息 。就这样我就加入了ACM协会，没再管数学建模。

  • 学习C语言

都说大学很多东西需要自学，在二中早已锻炼出了很强的自学能力（毕竟高三补了一年知识，而且我从来都没上过补习班，总感觉那是在浪费时间）。军训的时候，每天白天军训 ，晚自习兼职辅导员讲完事情之后我就开始看发的书，2周军训的时间，C语言这本书有用的部分都看完了。
后来上课，老师讲了一些基本用法，讲了讲OJ系统的使用。感觉自己会了就没怎么仔细听（事实证明这种做法很危险）。后来上机，第一道题输出“Helloworld!” ，我感觉很简单，却在输出时把w写成了大写，处女交光荣WA。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
printf("Hello World!");
}

/**************************************************************
    Problem: 1398
    User: 201401061124
    Language: C
    Result: Wrong Answer
****************************************************************/

艰难的做完了第一次的作业，自己又看了看书，找了找自己的不足。第二次作业时已经感觉没什么难度了，随心所欲的AK。

  • 协会的十一比赛

十一的时候收到了gmc学长群发的飞信，说协会在学校OJ上挂了一套十一的练习题，1日晚上。抱着试试看的心态，我晚上也去做了。第一题那个输出一句话的很简单的题。 第二题是一个不能用‘＋’、‘＊’、‘／’，求平均数的题，卡了好久不会做。后来请教了高中时期班里的大神wyd，在大神的指导下，过掉了这道题。接着一直做到凌晨2 点多，做了两道题，都没做出来，一道WA了，一道PE了。
这里写图片描述
这是当天的最后一次提交，内心几乎是崩溃的。
2日上午，gmc学长告诉我PE很好改的，在学长鼓励之下，改完了PE的那道题，又很快的做出来了一道数学题，那道数学题很水，可是是英文题面，晚上都没看这道题。把 其他几道题都读了读，写了两道，都没考虑什么细节，提交全部WA了，又去改昨天晚上的题，改过了。之后又把剩下的题仔细写了写，最初挂上的8道题AK了。
这里写图片描述
这是最后一次的提交。
3日高中聚会，中午收到学长飞信，说又加了两道题，下午干了一个挺厉害的事情：去网吧敲代码了。记着加的第一题是个简单的计数统计题，结果后台数据错了，一下午我都在 网吧改这道题，直到去聚会。
聚会回家之后，开始做最后一题，从11点开始直到凌晨2点做完，中途改了好多次，各种分类讨论，最后过了，这都要感谢高中数学老师教的分类讨论思想。
这里写图片描述

最后Ac的代码留念：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
int main()
{
    int n,i,x,p,q,k,l;
    while(scanf("%d\n",&n)!=EOF)
    {
        double a[n];
        for(i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
        }
        if(n>2)
        {
            int b[n-1];
            for(i=0;i<n-1;i++)
            {
                if(a[i]<a[i+1])
                    b[i]=-1;
                else
                    b[i]=1;
            }
            x=0;
            int c[n-2];
            for(i=0;i<n-2;i++)
            {
                c[i]=b[i]*b[i+1];
                if(c[i]<0)
                    x++;
            }
            p=0;
            q=0;
            if(b[0]<0&&b[n-2]<0)
            {
                if(x==0)
                {
                    printf("yes\n");
                    printf("1 1\n");
                }
                if(x==2)
                {
                    for(i=0;i<n-2;i++)
                    {
                        if(c[i]<0&&p==0)
                            p=i+2;
                        if(c[i]<0&&p!=0)
                            q=i+2;
                    }
                    if(a[p-2]<a[q-1]&&a[q]>a[p-1])
                    {
                        printf("yes\n");
                        printf("%d %d\n",p,q);
                    }
                    else
                        printf("no\n");
                }
                if(x>2)
                    printf("no\n");
            }
            if(b[0]>0&&b[n-2]>0)
            {
                if(x==0)
                {
                    printf("yes\n");
                    printf("1 %d\n",n);
                }
                else
                    printf("no\n");
            }
            k=0;
            if(b[0]<0&&b[n-2]>0)
            {
                if(x==1)
                {
                    for(i=0;i<n-2;i++)
                    {
                        if(c[i]<0)
                            k=i+2;
                    }
                    if(a[k-2]<a[n-1])
                    {
                        printf("yes\n");
                        printf("%d %d\n",k,n);
                    }
                    else
                        printf("no\n");
                }
                else
                    printf("no\n");
            }
            l=0;
            if(b[0]>0&&b[n-2]<0)
            {
                if(x==1)
                {
                    for(i=0;i<n-2;i++)
                    {
                        if(c[i]<0)
                            l=i+2;
                    }
                    if(a[l]>a[0])
                    {
                        printf("yes\n");
                        printf("1 %d\n",l);
                    }
                    else
                        printf("no\n");
                }
                else
                    printf("no\n");
            }
        }
        if(n==1)
            printf("yes\n1 1\n");
        if(n==2)
        {
            if(a[0]<a[1])
                printf("yes\n1 1\n");
            else
                printf("yes\n1 2\n");
        }
    }
}

/**************************************************************
    Problem: 1592
    User: 201401061124
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:800 kb
****************************************************************/

后来听学长说，这是CF有次比赛Div2的B题，感觉自己当时也是挺厉害的。
十一这次也算是让我对ACM有了一些认识，也体会到了ACM的乐趣。

  • 刷题加入集训队

10月12日，ACM协会见面会，讲了加入ACM集训队的要求，在UVa上刷够AOAPC II上的100题。
一开始没弄懂要求，上UVa从100开始刷，101就不会了，用指针写了好久一直RE，等去机房才知道要刷紫书的。
到11月，已经刷完了前五章基础型的东西，STL的基础应用什么的也都会了。
12月初，在紫书和蓝书上凑够了100题，成了14级第一个加入集训队的。

  • 几场比赛

大一上半年，也是打了几场比赛的，虽然有些比赛成绩不是很好，就当是感受下ACM比赛的氛围了。
青理工邀请赛
http://blog.csdn.net/wcr1996/article/details/40952361
班级对抗赛
http://blog.csdn.net/wcr1996/article/details/42048625
海大朗讯杯
http://blog.csdn.net/wcr1996/article/details/42221623

  • 寒假

从加集训队到寒假的好长时间，都没刷题，刚一放寒假就马上进入了刷题的状态。
开始的时候主要是刷紫书第6、7章的题，那两章的好多题不需要什么思路，就是普通搜索题，但是代码在当时看来也算比较复杂的了，有的时候一天都出不了几道。刷题速度缓 慢，可以算是比较黑暗的时期了。
后来6、7章的题刷的差不多了，开始刷第8章，第8章是高效算法，对代码能力的要求没有6、7章那么高，更加偏向思路。刷起来感觉好了不少，有的时候灵光乍现，一天可 以出好几道。
寒假快结束的时候有刷了几到DP，紫书上的DP难度不小，反复读了好久只做出来了几道例题，习题只做出来2道。
总的来说寒假，还是更多的练习了代码能力和一些解题的思维方式，现在看来寒假时期刷第6、7章的功夫没有白下，代码能力确实提高了不少。

  • 组队

现在我的队友是lry和zdl，当初组队的事情也是挺好玩的。
快省赛了，要提前联系好人组队，然而我把这件事忘了，有一天马原课，起床晚了没去上，结果老师点名了。ljr发消息告诉我老师点名了，他替我答了到。过了一会，zcy 也发消息告诉我老师点名了，还顺便问了我有没有联系别人组队。当时我才想起来还有这么个事，过了一会，zdl也发消息问我组队的事。
我想zcy可能跟他女票组队，跟他们组容易当电灯泡，于是就想跟zdl组队了，一问正好他们还差一个，就这样就组好了现在的队伍。
现在看来，还好当时没上马原。

  • 省赛前夕

清明节在学校打选拔赛，连着打了好多场比赛，先是个人赛，接着是组队赛。
个人赛做的是USACO月赛题，组队赛做的是各个地方的省赛题。
感觉清明节这几场比赛，自己了解了不少东西，很多模板题都能出了，知识面大了不少。寒假结束时学的DP也练的熟练了许多。
选拔赛结束之后，我们队拿到了正式队的名额，然后大部分时间都在准备省赛，开始看书扩充知识面，刷模板题收集模板。我还特别的学了一些解题技巧，尺取法就是那时候学的 ，在后来的省赛中，就是靠着最后不到三十分钟出了一道尺取法的题目从铜牌变成了银牌，还好当时看了。

  • 省赛

直接贴当时的总结了：

省赛打完了，最后出了5题，银牌，正式队排名21。总的来说打的还是不错的，最后的排位也在意料之中。总的分工实现的也比较好，lry开数学，zdl和我做其他题 ，我主写代码，zdl帮我出数据、Debug打印的代码。
开场读题，我们三个人读A、B、C三道题，具体怎么分得不记得了。读完之后了解了大概题意，这时候刷榜，C题有队5分钟1Y，A题有两个队6分钟1Y，F题有队7分钟 1Y。
我看C是个博弈，准备先开，就去推必胜策略。lry想A题。zdl跟我说B是个模拟。热身赛模拟这种细节题坑了好久，所以我们就没开B题。准备放一放，zdl其它题。
C题只能取连续编号且编号不改变，一开始理解错了题意，以为取走之后两边的就连续了，和从石子堆里取石子一样。很快写出代码，n%3为0时后手赢，其他情况先手赢。提 交WA。zdl开始和我一起Debug。
过了一会，lry看出A题了，给我讲思路，打完之后提交，18分钟A题1Y。
然后lry继续读其他题，zdl和我继续推C题，zdl给我讲清了题目原本的意思，我意识到原本的思路就是错的。他推了3至6的结果，我继续推剩下的，发现第一个人取 走之后，第二个人可以把剩下的取成对称的，所以第二个人必胜。
重写代码提交，23分钟C题2Y。
看榜上很多人过了B。zdl给我讲了题意，跟我说set就能过，只是个小模拟。用set维护所有惟一出价，写完之后提交，49分钟B题1Y。
打B题时知道了J题纸质题目指数打错了位置，这种事情以前也经常遇到，lry读完题之后感觉很简单，只需要两数相等且能被11整除即可。我准备用大数做。lry告诉我 只需要从个位开始，每两位当作一个整数，相加求和，求得的数能被11整除，原数就能被11整除，类似于判断被3整除的方法。
打完之后提交，J题66分钟1Y。至此四题，进入金牌区。
当时山科有四个队进入金牌区，心情激动。感觉再出一两道也不是很难，说不准就打金牌了。但我们当时怎么也不会想到，在接下来的近三个半小时里，我们一道题已没有出，直 至最后换题，才出了一道D题。
继续跟榜H题。感觉是要唯一分解之后再做。lry准备用唯一分解推推。在这时我出现了较大的失误。
一开始我们的思路方向是对的。但我在对唯一分解的素数的范围弄错了，数字的范围是100w，就想成了需要100w以内的素数。打表统计之后，发现居然有7.8w个素数 ，然后我脑补复杂度O(10w*7.8w)，认为唯一分解会超时，马上制止了lry继续推H题。
当时也已经想到了分解之后对2取余数，只保留余数为1的素因子，统计取余数为1的素因子与当前数字相同的数字相同的数的个数，如果不是我强行停止了H，很有可能，H题 不久就出了。
这时看榜上有人出了L题，zdl读完题之后告诉我是个最短路的题，一开始准备在H题之后做，放弃H题之后，lry继续推F题，zdl和我一起做L。
H题，是我第一次写Dijkstra算法思路就想了很久。而且一开始读错题了，以为两点间有单向路权值为1，双向路权值为1读图处理上就用了挺长时间的，最后由map < i n t , i n t > g[maxn]存的，读图复杂度O(mlogm)，然后用Dijkstra算法做，复杂度O(mlogn)，应该不超时，但是写好之后提交WA。
开始漫长的Debug，出了好几组数据都能过，以为是出现0权边，不能直接带书上的模板，修改边界之后又提交了两次，依然WA。
Debug中途我跟lry说了F题也许可以二分查找答案，他说不一定是单调的，所以要证明或者分类讨论。
比赛四小时封榜，当时我们已经从金牌区中部滑落到银牌区中部。当时我感觉如果一直不过题，最后肯定会变成铜牌。
还剩50分钟左右，Debug代码依然没有突破。我感觉程序实现没有问题，可能是读错题了，重新读题。发现有朋友圈的，圈内的边权值都是0。程序几乎需要完全重写，而 且我们还不会处理这种情况。必须得换题，zdl和我开始重新读其他题。
还有40多分钟时，我看到D题数据是400，以为是1s时间限制，想到了求前缀和之后枚举起点终点，对每个矩形进行尺取的算法，脑补复杂度O(n^3)，记得之前数据 量300的O(n^3)算法能1s出题，感觉貌似能过，要是过不了也就差个常数的优化。
我开始写D题，中途卡住了一会，这时lryF题推出了公式，跟我说了，我放下D题，写F题。我打公式，他发现还有个特殊情况，去修改。打完公式看他还在推，我就继续想 D题。
还差30多分钟时，我想出了D题的完整思路，他也推好公式了。但是那个要写二分，之前我们出现过一次写二分求上界一个多小时不过的情况，所以我跟他说先不做那道题，等 我把D题A掉。
打完D题，样例不过。Debug，样例过了，提交WA。
就剩10多分钟了，继续Debug，出现了未知的错误，读取点的顺序不同结果居然不一样，貌似是编译器差异，导致变量生存期和平时的习惯不同，使用同名变量出现问题。 修改，依然不对，继续改把读入边界1n改为了0n-1，居然就没错了。
提交，D题293分钟2Y。5题了感觉时间不长应该是银牌，吃饭。 最终5题收场，银牌。
赛后听其他人的题解知道了，H题就是唯一分解，只是范围很小1~1000，分解之后对2取余，标记素因子乘积，就好了。F题用塞瓦定理，最后式子就是lry来的那个， 是单调的，二分查找就行，可惜最后时间不够没写二分。
下次比赛继续加油了。

  • 市赛

还是贴当时的总结：

这场比赛打得不错，没有出现很大的失误，水题出的速度也挺快的，卡题的时间也比省赛少了不少。
开场，发下题来读题，lry看到F是汉诺塔问题，以为是蓝书上的原题，跟我说了，我开始敲代码。过会他看到L更水，叫我敲了，是个简单数论，就是个gcd，敲完测试了 几组数据，提交L1y(2)，全场FB。
过后看有人出了D，zdl给我讲了题意，我敲D，他和lry一块读其他题。 lry发现F数据量100太大了，超过了long
long得上大数，所以就没让我继续写。D题测试之后提交，D1y(12)。
zdl跟我说B题数据量只有40，应该可以直接爆出来，我去敲了B，一开始想错了思路，WA。后来重写，TLE，打印代码Debug。lry上机敲J。
Debug过程中发现n^4会超时，想不出更好的方法，开始读其他题。
zdl看了E题说是个并查集。lry代码出现了Bug之后，打印Debug。zdl上机敲E。我发现C和紫书上一个例题类似，准备一会敲。lry发现Bug，修改后提 交，J1y(65)。
过了一会，zdl敲完了E，测试数据提交，E1y(74)。 我上机敲C，因为读错了题，WA了一次，浪费了不少时间，再次提交，C2y(102)。
我跟zdl开始想A和B两道题，lry说I是个水题，上机敲。 I题提交，WA两次，但lry感觉没什么问题。
我上机敲I，I3y(124)，最后感觉是lry没有使用long long的缘故。 至此6道简单题出完了，成功登顶，领先第二名2题。
过了一会UPC的一个队出了E，和我们只差一题，又过了一会出了A，和我们题数并列，又过了一会出了C登顶。但是他们时间长，我们如果及时出A题，依然有时间优势。
zdl和我推出了A题的公式，提交WA，后续多次修改，依然WA。
这是lry上机敲H，我们继续Debug，中途我还再次尝试对B的代码进行剪枝优化，依然TLE。 lry写好了H，提交，TLE。
封榜前，再次提交A，WA。 我意识到要想登顶，必须得再开一道新题，并且1y才可以。 只剩F、G、K。 F、K做不了，只剩G了。
lry写了一个暴力的程序，输出了答案的前几个。 1、2、5、11、24、53、117…… 然后神奇的事情发生了：
我看这个数列，感觉是有个二倍的关系，再加上个数。加上的数也是递增的，一开始以为是个等差数列，后来发现不是。再后来我感觉是数列里的数。脑补一算，哎呦真是数列里 的数。a[n]=a[n-1]*2+a[n-3]。数列前三个是特殊值0、1、1。具体用了多长时间我也不知道，当时感觉不到1min。
我跟zdl、lry说了，验证了几组数据，对了。
当时只要1y就可以直接登顶，心情激动，提交，OLE，忘记判断EOF了。修改后提交G2y(246)。
当时脑补的时间比UPC的队多了，要想登顶必须再出一道题。失手交错题，心情特别差。
zdl和lry打印之前A题的代码Debug。我感觉B可以n^2枚举之后尺取，我开始写B。
lry发现A题代码下标出现-1越界现象，修改了最新版本提交WA。zdl让我再交一次最初的版本，修改最初版本提交，A6y(287)。8题夺回榜首，UPC的队伍 在出了7题之后再也没有提交过。
当时我也没心情继续写B题了，剩下的时间，我们三个密切关注UPC队伍的状态，直到最后他们提交了F题3次RE，并没有再出其他题。
结束，夺冠。

  • 百度之星

当初看百度之星前复赛就有衣服拿就抱着试试看的心态注册了，没想到最后真的还拿到了衣服，两场比赛都请了场外援助wyd。
初赛打的是第一场，最后一题是个旋转卡壳模板题，求最小面积覆盖矩形，3000分。我赶紧去百度搜模板，居然搜到了，贴模板过了，后来在wyd指导下又过了两道题。其 实B题有份改好的代码，借给队友zdl交了，如果自己交的话排名应该能更靠前，最后我400+进了复赛。
本来听说拿衣服的条件改成进决赛才有，不准备接着打复赛了，但是听说拿衣服的条件又改了，复赛前500有，就有硬着头皮打了一场，最后出了A、B两道题。A题是个暴力 ，自己写过了；B题是个DP，wyd给思路，我卡了好久才搞出来，最终排名400+拿到了衣服。
自己还是水平有限啊。

  • 暑假集训

从市赛到暑假，UVa几乎没刷（貌似是一点没刷），大概荒废了3个月的时间，感觉挺可惜的，到暑假集训该好好干了。
暑假第一周好多人回家了，没有安排比赛，补了不少东西，把紫书8～10章刷了刷，知识面扩充了一些。
从第二周开始就是无尽的比赛，上午刷题，下午比赛，晚上接着刷题，节奏很快，还好之前有些积累不然感觉还真的有点跟不上比赛的节奏了。这段时间很多题都没补，以后得补 上。
组队赛打的是各地区域赛的题，在写这些题的过程中感觉自己的代码能力提升了不少；而且因为随机组队，不和lry、zdl一队，比赛时少了很多配合，很多时候遇到题只能 自己解，独立思考的能力也提高了不少。
个人赛题的难度不是很大，但题目数比较多，比较考验手速和思维速度，还有卡题之后的应变能力。我经常会有初期开题顺，后期卡题之后不换题卡到死的情况。要想解决这个问 题就比较麻烦了，要么提高代码和Debug能力不被卡；要么得多练判断能力，不开坑题或及时换题；都得多加练习才行。
暑假做题的时候我还给uDebug贡献了一道水题的代码，传送门： http://www.udebug.com/UVa/12169
截图留念
这里写图片描述

  • 多校联合训练

多校是在暑假打的，打单独列一段吧。
这是最终的排名：
这里写图片描述
只也算是第一次组队和全国的学校比赛了，感觉自己还差得远呢，在多校中见识了很多解题的方法。
多校里的好多题都是需要多种知识相结合才能出的。有好多次出题都是三个人一起换了好多次思路最后凑过去的，现在我们做这种题目都是要卡好久，最后还不一定能做出来。知 识间的结合真的很重要，记得有个区间DP＋组合数学的题，一开始只用区间DP，没有加组合数，WA到死，后来想了好久才AC。
来年再战。

  • 网赛

区域赛的网赛，我也没出几个题，唯一值得纪念的是北京网赛的B题，手写指针链表过的，WA了好多次，不过中途居然没有RE（说不准是hiho上不返RE）。
代码留念：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 10010;
struct node{
    char c;
    node *fa, *son;
    node(char c = 0, node* fa = NULL, node* son = NULL) : c(c), fa(fa), son(son) {}
};
node *first, *car, *clip, *last;
int n;
char s[maxn];
void ins(node*& pos, char c) {
    node* tmp = pos->son;
    pos->son = new node(c, pos, tmp);
    if (tmp != NULL) tmp->fa = pos->son;
    pos = pos->son;
    return;
}
void del_c(node*& pos) {
    if (pos->son == last) return;
    pos->son->son->fa = pos;
    pos->son = pos->son->son;
    return;
}
void cov(node*& pos, char c) {
    ins(pos, c);
    del_c(pos);
    return;
}
void add_c(bool flag, char c){
    if (flag) ins(car, c);
    else cov(car, c);
    return;
}
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        getchar();
        first = new node;
        last = new node;
        first->son = last;
        last->fa = first;
        car = first;
        clip = new node;
        fgets(s, maxn, stdin);
        int len = int(strlen(s));
        s[len-1] = 0;
        --len;
        bool flag = true, clipst = false;
        int clipcnt = 0, clipsize = 0;
        int carpos = 0, sum = 0;
        node *clips = NULL, *clipt = NULL;
        for (int i = 0; i < len; ++i) {
            if (islower(s[i])) {
                clipst = false;
                if (sum >= n) {
                    if (flag || car->son == last)
                        continue;
                }
                add_c(flag, s[i]);
                ++carpos, ++sum;
            }
            else {
                switch (s[i]) {
                    case 'L': {
                        if (car->fa != NULL) car = car->fa, --carpos;
                        if (clipst) --clipcnt;
                        break;
                    }
                    case 'R': {
                        if (car->son != last) car = car->son, ++carpos;
                        if (clipst) ++clipcnt;
                        break;
                    }
                    case 'S': {
                        clipst = false;
                        flag = !flag;
                        break;
                    }
                    case 'D': {
                        if (clipst) {
                            if (clipcnt > 0) {
                                carpos -= abs(clipcnt);
                                car = clips;
                            }
                            clipcnt = abs(clipcnt);
                            while (clipcnt > 0) {
                                del_c(car);
                                --clipcnt, --sum;
                            }
                            clipst = false;
                        }
                        else del_c(car), --sum;
                        break;
                    }
                    case 'B': {
                        clipst = false;
                        if (car->fa != NULL) {
                            car = car->fa;
                            del_c(car);
                            --carpos;
                        }
                        break;
                    }
                    case 'C': {
                        if (clipst) {
                            clip = new node, clipt = car, clipsize = 0;
                            node* tmp = clip;
                            if (clipcnt < 0) swap(clips, clipt);
                            clips = clips->son;
                            while (clips != clipt->son && clips != last) {
                                ins(tmp, clips->c);
                                clips = clips->son;
                                ++clipsize;
                            }
                            clipcnt = 0;
                        }
                        else clips = car;
                        clipst = !clipst;
                        break;
                    }
                    case 'V': {
                        clipst = false;
                        if (sum+clipsize > n) {
                            if (!(!flag && carpos+clipsize <= n))
                                continue;
                        }
                        node* tmp = clip->son;
                        while (tmp != NULL) {
                            add_c(flag, tmp->c);
                            tmp = tmp->son;
                            ++carpos, ++sum;
                        }
                        break;
                    }
                    default: {
                        clipst = false;
                        break;
                    }
                }
            }
        }
        node* tmp = first->son;
        if(tmp == last) printf("NOTHING");
        while (tmp != last) {
            putchar(tmp->c);
            tmp = tmp->son;
        }
        puts("");
    }
    return 0;
}
  • 回顾、感悟、下一步

现在再来看高考，已经没有当时那种感觉了。高考成绩不会影响到三年的积累和人本身的能力，现在尽自己的努力奋斗就好了，也许这可以成为我奋斗下去的动力，引用去年转发 过的一条朋友圈中的一句。

有一天我们中的大多数人足够优秀，再回来向你们证实青岛二中“造就终身发展之生命主体的意义”的价值。

现在能做的就是为了那一天的到来而努力了，让自己变得足够优秀。
如果高考正常发挥，很可能大学四年都不会走ACM这条路，甚至不会知道ACM是什么，也许这就是命运的安排吧。
既然走上了这条路就一定会好好干下去，回顾这一年UVa刷题270+，HDU训练题150+，大大小小的比赛的题目加起来也至少有一两百道了。错略算起这一年也是刷了 五六百道题了。CF紫名，BC深蓝，TC一战黄名。
这里写图片描述
这里写图片描述
这里写图片描述
回到现在写写自己的打算，练ACM已经一年了，因为要考研，很有可能再练一年就要退役了，大二这一年得好好干了。不久就要区域赛了，第一次外出比赛，想想还有点小激动 呢，尽力而为吧。
大力出奇迹！
这里写图片描述

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **