写在二十岁

“男的是个很神奇的物种。给男孩一把玩具剑，他便成了男人；给男人一把玩具剑，他便成了男孩。”

一次学习会上讨论时，学弟晨曦说自己即将二十，弱冠之年，是古人十分重视，学弟想好好总结自己的过去，二十年来的见闻、所读的书、所遇的人。当时我想，我也快到二十了吧，自己很早的时候也想写一篇文章好好总结。想了很长时间，思考自己过去的事情，去想自己过去的想法、收获与遗失。总结是件很难的事，因为总会有你当时很想记起如今却又忘记的事情。所以这篇总结，也不知道丢失了多少过去很想将来写下的东西。（这篇文章最初写在 20 岁生日那天，不过写的时候逐渐偏离初心，于是也便暂时停笔，后面又准备面试，久久没有继续。今日得闲将它补齐。）

先说与自己专业、工作、前方的路相关的吧。对于编程，我心中有一团火，与生俱来。想了很长时间，我终于在最近几天想出了如此的描述。我觉得我生来便是要编程的吧。陈寅恪大师将爱情分为四境界，最伟大最纯洁的爱情应当是完全出于理想，“情之最上者，世无其人。悬空设想，而甘为之死，如《牡丹亭》之杜丽娘是也”。我觉得我对编程便是如此吧。我在没有遇上编程的时候便喜欢上了编程，希望以后自己也可以写程序。小时候在我第一眼看到电脑的时候，在我每次用电脑或者说玩电脑的时候，我都会想它是怎么运行的，所谓的代码应该是什么样子，它的逻辑是如何，应该怎么实现。玩游戏时我很好奇它是怎么实现的，猜测着它的实现方式。难道是把所有玩法的可能性都模拟一遍吗？不，想了好久，我得到的回答是否定的，觉得这样会很难。比如我打坐一分钟，编程者想到了，把打坐一分钟写了进去，那我如果打坐一分钟零一秒，那他也要写进去吗？那我打坐的时长是无穷可能的，他都要实现一遍吗？想到这些我就把模拟这种方法否定了，又开始想其它的办法。很多男孩子从小就有拆卸机器的爱好吧，要不是家里就一台电脑，拆坏了就会 game over，我不知道会把这台电脑拆成什么样子 = =。很幸运，这种编程的欲望一直还在，且愈来愈深。遇到 C 语言时，敲出第一个程序时，自己都超级幸福，直到现在，每当敲起代码时还会幸福感爆棚，每当敲起 hello world，心中总是有如清霖润洗一般。当然会有着不知多少倍受打击的时候，但想起过去的那个小男孩，想起高中时忍不住在纸上写链表的那个男孩，总会走下来，觉得自己不可辜负过去。有人问起我网名的意义，其实 {}←enter↑→enter 是自己编程时候的起手式，是自己敲花括号时一种习惯按键，大概是之前在用 VC++6.0 时候养成的吧，每次敲起 {}←enter↑→enter 序列时，自己会有一种名叫编程仪式感的东西，心里会很开心。之前队友说很享受我敲花括号的时候，当时听到这个超开心的。

我很喜欢比尔盖茨的一句话：“每个人都有一颗世纪之眼，它能看到上个世纪人们看不到的东西。” 我从小就很喜欢很酷的事情，满脑子想着一些美好的设计。遥控器这种东西真的吸引了我很久，那种从远处就能让电视换台的操作，在我眼中简直不啻魔术一般。我好奇了很久，直到初中时候老师告诉我们有红外线这种东西，之后我又开始好奇红外线为什么能够让电视换台，（逃）。我很小的时候就会想如果我们能在远处知道家里窗户有没有关，并能够操控他们开关，空调、暖水壶什么的亦如是，那应该多酷。那时候手机还是小灵通、翻盖等等，就会幻想着能在手机上操控着家里的电器。没想到当初天马行空般的幻想，如今已变成了眼前的东西。我想小时自己所想的，便是那颗世纪之眼才能看到的吧。自己身处物联网的时代，或许这些幻想的实现，恰是我们一代人要做的。所以如果有机会，我超想能做物联网，亲手去一点点实现小时那些幻想。有一个梦我至今依旧清晰，大概是初一初二的时候，我梦到在一个节目上比尔盖茨亲手送给我一个触屏的计算器，界面简约，功能强大，当自己触摸按钮时，喜悦而醒。当时心里觉得 oh， 这实在是太酷了，在当时那个智能手机还没普及的年代，这样的东西如同宝物一般。如今看来，不过只是手机上计算器 app，自己都懒得去写了（逃）。过去选编程这条路也是和家里有些许争执的，现在想来，或许是过去他们未曾看到我所看到的东西，未曾看到我心里那团火吧。

说到和家里在职业上的争执，突然想到了大学前看到一篇文章，文章名可能叫《我为什么（选择？留在？漂泊？）在北上广》，记不太清楚了 (更新，找了下，名为《我为什么不愿离开北上广》《我为什么不愿离开北上广》)。里面一句话和我看法一样吧，“父母所谓的稳定，其实不过是一种变相的啃老”。或许和部分家长的想法一样，我家里想让我走医生、机关等一类的工作，在家附近，还能够稳定些。可我觉得自己从小开始，骨子里就有着对新事物、对外面世界永不停息的好奇与追索。小时的村子，村口的有一条较窄的路，两排种着树，连向村头，我那时觉得，到达那里，便是外面的世界。我从小觉得自己所处的环境很闭塞，像桃花源一般，与世隔绝，外面的信息进不来，里面的信息出不去，如同孤岛，每天的新闻都与自己的周围无关，在网上找不到一丝自己所在地的影子。我很厌倦这样的状态（连电脑上看到的零食广告都看不到，难过，当时好想吃的），对大城市愈加痴迷，一心想走出去，去外面看看。高三暑假晚上，我漫步在长安街上，看着华灯闪耀，看着川流不息，看着光影迷离，感觉自己像是握住了时代的脉搏，心告诉我：我应该属于这些。我厌恶所谓的人脉交际，信仰着美国梦中说的 “只要经过努力不懈的奋斗便能获得更好的生活，亦即人们必须通过自己的工作勤奋、勇气、创意、和决心迈向富裕，而非依赖于特定的社会阶级和他人的援助。” 我从未认真地对家人说起这些我自己内心的想法，我知道我小时候说这些他们肯定会不加思索地轻笑，说我还小，未经社会，年少无知等等。但我也深知，我自是年少，我有着年轻人所应有的年少轻狂，我有着改变世界的梦想，不惧一切，披荆向前。我懂或许拼搏一生，我仍一无所获，回到故乡，未能得到自己想要的，成为大众中庸庸一名，我也会觉得不负至此一程。我觉得年少时假若不狂一些、傲一些、梦想大一些，便是对年少的辜负。每个人老后都会归于茶水，但谁没有爱喝可乐的时候呢。一段时间前读过这样一个句子 “少年就是少年。他们看春风不喜，看夏蝉不烦，看秋风不悲，看冬雪不叹，看满身富贵懒察觉，看不公不允敢面对”，初读时觉得很有意味，但后来一想，却又觉得 “少年就应看春风而喜，听夏蝉而躁，闻秋风而悲，见冬雪而叹”，这样才能不负少年。年龄越大，越是信奉喜欢罗曼罗兰那句 “Il n’ya qu’un héroïsme au monde : c’est de voir le monde tel qu’il est et de l’aimer.”（世上只有一种英雄主义，就是在认清生活真相之后依然热爱生活。）

人生前二十年，避不开的便是高考和大学这一话题。没有考上自己想要的大学也是自己避不开要谈的。其实我之前一向觉得一个人的梦想是要在自己胸腔中，点燃自己的，而非去告诉别人、宣告天下的。我觉得自己未和很多人说起自己具体的梦想，具体要上的大学，只会和挚友说起。不太熟的人问起的时候也只是搪塞耸肩一笑，说 “当然是想上个好些的大学，和编程有关”，点到而已。可奇怪的是好像所有的人都知道我想要上的大学。那个时候我很难受，因为和我心中对梦想的定义不相符，所谓的梦想后来渐渐成了一种压迫在身上的负担，而非是最初激励我前进的动力。我知道在高考失利面前没有借口，在得知成绩后我没有太大的失望（或许是很早的时候就想到了结果），更没有如同当年看的小文、视频一般嚎啕大哭，而是很快的平静了下来，想着以后要走的路，以后去抹平没考好要付出的努力。我从未在心里把大学当成一段享乐的时间，而是求知的地方，是做自己真正喜欢的事情的地方。得知自己最终去往南邮的时候，我便心知 “假若我不是学校中的佼佼者，那我便没资格抱怨”。如今我依旧未能成为学校的佼佼者，所以也未曾抱怨学校配不上自己如何如何。记得自己来大学时发的动态是 “希望我的大学，比我的高中更加努力”，让父亲刻了一枚章，为 “殷鉴不远”，取《诗经》中 “殷鉴不远，在夏后之世” 之意，意为铭记高中失败之往事，以它为前车之鉴，吸取教训，以警未来。南邮有让我满意也有让我失望的地方，失望的地方还是在其教育体制以及学风，问及老师较为拓展的问题时，会感觉老师避而不谈，或是含糊其辞，亦或是直接说不需要掌握。满意的地方在于我很大地提高了自学能力，以及前些天说的 “眼界始阔”，我觉得这才是大学更重要的，教人以智慧优于教人以知识。还有幸运的一点是遇到了一群伙伴，志同道合。没有考上理想大学的遗憾还是有的，我不知多少次将路边指示牌想错，看到 “京邮电大学” 就会想到北邮，恍惚过后才想起自己身处南京，任何和北邮有关的东西总会第一时间跑入我的眼帘，尽管自己逃避不想见到他们。或许是出于一点点的自命不凡的心理，在 ICPC 南京区域赛的时候看到有两个北邮的队伍在自己后面，突然有种两年没有虚度的安慰感。

二十年间最满足最得意的事情，便是在大学中寻找到了自己一生的灵魂导师 —— 王阳明。小时不懂王阴阳，因课本格竹一事误会了先生十年。大二时见先生言行，方知一生俯首拜阳明。其实选一个人作导师并不难，只要两人思想相契就好。我读先生时，便觉我的认知与先生有相似的地方，他人觉得怪异的思想于我看来是正常不过的，于是便认定先生为我灵魂导师。心明了了，理也便明了了。每次有困惑去读《传习录》时，都有大悟之感。无善无恶心之体，有善有恶意之动，知善知恶是良知，为善去恶是格物。阳明先生顿悟时在贵州栖霞山，而我开始追寻先生亦是在栖霞，虽非一处，但名字却是相同，也算是一种上天注定的缘分吧。

我是个完美主义者，也是个极简主义者，觉得完美和简单的设计能给自己带来极大的满足。我的完美主义几于是病态的，在做任何事之前都会纠结很久，因为一件事对我来说，我要么将它做到极致，要么根本不去做它。我发现自己有着暴君的体质，当别人所做的达不到自己的预期时，就会忍不住对他的不满。为了避免如此，我一向更多地去自己做事，而大学里的团队作业实在是我最头疼的事情，因为最终的结果总是和自己的预期相差甚远。我追求完美主义，我逃避去做图片、视频、或者幻灯片，因为我不会用 PS、AE、PowerPoint 等工具，但我却想着各种整体或细节的处理。因为完美主义，我也在一些认知上和他人有着极大的分歧，后来我才明白，别人说的会做一件事是做出，而我理解的会是将其做好。周围总有人说什么计算机市场已经饱和不缺人一类的话，而我坚持觉得极度缺人，也是后来才明白，他说的人是人力人数，我说的人是人才。而我天生固执又倔犟，从不愿在这种事情上和他人妥协半分。完美主义让我十分苦恼，但我依旧愿意坚持。我的性格里有着偏激的一样，有着赌徒梭哈的孤注一掷，持精一之功，更喜欢 All in 的魄力。我认为大道至简，上帝是喜欢简单的。一条线、一个圆，在我眼里有时都是极美的，$e^{i\pi}+1=0$ 在我眼里不知胜过多少市井嘈杂， 程序中的 “hello world” 便是最美的情话。（最近看到爱因斯坦的一句话 “万物应该简单，但不应过于简单”）

思二十年间见闻，我觉得包容和谦虚两者最为重要。我见过太多为显自己博识而大放厥词滔滔不绝之人，看过太多持一家之见而抵斥他家之人，我总觉得他们很浅薄，可悲又可笑。我深知我所学的所知道的知识都是在它所在领域的皮毛，甚至皮毛也算不上，是这个领域最基础，最浅显的知识。真理无穷，进一步有一步的欢喜，亦有着向前一步所带来的恐惧。因为向前一步，你会看到更广阔的天空，更高峻的山峰。之前的时候我没能理解一句话，现在却是真真地感受到了。你的知识面是一个圆，你所知道的东西便是它的半径。你所知道的东西越多，那它半径也就越大，知识面也就越大，但在它圆周上，所接触到的新知识未知的知识也就越多，越会感觉到自己的渺小无知。所以我总觉得越有智慧的人他们越会觉得自己无知，因为他们能够看到真理无穷。而相反，那些较为浅薄之人越会自觉狂傲（不是外在表现出的狂傲，而是内心因无知而无所在乎敬畏的狂傲）。我一向喜欢空杯理论，也一向把自己自诩为空杯（其实实际上就是），学习或者处事的时候能够有所辨别地将他人的智慧放入进来，永不觉满。有人持一家之见或不知知识无穷而不愿将自己放空，便也无法吸收进新的知识。或许他们的容量也只是那些，只能够盛下一杯子的水，而谦虚者却是江海湖泊。前面所说的为谦虚，包容亦是如此。我很不习惯没有包容之心的一个人，他们看到与自己想法、立场不一样的人或事就开始开口成喷，遇到自己不能理解看不过的事也便不予包容。我亦是觉得他们可悲又可笑。有时一个人或一件事之所以成为如今的样子，往往与他的过去有着千丝万缕的联系。有人不去一丝丝分析便只就如今的模样去喷与怼，这不过是暴露智商的表现。学会了包容，天地也便开阔了。你不再拘于过去的一己之思、一家之见，而去往更广阔深入的思考，往往能够另有所得，能够明白这世上的人或事为什么会是现在的样子。如果一个人能够容纳两个相反相悖的理论，那这个人将会很可怕。我自觉自己是这样一个人，学习一家的思想后假若接受到与之相悖的事物，只要它不是本质为恶，并不会直接奋起反对，而是一点点将两者融为一体，将两者都放在自己的口袋中。

最近也加了一些程序员的群，发现自己变得愈加喜欢程序员们，或者说愈加喜欢向上的人。他们能够意识到自己要学习的还有很多，一向保持着谦虚昂扬的姿态，保持着登高自卑的决心，每天和他们交谈，会觉得有着一身向上的动力。或许是程序员自黑惯了，只有他们自己知道这一行业的有趣。我一直觉得一个男人的魅力只有一小部分在颜值，更多的在于他的视野与能力。

大学这几年也是自己责任意识苏醒的时期，无论是为家的责任、还是为国的责任。有时在行走或是骑车时会听一些曲子，如骆玉笙先生的《重整山河待后生》，不时落泪，那时候方知责任落在我们一辈的身上。重整山河待后生，我们便是后生。我一向很敬畏 “先生” 这个词，日常中也极少去用它。只有在说自己最为崇拜之人时，才会加上这两字。二十年来，看见了不知多少阴暗向下的世事言论与自暴自弃之人，方知先生当年灼见、文辞中的鞭笞。最后用先生的文字来结尾吧：

愿中国青年都摆脱冷气，只是向上走，不必听自暴自弃者流的话。能做事的做事，能发声的发声。有一分热，发一分光，就令萤火一般，也可以在黑暗里发一点光，不必等候炬火。

2019 年 3 月 9 日

题目链接

因为在准备谷歌面试中，本来准备最近并不更新刷过的题，多刷些题。但由于这题对我来说意义很大，所以记载了下来。

为了节省些时间，题目题意在这里不复制粘贴了，可以在上面的链接跳转过去。

Solution

Idea

题目是很直接的 BFS ， 相比较最简单的迷宫寻路问题，这题增加了钥匙和门，即如果我们想要通过一个门，必须在此之前获得它的钥匙。 注意题目中的数据范围，门和钥匙最多为 10. 故可以用状态压缩记录状态。

Code

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

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

typedef struct point
{
    int x, y, key, step;
    point() {}
    point(int _x, int _y, int _key, int _step) : x(_x), y(_y), key(_key), step(_step) { }
} P;

int n, m;
char maze[107][107];
bool vis[107][107][1050];
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

int main()
{
    memset(vis, false, sizeof(vis));
    scanf("%d%d", &n, &m);
    getchar();
    char ch;
    int startX, startY;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            ch = getchar();
            maze[i][j] = ch;
            if(ch == '2')
            {
                startX = i;
                startY = j;
            }
        }
        getchar();
    }
    
    queue<P> que;
    que.push(P(startX, startY, 0, 0));
    int curX, curY;
    P p;
    
    while(!que.empty())
    {
        p = que.front();
        que.pop();
        if(maze[p.x][p.y] == '3')
        {
            printf("%d\n", p.step);
            break;
        }
        
        for(int i=0; i<4; i++)
        {
            curX = p.x + dx[i];
            curY = p.y + dy[i];
            if(curX < 0 || curX>=n || curY < 0 || curY >= m || maze[curX][curY] == '0' || vis[curX][curY][p.key])
                continue;
            ch = maze[curX][curY];
            if(ch >= 'A' && ch <= 'Z')
            {
                if( p.key & (1 << (ch-'A') ) )
                   {
                       que.push(P(curX, curY, p.key, p.step+1));
                       vis[curX][curY][p.key] = true;
                   }
            }
            else if(ch >= 'a' && ch <= 'z')
            {
                que.push( P(curX, curY, p.key | ( 1 << (ch-'a') ), p.step+1) );
                vis[curX][curY][p.key] = true;
            }
            else
            {
                que.push(P(curX, curY, p.key, p.step+1));
                vis[curX][curY][p.key] = true;
            }
        }
        
    }
    return 0;   
}

闲言

之所以说这题对我意义比较大，是因为在一次很久之前的训练时，有学长出了这道题。

那时候我还是个小白，几乎啥都不会，连 dp 是什么都不知道。那时候做到这个题还是蛮受打击的。讲题目时这题是邓新议（应该是）学长讲的。学长又讲到状压，把拿到我钥匙压缩为一个状态，当时我的心里几乎是崩溃的，因为学长们说的名词我都没有听过， 有一种很无力的感觉。

回去的时候，我一个人走在北操前的路上，有些流泪？因为深深地感受到了自己什么都不知道。于是回去查了 dp，状态压缩一些名词的意思， 这才知道原来 dp 是动态规划的意思。

所以对这题印象蛮深的，过去后一直想再见见这题。昨天刷题时看到题目名字中有个迷宫寻路，心想，不会是有钥匙和门的那道吧。

现在在看这道题，只感觉是一道很基础的题目了，很容易地就能够过掉。对比起来，自己还是学到了些知识的，进步了很多。 也算是给那晚独自一人的自己一个回答吧。

今天看代码的时候看到有人在 sort 里用了 lambda 表达式，好奇心爆棚的我就寻思这样用的效率和我们定义一个函数之后调用这个函数两种方法哪个效率高。

于是自己动手比较了下，因为之前从没有用过 lambda 表达式，所以这也算是自己第一次使用 lambda 了。

比较代码

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

#include<cstdio>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;

const int MAXN = 1e6+7;
bool cmp(const int &a, const int &b)
{
    return a<b;
}
int main()
{
    srand((unsigned int)time(NULL));
    vector<int> vec(MAXN);
    int time1 = 0;
    for(int cnt=0; cnt<5; cnt++)
    {
        for(int i=0; i<MAXN; i++)
            vec[i] = rand();
        int start = clock();
        sort(vec.begin(), vec.end(), cmp);
        time1 += clock() - start;
    }

    int time2 = 0;

    for(int cnt=0; cnt<5; cnt++)
    {
        for(int i=0; i<MAXN; i++)
            vec[i] = rand();
        int start = clock();
        sort(vec.begin(), vec.end(), [](const int &a, const int &b){
                return a < b;
             });
        time2 += clock() - start;
    }
    printf("%d %d\n", time1, time2);
    return 0;
}

输出

多次实验后， time1 (不用 lambda 方法) 时间大约为 2050 ms 左右，而 time2 （使用 lambda 方法）耗时大约为 2250 ms 左右。所以估计 lambda 表达式效率会低一丢丢。

题目传送门

博客参考 : https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/uva-1471---defense-lines

我回到美国之后感受到的文化冲击，比我去印度时感受到的还要强烈。印度乡间的人与我们不同，我们运用思维，而他们运用直觉，他们的直觉比世界上其他地方的人要发达得多。直觉是非常强大的，在我看来比思维更加强大。直觉对我的工作有很大的影响。

西方的理性思维并不是人类先天就具有的，而是通过学习获得的，它是西方文明的一项伟大成就。而在印度的村子里，人们从未学习过理性思维。他们学习的是其他的东西，在某些方面与理性思维同样有价值，那就是直观和经验智慧的力量。

在印度的村庄待了 7 个月后再回美国，我看到了西方世界的疯狂以及理性思维的局限。如果你坐下来静静观察，你会发现自己的心灵有多焦躁，如果你想平静下来，那情况只会更更糟，但是时间久了之后总会平静下来，心看事情会更加透彻，也更能感受现实的环境。你的心灵逐渐平静下来，你的视界会极大地延伸。你能看到之前看不到的东西。这是一种修行，你必须不断练习。

禅对我的生活一直有很深的影响。我曾经想过要去日本，到永平寺修行，但我的精神导师要我留在这儿。他说那里有的东西这里都有，他说得没错。我从禅中学到的真理就是，如果你愿意跋山涉水去见一个导师的话，往往你的身边就会出现一位。

近日复习之暇，看完了《西南联大》纪录片，几度落泪，盖一年之泪点皆在此。思大一时近现代史纲要报告，吾题为《违千夫之诺诺，作一士之诺诺》，即写西南联大事。余于大学两载，眼界始阔，今日观此片，又生新悟，每看联大，皆有朝圣之感，故记之。然时至期末，时间尚紧，行笔匆匆，文章烂漫，加之感悟颇多，不免混杂失秩，有所佚露，来日有时更复修。

纪录片开头引《西潮》句，“目睹国帜三易”，仅仅六字，时事何坚！此余初落泪耶。思之痛之，更复叹之。时中国积百年之弱，不堪帝强欺凌，受鲸吞蚕食之耻而难以抗。今日有国泰民安之象，目光放远，览千年之史，方知不易，复看今年时局，更不敢放下一丝警惕。一年来，观媒体之言，群众之应，惊民智之未化，觉一国之根基需在教育，非知识之教育，而乃眼界之教育，智慧之教育。

连续的数据，如 abcdefg , 经过多次循环移位后，（如 abcdefg 经一次循环移位后变为 bcdefga ），该数据会变为什么。

我们知道数组的移位是 O (n)，很耗时间，如果连续移动 m 次的话时间消耗会很大。最近在读《编程珠玑》， 上边提供了两种算法。第一种称之为 “杂技算法”，即给定一些临时空间（设为可存放 k 个数据，需连续移动 m 次），先将前 k 个数据放入里面，之后将第 m+1 到第 m+k 个数据移入第 1 个到第 k 个中，其后依次移入其所在位置。（本文章并不想详细说此方法）。

第二种方法则比较巧妙，使我想起了暑假集训时做到的一道题目。那道题目和本题很相似，不过是要做多次这种连续移位，更加复杂。但其解决方法的思想和第二种方法思想一致。若总共有 n 个数据，要连续移动 m 次，算法如下：

• Reserve(0, m-1)
• Reserve(m, n-1)
• Reserve(0, n-1)

如 abcdefg ， 第一步翻转后变为 cbadefg , 第二步后变为 cbagfed , 第三步后变为 defgabc。 即为答案，十分巧妙！

暑假那题因为需要多次进行连续移位，所以用到了 Splay 树。还有巨巨们用了 rope（块状链表）。 也是我第一次听说这种数据结构。不过 Splay 树效率更高些。

我一直只知道 C++ 子类函数对父类函数有重写操作，最近才知道了有重定义这么个概念，原因来源于类似如下代码：

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

class Base
{
protected:
    int a;
public:
    virtual void seta()
    {
        a = 0;
    }
};

class Derived : public Base
{
public:
    void seta(int x)
    {
        a = x;
    }
};
int main()
{
    Derived a;
    a.seta();   //error，candidate expects 1 argument, 0 provided

    return 0;
}

我的本意是想调用父类中的 seta() 方法，结果却报错了。这是我当初写代码时不曾想到的。我本想这算是函数的重载，派生类中有两个方法，结果事实（程序）却说明派生类中只有一个 seta(intx) 。

原因

函数重载发生在相同的范围内， 也就是说在同一个作用域内， 而上面代码两个方法一个在父类， 一个在子类， 并不处于同一个作用域。 这里发生的是重定义， 基类的方法将会被隐藏。

下面给出重载，重写，重定义三者的特征。(来源： Fred^_^)

• 函数重载（overload）
  函数重载是指在一个类中声明多个名称相同但参数列表不同的函数，这些的参数可能个数或顺序，类型不同，但是不能靠返回类型来判断。特征是：
  （1）相同的范围（在同一个作用域中）；
  （2）函数名字相同；
  （3）参数不同；
  （4）virtual 关键字可有可无（注：函数重载与有无 virtual 修饰无关）；
  （5）返回值可以不同；

• 函数重写（也称为覆盖 override）
  函数重写是指子类重新定义基类的虚函数。特征是：
  （1）不在同一个作用域（分别位于派生类与基类）；
  （2）函数名字相同；
  （3）参数相同；
  （4）基类函数必须有 virtual 关键字，不能有 static 。
  （5）返回值相同，否则报错；
  （6）重写函数的访问修饰符可以不同；

• 重定义（也称隐藏）
  （1）不在同一个作用域（分别位于派生类与基类） ；
  （2）函数名字相同；
  （3）返回值可以不同；
  （4）参数不同。此时，不论有无 virtual 关键字，基类的函数将被隐藏（注意别与重载以及覆盖混淆）；
  （5）参数相同，但是基类函数没有 virtual 关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）

之前一直读不懂书上说的 cout 运算顺序为从右向左什么意思。昨天遇到一个问题明白了一些。题意大概是让我们写个 ID 类，ID 类里有个方法是 nextID() ，即返回现在的 id ，再让 id 自增 1（id 初始为 0）。所以我觉得这样写就好。

1
2
3
4

int nextID()
{
    return id++;
}

在之后的输出中（为了简便，我把空格啥的都删了）

1
2
3

IDSystem x;
cout << x.nextID() << x.nextID() << x.nextID();
cout << x.nextID() << x.nextID() << x.nextID();

我本来觉得应该输出 0 1 2 3 4 5，但事实却是 2 1 0 5 4 3。

我惊了，我本以为是 Codeblocks 出 Bug 了，重启后结果还是如此。此后，在校队群里问了后才想起知道原来是 cout 从右向左压栈搞的鬼。这样也就不难理解为什么如此了。(也懂了其他一些运算顺序从右向左的道理)

下面给出刁老板找出编译器汇编的代码：

原来 cout 是有栈的。
之后刁老板又测试了如下代码：发现已经解释不通了。孙心乾大佬说一个语句中同时读和写同一个变量算是 ub (undefined behaviour) 吧。

哈哈哈，被谷歌十动然拒了。

继续加油。