算法原理 首先将 s 处理为 #a#b#c#b#a# 的形式，方便同时统计长度为奇数或偶数的回文串。 设 d[i] 表示以 s_i 为对称中心所能扩展出的回文串个数，而manacher可以在线性时间内求出 d[1]\do…

Luogu P3369 【模板】普通平衡树 #include <iostream> #include <stdio.h> #include <string.h> #define MAX_N 100005…

传送门：Gym 102341 A - Alakazam 对于shuffle操作，相当于将区间 [l,r] 内的所有值设置成该区间的平均值，每次询问即为单点查值，线段树维护即可。 C - Cloyster 首先由题目条件「…

传送门：Gym 102501 A - Environment-Friendly Travel 首先对于两个车站，如果它们之间有边，由于距离相同，显然只保留单位排放量最小的交通方式。设 f[i][j] 表示走到车站 i，已…

D - equation 求出所有使绝对值号内表达式变号的 x 分界点并排序，然后对于分成的若干个区间去绝对值号解方程即可。 E - permutation 1 由于 K 较小，当 N 较大时，差值序列字典序第 K 小的…

A - A + B = C 首先去除 a,b,c 的后导零并记录个数，最后在答案中算上即可，所以下面讨论的均为 a,b,c 个位不为0的情况。显然 x,y,z 均不为0的解一定可以转化为其中至少有一个为0的解，所以我们只…

I - Calabash and Landlord 显然可以分类讨论两个矩形的位置关系，但是很蠢（指比赛时候的我......）。可以将所有坐标离散化在 [0,4]\times [0,4] 的区域内，然后打标记并dfs即可…

E - Welcome Party 先将所有同学按照 x 升序排序，枚举 x_i 为当前选唱歌的同学的 x 的最大值，则同学 i+1\dots n 必须选脱口秀，此外前 i-1 个同学可以任意选择。设 y_{\max}=…

B - Blow up the city DAG上的支配树板题。建立超级点 S，将所有指挥城市向 S 连一条边，则原题转化成了：从 S 出发，有多少个点为到达 a 或 b 的必经点（除 S 之外）。以 S 为根并根据反向…

J - Just Skip The Problem 签到题。每一次询问最多只能获得一位的信息，有询问次数下界为 n，可构造询问：第 i 个询问为 y_i=000\dots010\dots000（只有第 i 位为1），显然…