また あした TVアニメ「魔法少女まどか☆マギカ」キャラクターソング 作詞：hanawaya 作曲：hanawaya 編曲：流歌、田口智則 歌：鹿目まどか(CV:悠木碧) 「それじゃ　またね」って手を振って 向你挥挥手「那么就再见了」 無理に笑って　さみしくなって… 勉强露出了笑容　内心却开始寂寞 歩道橋　自転車抱えて登る人 天桥上推着自行车前进的人 コンビニ　誰かのウワサ話 便利店旁人们的闲语 交差点　信号 十字路口的信号灯 遠くのクラクション 远处汽车的鸣笛声 知らない誰かの笑い合う声 不知是谁的欢言笑语 今日はひとりで歩く　通い慣れた街 今天虽独自在走在熟悉的街...

题目链接 给定一个字符串，可以选择两个字符将其交换一次，求交换后的最长回文子串。 和Manacher一样的套路，因为回文串分奇数/偶数长度，所以把串扩充为$#1#2#3#…#$的形式来避免这种讨论。 求出一每个字符为中心的最长回文子串的最大长度后，考虑第一个不匹配的位置，左右两边分别记为$L , R$，此外再求出如果这一位也匹配了，得到的回文子串的长度。 这样一共就分三种情况。 从串的两端选择一个$L$或$R$与对应位置交换。匹配两段。 如果串长为奇数且中心字符是$L , R$之一，与其交换，匹配两段。 如果第二次得到的不匹配位置的字符为$R , L$，与第一次不匹配位置交换恰好让它都匹配上，这样就能匹配三段。 再举一些例子 $acbab$、是以$c...

题目链接 给定一棵无根树，边权都为1，每次询问给定三个点，求这三个点各控制了多少个点。 点A被点B控制当且仅当点A到其他点的的距离都小于点A到点B的距离。 这道题可以是一道大讨论题，但感觉很容易讨论错且找不到问题。所以想了一些更完备优美的做法。 三个点$x , y , z$确定以后，明显对于大部分点都是没有意义的，有意义的只有$x , y , z$之间的$LCA$，即最近公共祖先。为了避免麻烦，我将$x , y , z$间路径的中点也列入关键点，这个中点有可能有两个。 这样对于一个询问，就能把树简化为一个至多12个点的结构。利用树的dfs序列可以实现线性复杂度建树，当然这里暴力建树也没问题。 现在再考虑其他点，这些点分为两类，一部分点会附加到某个关键点上，另一部分点会附加到...

题目链接 很早之前训练过的一套ASC题，难度相对来说还可以接受。 A. Bike Roads 平面上有两个圆形跑道，在圆上走比其他走法速度快，求两个圆上各一点间的最短路 离开第一个圆以及到达第二个圆的位置确定后，代价也确定了。答案单峰性质不是非常明显，但还是能以分段三分套三分的方法得到正确的结果。 B. Diversion 一个国家是一个n个点m条边构成的无向图，边分黑白两种，白边有$ n-1 $条并构成一棵生成树。现在可以拆除一条黑边一条白边，求让图不连通的方案总数，保证图中没有桥。 每条黑边能覆盖一整条链，找出所有只被一条黑边覆盖的白边即可。 C. Hex 一个在六边形网格上博弈的问题。 D. Monotone Gray Code 设计一种奇怪的格雷码。 E.Nic...

一套质量非常棒的题目，不拿来训练实在可惜。整体难度不是很大，但简单题比较少。 题目链接 A. Balanced Number 每个Balanced Number实际上只会有一个支点。 于是就可以愉快地枚举一下支点，再进行常规的数位DP， B. Battle over Cities （坑） C. Binary Number 最简单的题，直接枚举。 D. Detector Placement 模拟一条光线进入三棱镜折射的过程。 也是直接模拟，但要考虑很多细节，比较麻烦。 注意光线进入了棱镜不一定能出来，可能发生全反射。 E. Double Maze 比较简单且有趣的BFS题，需要一定的代码量。 输出要求字典序最小，BFS时注意枚举的顺序。 F. Error Curve...

题目链接 A. Wow! Such Doge! 统计输入文本里面有多少只Doge，直接暴力统计即可。 B. Wow! Such Conquering! 搜索，变种的TSP问题，先对原图进行一次Floyd。 有两个比较重要的剪枝： 如果当前存在一个没有走过的点，直接走过去也会超过Deadline，剪。 如果当前搜到的时间和已经大于答案，剪。 有了这两个剪枝，这道题就可以通过了。 C. Wow! Such City! 很基础的最短路，直接Dijkstra即可。 D. Wow! Such String! 如果把三个连续的字符看成一个节点，原问题可以转化为求26^3个节点的欧拉路径问题。比如aaa后面加一个b，就相当于从aaa节点往aab节点连一条边。 注意n如果大...