这是两个本来毫不相干的少年，因为被校园霸凌，从此命运交集在一起的故事。 没想到最后让我心里“咯噔”一下的片段，居然是办案警察说的话。 女警官说：“没有任何一个人会为了另一个人，扛上强奸和杀人的罪名。” 男警官说：“我和你不会，但他们还是少年。” 有人说，这句台词太矫情，不如改成“他们还年轻”。 不，年轻还不足够，只能是少年。 唯有少年，我们才会如此不顾一切，才会相信自己能够保护世界，才会因为爱一个人便为TA付出全部。 少年心气，一抵万金。

故事的缘起，是女主角陈念的同学跳楼身亡。同学们都在围观拍照，只有陈念，因为不忍，走上前用自己的衣服给她盖上脸。结果，陈念成了下一个被欺凌的对象。 陈念是一个单亲家庭孩子，母亲卖三无产品，欠了一堆外债，常年不敢回家。被霸凌的时候，无人可以诉说，也没有人可以保护她。当她遇到小混混小北时，或许就是生命的本能，牢牢想抓住这根稻草，让小北保护她。 小北，被父母抛弃，辍学打架，在底层讨生活。但面对这个弱弱的女孩时，可能就是那股少年意气，那种明亮的小喜欢，他答应保护她。 一、少年，是我能保护世界的相信【你保护世界，我保护你】 小北护送着陈念上下学，但怕对她影响不好，不和她并肩走。陈念不解，说自己不在意。“你往前走，我一定在你后面”小北对她说。从此，高高低低的破路上，一个在前，一个在后；树叶垂落的马路上，一个在左，一个在右；长长的电梯上，一个在这边，一个在那边。星光下，陈念说：“读书考试上好学校，想变成最聪明的人，如果可以的话保护全世界。”小北转头看了一眼，有些混不吝，却带着一种义无反顾：“那说好了，你保护世界，我保护你。” 年少时，我们相信自己能够改变世界。长大后，我们发现只是不想被世界改变，都要竭尽全力。 就像准备拍这部电影时，导演曾国祥和监制许月珍也在困惑，他们想通过电影来表达什么，要为孩子们留下什么？后来他们找到的答案是“为了别人”。许月珍想：“如果每个人都抱有一点为了别人的心态，可能世界会更美好一点。” 或许这就是少年气，知道不能改变世界，但却相信：每个人只要努力一点点，这个世界就会再美好一点点。 二、少年，是爱就要给对方最好的【可是我喜欢一个人，就要给她最好的结局】 为了帮陈念，小北做了一个局，想要把自己送进监狱，替陈念顶罪。陈念不肯，闷头拒绝。两人僵持不下时，小北说：“我这个人什么也不是，没脑子，没钱，也没有未来，可是我喜欢一个人，就要给她最好的结局。” 这是小北，一个少年，能够想到的给心爱的姑娘最好的方式。他在陈念去高考的路上，在每根电线杆上都绑了几朵小雏菊。在那寒风凄雨的日子里，小雏菊是那么明媚干净，恰如小北对陈念的守护，恰如这年少的爱，那是爱情，更高于爱情。 试问，成年后的我们，有多久没有这样爱过一个人了？少年的爱，就像跳水，只管一猛扎子往下跳，无论结果，千金难买我愿意。可就像警官说的那样：“长大就像跳水，闭上眼睛，什么都不要想，就往河里跳，河里会有沙子石头，还有蚌壳，但我们都是这样长大的。”跳过，痛过，所以再难如初。比起去爱，我们更怕受伤。 年少时，以为爱一个人就是全世界。长大后，才知道世界还很大，我们还很渺小。 三、少年，才为输赢对错拼尽全力【只有你赢了，我才不算输】 为了让陈念和自己把这个局完成，小北对她说：“只有你赢了，我才不算输。”有人说，这是少年才会说出来的情话，是少年才会有的宣言。影片中怀孕的女警官，她不相信，会有一个为另一个赌上全部。甚至对陈念说：“但凡你信任大人一些……”她像极了大多数成年人。他们不是善良，只是在生活的粗粝中磨去了温柔的棱角。他们不是不关心，只是见多了冷漠也习以为常。年少时，我们相信世界有是非对错，要争个输赢才行。长大后，才发现经常没有输赢，只有利弊。 直到陈念反复问她：“如果这个世界是这样的，你忍心让你的孩子出生吗？”她突然背过身去，不说话了。其实，他们的内心都有某一处柔软，某一处不甘心，那可能就是深藏在心底的少年气。那一刻的沉默就是最好的证明。 四、少年，才会仰望星空【我们生活在阴沟里，但有人依然仰望星空。】 电影中有一幕，是两个少年在破旧的小屋里，一个看书，一个看着对方。陈念问小北，为什么打架，为什么过这样的日子。小北沉默了一下，说：“你太干净了，你不懂。”然后拿起了陈念的课本，一打开正是奥斯卡·王尔德的名言： We are all in the gutter ,but some of us are looking at the stars. 我们生活在阴沟里，但有人依然仰望星空。 年少的时候，总以为长大了就会变好，就会有力量保护想保护的人。可是，当我们走入成年人的世界里，才发现，原来生活总是一地鸡毛。就像那位男警官郑易，他想保护陈念，但工作太忙总是不到位。他想帮助这两个少年，但结果自己也意气用事还被降职。但在最后，他还是听从了自己的内心，做出了一番努力。他的上司对他说：“你成熟了。”他却摆摆手，走了：“困了，睡觉。” 在成年人世界里，坚持少年心气，总有些许无奈，总有太多不易。 花有重开日，人无再少年。 我们终将难以重返少年，难以回到人生路的开始，但在迷茫焦躁时，不妨问问十三四岁的自己，你会如何选择。因为我们曾经向往的星空，就是少年的自己。 愿你走出半生，归来仍是少年，仍有少年心气。

前言：本次测试是在家通过网络提交进行的，不出所料，我又考得十分“爆炸”，炸到我怀疑人生。

另外，由于以前有一些题目迟迟没有改完，所以我打算改完哪场比赛的题目就先写那场比赛的总结，避免遗忘和拖沓，虽然可能会有些乱。。。

“回文分数”游戏并不简单。游戏的目标是修改最多maxChanges个字符使得一个字符串word的回文分数最高。只允许修改，不许增加或者删除字符。
一个字符串的回文分数定义如下：

1、如果字符串不是回文串，则分数为0。
2、如果字符串是回文串，且长度为奇数，则分数为1。
3、如果字符串是回文串，且长度为偶数，我们将它分为左右两半。计算它的一半子串的回文分数为K（两个一半子串得分一定相同），则原字符串的回文分数为K + 1。

给定一个字符串word和一个型整数maxChanges，返回最多修改maxChanges个字符后最大可能的回文分数。

回文串的定义是一个字符串从前向后读和从后向前读完全一样。

如果把x改成a，得到偶数长度的回文串”abcbaabcba”。它的一半子串是奇数长度的回文串”abcba”，所以子串分数为K = 1，因而最后得分是K + 1 = 2。

我们可以把c改成r，把e改成o，得到”rodor”。这是一个奇数长度的回文串，所以得分为1。

解题思路(模拟+贪心)

这题做得我十分痛苦，其实这是一道比较简单的贪心+模拟题。我一开始的做法就是照着题目要求模拟，在一次比较，两个字符不同时，关键就是如何替换才使答案最优。如果随便替换的话将对后面的答案有影响。所以我当时的做法是处理一层的替换的时候看看下一层，怎样替换对下一层更优我就怎样替换。本质就是看看字符的出现个数。

然而这样未必对，我们知道，如果当前层对下一层一样优的话，对下下层可能不一样。但是我这样做也有94分，好一段时间内我不知道该怎么改。其实必须边递归边展开所有层判断是否能继续，再统计答案。由于层数不超过6层，所以这样不会超时。但这样的方法其实并不直观们还有一种更易理解的方法。

直接枚举答案,假如长度为12，枚举的答案为2，则可以表示为1 2 3 3 2 1 1 2 3 3 2 1，然后将相同数字的位置改成相同字符即可。如何改就贪心，改成哪个字符修改次数少就那么改，再和maxChanges比较判断答案。

你有一台超小的电脑，内存只有两个寄存器：X和Y。寄存器只能存储正整数，一开始两个寄存器的值都是1，电脑操作系统只有两种指令：指令[X]和指令[Y]。
指令[X]的功能是：X ← X + Y，即把两寄存器目前的值累加到X寄存器；
指令[Y]的功能是：Y ← X + Y，即把两寄存器目前的值累加到Ｙ寄存器。例如：指令序列”XXYYX”的执行过程如下:

可以发现，执行指令序列”XXYYX”后，X寄存器的值是10，Y寄存器的值是7。现在你的任务是：给你一个正整数R, 你要编写指令序列，使得最后X寄存器的值是R (此时Y寄存器可以是任意整数). 当然，我们希望你编写的指令序列的长度要尽量短，在此前提下，如果有多种方案，请输出字典序最小的一种方案。

一个字符串，代表生成R的长度最短的指令序列。

解题思路(更相减损术(迭代)+gcd)

如果直接宽搜，必定超时。
我们必须注意到一点，如果我们枚举一个Y，是可以直接根据最短步数得到方案的。
这个得到方案的方法就是在数学上有了解到的更相减损术。

容易证明，我们不断用大数减小数，得到的差和较小数再次重复做这个操作，不断迭代，步数一定是最短的。根据一些方法，我们可以知道可能的最少步数不会超过三十几步，这里我是用斐波那契数列去发现的(然后考试时我就想歪了。。)。

于是时间就是枚举Y(1e6)然后乘上个三十几。至于枚举的Y不一定是合法的，合法的前提是与给出的X互质，为什么呢？因为更相减损术就是在求gcd啊！于是不与X互质的Y必然不会产生合法答案。然后就写个欧几里德算法判断，时间照样不成问题。不过考试时我思维僵化，连方向都错了。

字典序就做完一次判断更新答案。如果算的过程中，答案长度已经超过可能的最优长度(三十几)或当前答案，就不用往下做了，直接跳过，这样可以节省很多时间。最后倒叙输出答案就行了。

坑点：第一是特判，然后不要用字符串，要用字符数组记录答案，否则超时。。

FJ最近得到了一份工作，那就是送肯德基外卖。FJ所在的小镇可以看作是R行C列矩形，被划分成R×C个单元格子，从上往下，行的编号是1至R；从左往右，列的编号是1至C。FJ一开始在第1行第1列的格子处，他收到D个顾客的订单，第i个顾客的位置在第Ri行第Ci列的格子。FJ一开始就把所有顾客的订餐一起装在背包里，这样在送餐过程中就没必要一定要返回出发点了，FJ必须严格按照次序给顾客送肯德基（即先送完第1个顾客，再送第2个顾客，…依次类推）。当送完所有的肯德基外卖后，FJ也没有必要返回出发处。FJ每一步的移动规则是这样的：FJ可以从当前格子移动一步，到达相邻的左格子或者相邻的右格子（两个格子相邻是指它们有公共边）；此外，如果FJ当前所在格的列是第1列或者第C列，那么FJ还可以向上移动一格或者向下移动一格。任意时刻，FJ都不能走出矩形的边界。FJ每进入一个格子，都会在该格子停留一定的时间T，在不同的给子，FJ停留的时间可能不同。FJ送完所有订餐，至少需要多少时间？

第一行，两个整数，R和C。
接下来有R行C列，第i行第j列的整数表示FJ进入第i行第j列的格子，必须在那个格子停留的时间T
接下来一行，有一个整数D，表示有D个顾客订餐。
接下来有D行，每行两个整数，依次表示顾客的位置，即所在行和所在列。 顾客所在的位置没有重复。

一个整数，送完所有订餐的最少时间。

首先要吐槽一下题目的翻译，FJ送肯德基。。

本题多种做法，我在考试时没时间了(吃晚饭)，于是写了一个狂暴的SPFA，地图上每个点都提出来做最短路，拿了50分。然而最短裤(路)能拿70分，dp是满分。

首先讲讲SPFA的方法求最短路。
我们发现由于只有第一列和最后一列是可以向下向上走的，其他的只能横着走，于是我们将那两列点单独拿出来做一遍SPFA，建图、做法就不用说了，维护行和列的前缀和，这样就得到了这两列点互相到达的最短路了。注意这里做2n次SPFA，时间复杂度的级别是 ，k是SPFA的常数，m是边数，与点数成正比，这样其实理论是n^2的，但是常数太大，所以很慢。但实测也是能过的（前提是加了玄学优化）。

算出那些点的最短路后，对于每组询问，我们分5种情况，设二点为A和B，第一列为1，最后一列为m，则

上面所有行的第三个箭头都是沿最短路走，其他的打横走就查询部分和。于是，通过SPFA求最短路，分类讨论取最小值，就可以解决此题了。不过SPFA部分我写的比较复杂，也不如下面的DP方法巧妙。

其实DP的做法也是在求最短路。
不过，计算最短路的时间是严格的 O(4n2) 。首先我们除了 dis[i][j] 表示点 i 与j的最短路外，我们要先预处理出一个 表示第i行的左边的点向右边的点走的最短路径。就是从第一列的某个点出发，通过各种“蛇皮走位”，到达同行的最后一列的最短路径。

为什么要先算这个呢？假设不是同一行的点，最短路径可能绕很多次。如下图

当行数变多，拐的弯可能越来越多，枚举拐点是不太可行的。而当同一行时，拐一次一定是最优的。如图

若红色的是最短路，由于T非负，毫无疑问黑色的路径更优。

那我们枚举拐点求出 cost[] ，然后用 cost 去更新 dis 数组。具体的更新就是按照如下次序：

如果当前最短路的源点在左边，更新次序就是第i行的右边，再到第i行的左边，反之就相反。更新的方法就是用部分和与 cost ，具体的公式参见代码，注意不要算重算漏。

预处理的时候我们知道每个点到自己的最短路和对面的最短路。然后n^2按行数向下更新就行了，只向下是为了避免重复计算。

最后一样的分类讨论算出答案。

考试时很不在状态，简单的题居然脑抽不会做，还有希望以后改题写总结能快点，不然很多事情都做不了，好好把握时间才行，争取多做有意义的事，提高水平。

愿你走出半生 归来仍是少年