最近好多题没补，慢慢来吧。包括一些开火车和一些$atcoder$，有一些题队友@yangdavid已经写过了，我就不用再浪费时间了。由于不是训练实录，有些水题就不写了
待补任务：
1.$opentrains1538GJ$啃$std$
opentrains 1483 E.Expected LCP
题目：有$n$个长度无穷的$0/1$串
$$
f_n=max_{i \ne j}{LCP(s_i,s_j)}
$$
求$f_n$的期望。
solution：
首先，我们可以确定一个$p\ge1$,使得存在一种方式使得$f_n<p$
这样的话，说明$f_n$至少是$p-1$先把这部分加上去
考虑，$P(i)=P(f_n=i)=\frac{A^n_{2^{i+1}}}{2^{(i+1)n}}-\frac{A^n_{2^{i}}}{2^{in}}$，设$b_i=\frac{A^n_{2^{i}}}{2^{in}}$
$$
E(f_n)=contribution(p-1)+\sum_{i=p}^{\infty}i(b_{i+1}-b_i)=contribution(p-1)-ib_i-\sum_{i={p+1}}^{\infty}b_i
$$
考虑如何计算$\sum_{i={p+1}}^{\infty}b_i$，设$x_i=2^i$
$$
b_i=\frac{\prod_{j=0}^{n-1}x_i-j}{x_i^n}=F(\frac{1}{x_i})
$$
其中$F(x)=\sum_{i=0}^na_ix^i$是一个$n$次多项式
对于每一个$i$，$B_i=\sum_{j=p+1}^{\infty}a_i\frac{1}{x_j^i}$都是一个无穷等比数列求和形式，将每个$B_i$都求出来，则$\sum_{i={p+1}}^{\infty}b_i=\sum_{i=0}^nB_i$。由于$n$有限，因此是对的
启示：当遇到难以处理的数列求和时，可考虑把数列看成多项式形式，对每一项分别求和
opentrains 1538 I.Modulo-magic squares
有一个$n^2$的矩阵，矩阵元素是$[0,m-1]$,求有多少个合法矩阵，满足每一行、每一列、主对角线、副对角线的元素和在模$m$意义下都是一个常数$C$？
$solution$:考虑有多少个自由元，然后答案就是$m^{自由元个数}$
自由元个数：$1(选择C)+(n-1)(n-2)(随意选择前n-2行的前n-1列的每个数字)+(n-3)(选择倒数第二行的除第一列、最后一列、第三列的所有元素)=n^2-2n$
这样，我们用第二项中的$n^2-3n+2$个自由元确定了前$(n-2)$行，用倒数第二行的第二列和倒数第二列两个自由元确定了主副对角线和第一、二、倒数第一、倒数第二列。然后我们用倒数第二行的其他自由元确定了倒数第二行和其他所有的列，至于倒数第一行，由于我们已经确保所有列和其他所有行成立，用二次求和法对矩阵所有元素求和即可证倒数第一行也成立
$ans=m^{n^2-2n}$
以上构造方法对$n\ge5$均成立
手推可知对$n\leq3$也成立
对于$n=4$,我们发现，倒数第二行倒数第二列的取值满足一个可写为$2x=K(mod\ m)$的方程。在$m$为奇数时，取$2$的逆元则有唯一解，这时满足上述公式，但在$m$为偶数时，若$K$为偶数则有两个解否则没有解，打表或经过超高校级麻烦的分类讨论可以发现，$K$不可能为奇数。因此，唯一的特例是，当$n=4,2|m$时：
$ans=2m^{n^2-2n}$
Atcoder AGC010
非常棒的一场，三道操作题三道博弈论，很自闭但真的很有趣，由于官方题解很详细了就不再赘述。
opentrains1519
A.线段树优化建图+强连通分量，B.签到，D.递归优化 F.二维数点 G.最小圆覆盖 H.状压 见@yangdavid博客，不再重新叙述
其中$H$是一道不错的状压
K.Knapsack
这时$Claris$讲课时说的那个随机凸包期望$logn$的随机背包神题，由于也不知道证明，也不是很了解，就不细讲，听$Claris$课即可
I.Statistics
给出 $n≤5000$个物品，第 $i$个物品的体积为$v_i$ ，求所有体积和恰为$1≤V≤5000$且物品数量最小的集合中，最小的平均体积，最小的中位数（偶数的中位数是中间靠左的一个），最小的众数个数，最小的极差
下面我们一个一个说：
首先我们得做一遍普通背包得知体积恰为$V$最少多少个物品，设为$m$个
平均值：直接算，$O(1)$
中位数：
算法一：做前缀背包和后缀背包并枚举中位数，检查是否合法时枚举集合种比中位数小的背包体积和，复杂度$nV$,常数为$3$
算法二：二分中位数，把每个物品价值变成$inf+(-1)^{[v_i<mid]}$，做体积固定价值最小的背包，若结果大于$m·mid$则当前中位数过小，否则过大。此方法虽然多一个$log$，但巧妙地通过$inf$把物品数量最小的限制转化掉了，感觉挺有启发
众数：
算法一：二分答案然后做背包，复杂度$O(nVlogn)$
算法二：从小到达枚举众数，每次把可以增加的物品加入背包，复杂度$O(nV)$
极差：
极差是这道题目的精华，两个算法都很有启发性
算法一：将物品按照$v_i$排序后，考虑滑动窗口，滑动窗口里是要满足存在一个大小为$m$的子集使得体积和为$V$,我们现在这样支持添加物品和删除物品：维护两个栈，栈的每个元素都是一个长度为$V$的代表背包的数组，共需要$V^2$空间，当我们加入一个物品时，直接加在$A$栈栈顶，用原来$A$栈栈顶的背包更新构成新栈顶，如果我们要删除一个物品（这个物品是当前区间的第一位），这时如果栈$B$不为空，说明要删除的东西是栈$B$栈顶，那么直接将栈$B$的栈顶弹出即可，如果栈$B$是空的，说明要删除的物品是栈底，这时，我们将$A$除了栈底以外的元素一个个弹出，并按照弹出的顺序一个个加入栈$B$并做背包即可。
我们发现，栈$A$从顶到底元素的$v_i$减小，栈$B$从底到顶元素的$v_i$减小
要查询整个背包某一项，直接合并$A、B$栈顶所代表的背包即可，合并一次复杂度$O(V)$
势能分析可得这样做维护两个栈背包的时间是$O(nV)$
以上方法可以处理所有滑动窗口背包、$n$次查询背包某一个值的问题
算法二：按照$v_i$从小到大加入背包，把物品价值设为$inf-v_i$(更新$dp[v_i]$时)，$inf$（其他时候），枚举最大值直接查询即可，不得不说这个方法也很棒。
总复杂度$O(nV)$
C.Flip a coin
有两个人，他们分别拥有 $0/1$ 串$s$ 和$t$。现在不停地掷一枚均匀的硬币，正面为 $1$，反面为 $0$。如果某一时刻硬币组成的串中包含 $s$，那么第一个人赢；如果包含 $t$，那么第二个人赢；如果同时包含$s,t$，那么平局。问这三种情况的概率。
字符串长度小于$50$
$solution$:游戏不停止$0/1$串就会不停写下去
算法一：我们设一个零一串$S$的“产生价值”为$f(S)=2^{-|S|}$
求出两个串的前缀$border$数组
我们设$dp[i][j]$表示所有内部不包括$s/t$为子串，且$s、t$的后缀$KMP$状态分别是$i,j$的$0/1$串的价值和
然后我们做高斯消元即可，复杂度$O(n^6)$
算法二：跟上一个算法一样，不过这次，我们建出$s、t$的$AC$自动机，我们的$dp$状态是：所有$s/t$都没有出现过，且后缀状态在$AC$自动机的特定节点上的字符串的价值和，也是一样的高斯消元，只是这次的复杂度为$O((n+m)^3)$
算法三：这道题原题是让输出小数，因此我们怕高斯消元精度不够，这时我们还是考虑$n+m$个$AC$自动机的状态，用他们之间的转移构造出矩阵，跑一个非常大的矩阵快速幂来逼近精确值即可（可理解为串是有限长的，但长度非常长）。复杂度$O((n+m)^3log10^{18})$
E.Tree Paths
一个点的点权就是它的编号，求一棵树上有多少条路径使得$max-min=len$
$n\leq10^5$
考虑点分治，每次计数经过分治中心的路径，在每个点分数中$dfs$，求出每个点$x$到分治中心的路径上的$max,min,len$，然后，我们考虑，对这个分治中心的每个儿子的子树里的点维护一个树状数组，对这棵分治树里的所有点维护一个树状数组，这些树状数组以某种需要的值为下标，记录满足该值的元素的数量。在这里，每条我们要考虑的树链都是由两条来自不同子树的树链拼合而成的（要经过分治中心）。为了满足来自不同子树的性质，我们只需要用在全局树状数组中查询的结果，减去在当前子树代表的树状数组中查询的结果，便是合法的结果。以下我们仅叙述要怎么在某个数据结构中查询合法的数量。
我们首先考虑$max$和$min$都处在两条树链中某一条上的情况数，考虑枚举这条又有$max$又有$min$的链，首先他得满足$max-min=len$，我们称这样的链为合法链,这样，我们按照$min$从大到小考虑每个点，如果这个点代表的链是合法链，我们就考虑有多条链$v$，满足$max_v<max$,因此在这里我们的树状数组的下标应为$max$，这一步等价于一个离线二维数点的过程
接下来我们考虑$max$和$min$分别咋链$a,b$上，这样我们就有$max_a-len_a=min_b+len_b$,这样，我们对每条链就有两个属性$f(a)=max_a-len_a,g(a)=min_a+len+a$，我们把每条链的两个属性看成是两个链，分别是一类链和二类链，我们把所有的$2n$个链按照权值排序，由于每个合法的组合都是两个权值相同的、一个一类一个二类两条链组成，我们按照权值一批一批考虑，在每一批中我们都按照$min$从小到大考虑，每枚举到一个一类链，我们去树状数组中查询$max_v<max$的二类链的数量，这样就做完了。
回顾这个解法：首先，我们用全局树状数组和分子树树状数组保证了来自不同子树这一限制，从而使我们可以随意决定枚举点的顺序，其次，在第一步中，二维数点思维含量不高，第二步中，我们首先用权值限制了所需等式，又用按照$min$从小到大枚举这一顺序限制了$min$的大小关系，这样就只有$max$的大小关系需要使用数据结构维护。我们将$1.不同子树 2.min 3.max 4.max-min=len$四个限制最终化简到只需考虑一个限制
复杂度$O(nlog^2n)$
以上为口胡，这次是个例外，代码完成后会将代码给出。
J.Zigzag
求两个数列的最长公共波浪子序列。
数据范围：$n,m\leq5000$
这题一点都不难，第一次听题的时候yd讲错题意了（要不就是我自己听错了）
$O(nm)$的$dp$,方法跟进阶指南傻逼题$LCIS$(最长公共上升子序列)一毛一样
关于一类区间mex问题
现要进行如下操作：
$1.$插入/删除一个数
$2.$询问当前数字集合的$mex$
$solution$:我们考虑，假设操作$n$次，那只有$[0,n-1]$的值有用。现在考虑对值域分块，维护每个数字在集合中有几个，每个块有没有满，那么，就可以做到插入/删除$O(1)$，询问一次$O(\sqrt n)$的复杂度
在区间$mex$问题中，我们考虑先对询问用莫队，那么取块大小$k=\frac{n}{\sqrt m}$最优，相当于有$O(n\sqrt m)$次一类操作，$O(m)$次二类操作，复杂度$O(n\sqrt m+m\sqrt n)$
对于树链$mex$，相当于在欧拉序上跑区间$mex$问题
opentrains1505/1491/1483
历史遗留问题：
opentrains1538J Count the sequences
给定四个数$n,b,c,m$求有多少个长度为$m$的整数数列${x}$满足：
$0\leq x_i\leq b^i-c$
$\sum_{i=1}^mx_i\leq n$
数据范围：
$1\leq m\leq 50,2\leq b\leq10^9,-b+2\leq c\leq b-1,n\leq b^{m+1}$
不是很会，大概有一个补集转化数位$dp$的想法，有时间再啃代码：
1 |
|
opentrains1538G String transformation
给定一个长度为$10^5$的字符串，你可以随意操作，每次操作可以选择一个字母让他上一位，如$A->a,e->F,z->A$
问能否使得一番操作后字符串总共刚好有$k$个洞。（如$B$有两个洞，$p$有一个洞，$F$没有洞）
这题貌似分了好久种情况，代码也特别长，有时间啃啃
1 |
|