算法原理 首先将 s 处理为 #a#b#c#b#a# 的形式,方便同时统计长度为奇数或偶数的回文串。 设 d[i] 表示以 s_i 为对称中心所能扩展出的回文串个数,而manacher可以在线性时间内求出 d[1]\do…
【XJTU 2020暑期集训】Day18 - 2019 XX Open Cup GP of Warsaw
传送门:Gym 102341 A - Alakazam 对于shuffle操作,相当于将区间 [l,r] 内的所有值设置成该区间的平均值,每次询问即为单点查值,线段树维护即可。 B - Bulbasaur 咕 C - C…
【XJTU 2020暑期集训】Day17 - 2019-2020 ICPC Southwestern European Regional Programming Contest
传送门:Gym 102501 A - Environment-Friendly Travel 首先对于两个车站,如果它们之间有边,由于距离相同,显然只保留单位排放量最小的交通方式。设 f[i][j] 表示走到车站 i,已…
【XJTU 2020暑期集训】Day16 - 2019 Multi-University Training Contest 5
A - fraction 咕 B - three arrays 咕 C - geometric problem 咕 D - equation 求出所有使绝对值号内表达式变号的 x 分界点并排序,然后对于分成的若干个区间去…
【XJTU 2020暑期集训】Day15 - 2019 Multi-University Training Contest 7
A - A + B = C 首先去除 a,b,c 的后导零并记录个数,最后在答案中算上即可,所以下面讨论的均为 a,b,c 个位不为0的情况。显然 x,y,z 均不为0的解一定可以转化为其中至少有一个为0的解,所以我们只…
【XJTU 2020暑期集训】Day14 - 2019 Multi-University Training Contest 8
A - Acesrc and Cube Hypernet 咕 B - Acesrc and Girlfriend 咕 C - Acesrc and Good Numbers 咕 D - Acesrc and Huntin…
【XJTU 2020暑期集训】Day13 - 2019 Multi-University Training Contest 10
A - Minimum Spanning Trees 咕 B - Line Graphs 咕 C - Valentine's Day 咕 D - Play Games with Rounddog 咕 E - Welcom…
【XJTU 2020暑期集训】Day12 - 2019 杭电多校训练第3场
A - Azshara's deep sea 咕 B - Blow up the city DAG上的支配树板题。建立超级点 S,将所有指挥城市向 S 连一条边,则原题转化成了:从 S 出发,有多少个点为到达 a 或 b…
【XJTU 2020暑期集训】Day11 - 2019 杭电多校训练第2场
A - Another Chess Problem 咕 B - Beauty Of Unimodal Sequence 咕 C - Coefficient 咕 D - Double Tree 咕 E - Everythi…