二轮前水题记
5.4
洛谷P4607 [SDOI2018]反回文串
神仙反演Orzzzzzzzzzz
首先一个串的本质不同的轮换个数是不重叠最小循环节的长度
如果最小循环节的长度(d)是偶数，此时一个回文串的(d)种不同的轮换字符串当中恰好有两个回文串(本身一个，把前(frac{d}{2})个字符拼到后面一个)
否则(d)是奇数的话一定会有(d)个本质不同的字符串
首先考虑字符集为(k)的情况下回文串的数量(g(n))
显然(g(n) = k^{lfloorfrac{n+1}{2} floor})(固定一半)
那么设
设(f(i))表示最小循环节为(i)的字符串数量，显然有
(Ans(n) = sum_{d|n} h(d) f(d))
(f(d))很难直接求，但是我们可以枚举循环节得到一个等式
反演一下
带入原来的公式
我们尝试枚举(g)
把(d)拆为(d = d' * K)，我们去枚举新的(d')
之前我们发现(h)函数有比较好的性质，这里似乎可以直接把(d)提出来。分析一下不难发现，只有当(d)是偶数且(k)是奇数是不能直接提。因为一个奇数不会有偶数因子，那么(frac{n}{k})一定是偶数
此时把式子中的(k)提出来，考虑一下(ksum_{d|frac{n}{k}} h(d)mu(d))的值，打一下表可以发现值总是(0)，因为(2)这个因子使得(mu)为(pm 1)的项消掉了
那么在计算这时候直接把这种情况判掉就可以
原式变为
然后直接对(n)进行Pollard-Rho分解，分解的同时可以求出后面的值，拿个map存一下。
然后dfs枚举约数直接算就行了
复杂度玄学，但是出题人把(n)出到(10^{18})也只能这么干。。
5.3
洛谷P4606 [SDOI2018]战略游戏
首先建出圆方树，那么答案为包含所有询问点的最小联通块大小 减去关键点个数
最小联通块大小可以转化为边的贡献最后特判LCA，将所有点按dfs序排序后算出相邻两点的dis，最后/2即可
复杂度(O(n log n))
5.2
洛谷P4620 [SDOI2018]荣誉称号
每个位置(x)向(frac{x}{2})连边最终会得到一棵完全二叉树
题目转化为：给出一个有点权的树，对于每个点可以花费(b_i)的代价使点权增加(1)，问使得所有长度为(k + 1)的链的点权和(\% M)均为(0)的最小花费
首先考虑序列的情况，稍加归纳后不难得到(a_i equiv a_{i + K + 1} pmod M)
放到树上话那么最终一个点的权值一定和它的(K+1)级祖先相同，因此对于前(2^{k})个点，我们(O(nm))预处理出(w[x][y])表示(x)的点为(y)时，所有能被它限制的点的代价
现在只需要考虑前(2^{k+1}-1)个点，首先把标号(< 2^k)的叶子节点删掉，对于剩下的点的限制条件变为所有叶子节点到根的路径和(\% M =0)。那么设(f[i][j])表示以(i)为根的子树，到所有叶子节点的权值(\%M = j)的最小代价，转移的时候暴力枚举该点的取值。
复杂度(O(nm + 2^k m^2))可以拿到70分
考虑(w)的预处理，std在这里用了一个等差数列，实际上不用这么麻烦，因为(a[i])取值只有(200)，直接对值域暴力就行
复杂度(O(n + 2^k m^2))
4.26
BZOJ4145: [AMPPZ2014]The Prices
f[sta][i]表示买完sta中集合中的物品，当前在i号城市的最小代价
转移的时候枚举一下最后买的物品以及从哪儿买
前缀和优化一下
复杂度O(n2^mm)
cf 1129 E. Legendary Tree
每次可以给定两个不相交且非空的点集以及一个常数({S}, {T}, p)，系统会返回(u∈S, v∈T)且(u, v)经过p的点的对数。
需要在11111次操作后还原出树的形态
n <= 500
首先转化为有根树，假设1是根。根据题目描述我们实际上得到了几个操作
1.询问点集S中有多少在p的子树内 - ({S}, {1}, p)即可
2.询问某个点p的子树大小 - {{2, 3, 4, 5}, {1}, p}
接下来考虑怎么还原出一棵树，显然我们只要维护出父子关系就行了
首先询问出所有点的siz，从小到大排序，那么此时每个点的孩子一定在它左边。接下来动态的从做往右扫，实时维护一下没有找到父亲的所有节点。
然后直接在点集中二分就行了。
UOJ #311. 【UNR #2】积劳成疾
每个长度为k的区间都是独立的，所以我们直接对着最大值dp
f[i][j]表示长度为i的序列，最大值为<=j时 的所有答案，也就是对整体进行dp
转移的时候只需要考虑第一个j在哪儿，其余的可以通过f[i][j - 1]转移
icpc 2018 焦作 I
给出数轴上(n)个点，要求选出(k)个点，最大化两两的距离，对于所有的(k=1, 2, 3, dots n)都要输出答案
有点小神仙，推出来感觉还是很有成就感的qwq
手玩一下不难得到最优策略：
偶数往两边放，同时维护任意对称点之间的距离
奇数往没放过的点放，往哪里放的贡献都是一样的，是上一次偶数放的两个点之间的距离
CometOJ#2 C
枚举独立集的大小是多少。那么最终答案是$sum_{i=1}^n C_{n}^i * (frac{x}{y})^{frac{i(i-1)}{2}}
4.29
cf618 F. Double Knapsack
一个很强的限制条件是(a_i, b_i <= N)
我们首先求出两个序列的前缀和，记为(sa, sb)
同时对于所有的(i)，找到最大的(0 <= sa[i] - sb[j] < N)的最大的(j)，记新的数组为(d_i)
显然(d_i)的取值最多有(n)个，但是由于是前缀和，因此(sa[0])也会有贡献(这个回路有点奇葩，看到下面就理解了)
也就是说(n)个位置，有(n+1)个取值，一定有一对是相同的
换句话说一定可以找到(sa_i - sb_{j} = sa_{i'} - sb_{j'})，移一下项有(sa_i - sa_{i'} =sb_{j} - sb_{j'})
因此我们求出(d)数组即可
loj#3083. 「GXOI / GZOI2019」与或和
单调栈入门题。
首先二进制拆分一下则我们只需要统计每一位的贡献。
第一问相当于求有多少矩形全为1
第二问相当于求有多少矩阵至少有一个1，相当于总数-全是0，取反之后相当于求多与少矩阵全为1，和第一问是一样的。
然后直接单调栈n^2
loj#2952. 「NOIP2018」赛道修建
傻逼贪心
首先二分一个答案
然后从从底向上合并，check的时候只需要判断是否能合成长度>=mid的链
4.30
洛谷P4559 [JSOI2018]列队
主席树板子题
每次需要在主席树上二分一个mid，满足(mid - K + 1 = num[1 - mid])，然后xjb搞一搞
mmp写的代码一开O2就RE。本机一点问题都没有，不调了。。
loj#6253. 「CodePlus 2017 11 月赛」Yazid 的新生舞会
这题淦了我一下午，，不过还好最后淦出来了qwq
考虑每个数的贡献，显然每个区间[l, r]最多被统计一次
设当前数为x, 那么[l, r]能产生贡献当且仅当(2sum_{l, r} > r - l + 1)
求个前缀和也就是(2s_r - r > 2s_{l - 1} + {l - 1})
然后相当于每次加公差为1的等差数列，线段树维护一下就好了