Day 7

不知不觉日程已经过半了呢……集训刚开始的时候总觉得14天好长，结果不知不觉就过去了七天呢（顺便欠了好几天的题解）。大概到了Day 14我会一也像这样感慨万分吧…
今天的题其实还是很有难度的，不过似乎考的算法比较单一然后咱就觉得还是简单的

T1 X国的军队

贪心。和昨天讲的杂题十分相似，然后咱就爆零了Qw
从题目描述中我们可以知道，投入作战的士兵要么中途战死，要么打完最后一场战役退役。显然，要拿下所有的据点，死亡的士兵数量是相同的，那么，我们投入士兵的总量只与最后打完最后一场战役退役的士兵数量有关。我们让这个数量尽可能少即可。
显然，这个数量只与最后一场战役和倒数第二场战役有关，我们按b_{i}-a_{i}降序排序即可。

T2 排列组合

不敢相信咱T1爆零T2AC Qw
题目要求\sum\limits_{i=0}^{n} C_{n}^{i}*C_{n}^{i}。可证这个式子是等于C_{2n}^{n}的。那么我们预处理2n!和n!的逆元即可。
证明：
考虑二项式定理。(1+x)^{n}=C_{n}^{0}+C_{n}^{1}x+C_{n}^{2}x^{2}+…+C_{n}^{n}x^{n}
(1+x)^{2n}=C_{2n}^{0}+C_{2n}^{1}x+C_{2n}^{2}x^{2}+…+C_{2n}^{n}x^{n}+…+C_{2n}^{2n}x^{2n}
对(1+x)^{n}一式进行多项式卷积，得到C_{2n}^{n}x^{n}=C_{n}^{0} * C_{n}^{0}x^{n}+C_{n}^{1} * C_{n}^{1}x^{n}+C_{n}^{2} * C_{n}^{2}x^{n}+…+C_{n}^{n} * C_{n}^{n}x^{n}，即\sum\limits_{i=0}^{n} C_{n}^{i} * C_{n}^{i} = C_{2n}^{n}

T3 回文

本来以为良心出题人又来了一题manacher，结果肝了半天只弄出来了40分的暴力（最后还打挂了）==
结果正解很神奇的是DP。似乎是区间DP的一种？咱不怎么写DP不是很清楚。
我们注意到n的大小只有3*10^{3}，而T则达到了10^{6}。显然，要做到O(1)或O(\log n)级别的查询。我们令p[i][j]表示[i,j]这个区间中包含的回文子串个数，令q[i][j]表示[i,j]这个区间是否为一个回文串。区间中包含的回文子串个数可以通过比[i,j]更短的区间来求得。可得状态转移方程为f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+q[i][j]。按长度枚举字符串中的每个子串预处理即可，时间复杂度为n^{2}。

The Nights

推了一晚上Summer Pockets的咱表示这作真的超有趣的！从系统到日常都很能吸引人！大概这就是Key社的真正实力吧。常常看到有人说Summer Pockets要么把Key社重新推回巅峰，要么让Key社就此沉沦。咱作为一个路人Gal玩家的话，对于本作还是很看好的。就算Summer Pockets无法把Key社重新推回巅峰，它也能重新塑造Key社有点丢失的形象，将Key带回人们的视野当中。
然后咱就BE了。对不起咱路转黑了Key社拜拜了您呐
于是咱不得不拔掉之前立的“不看攻略走完一条线”的flag……果然不行啊咱pup 在BE之前咱已经存了近50个档了估计不看攻略的话存档管理都能杀我……
然后就被剧透了一小点……真的只有一小点！不过温暖人心新岛夕的剧本不要剧透也能猜到大概长啥样就是了。
不管了反正明天开始推紬线，试试在回去前能不能推到ALKA叭。希望不会再高铁上推它推到哭吧……