北京八十中

北京八十中

---

---

Day1 PM

任何时刻非叶节点都形成了一个...一个什么来...？

gym 100962D
hdu 5891
bzoj 3499 3115 2803

---

Tests

Day2 tvt(倍增)

只要我们找到两条路径的公共路径，就可以通过判断他们相遇时是否在整点来得到答案了。
我们求$u1\to v1$路径上与$u2\to v2$相交的部分$S\to T$。令$w=LCA(u2,v2)$，发现如果$u1$在$w$的子树内，那么$S$就是$LCA(u1,u2)$与$LCA(u1,v2)$中深度较大的那个，否则$S$就是$w$。
同理，若$T$在$w$的子树内，则$T$是$LCA(v1,u2)$与$LCA(v1,v2)$中深度较大的那个，否则$T$是$w$。
然后可以算出从$u1,u2$到达公共路径（$u1$是$u1\to S$，$u2$则可能是$u2\to S$或$u2\to T$）上的时间$t1,t2$。
如果$u1,u2$在公共路径上行走时同向（即$u2$也离$S$更近一些），那么只需要判断$abs(t1-t2)$是否大于等于公共路径上的最大边，如果是则答案为$NO$，否则$YES$。
如果不同向，显然首先要满足$dis(S\to T)>abs(t1-t2)$。然后我们计算两人路过公共路径的时间中点，即$mid=\frac{dis(S\to T)+t1+t2}{2}$（若为奇数则显然不会在整点相遇）。令$w'=LCA(S,T)$，然后判一下在$mid$时刻是位于$S\to w'$还是$w'\to T$的路径上，然后在对应路径上倍增即可。

Day3 a

EC-Final E

Day3 c(思路 并查集)

https://www.bilibili.com/video/av38542305 A

边权只有$30$，这其实和边权为$1$是等价的。也就是去算边权为$1$的边用了多少条，边权为$2$的边用了多少条...设只考虑边权为$1$的边用了$x$条，只考虑边权为$1,2$的边一共用了$y$条，那么边权为$2$的边就用了$y-x$条。
其实可以这样算：枚举边权$w$，将所有边权$\leq w$的边加入图中，若成功加入了$t$条边（要构造一棵树，可以直接并查集维护），设当前图的点数为$n$，则边权$>w$的边一共用了$n-1-t$条。令它们贡献为$1$，即$Ans$+=$n-1-t$。
这样$w$从$0$枚举到$30$，那边权为$1$的边就会被算$1$次，边权为$2$的边会被算$2$次...每一次的贡献都是直接加$1$，不需要考虑边权。
对于当前要加入的边，我们维护一个大小为$2n$的并查集，计算每一层成功加入了多少条边。
对于最初的两层点，只需要并查集维护一下就可以了。考虑第二层与第三层点的连通性与前两层有什么不同，显然在之前连通的点现在还是能连通（加入的边都是一样的），区别就是，第二层的点之间可能在之前连通了。
所以我们可以保留之前的并查集，对于在第二层右侧连通的点对$u_i+n,v_i+n$，在第三层左侧加入一条边$u_i,v_i$。原本的边就不需要保留了。
同样在第三层继续加边$u,v$的时候会出现两种情况：$u,v$不连通，合并$u,v$；$u,v$已连通，这意味着和上一层相比我们可以少加一条边，令增量$s[i]$--。
同样对于在右侧连通的点对$u_i+n,v_i+n$，再在第四层左侧加入边$u_i,v_i$。
当做到某一层没有要加入的边时，答案就不会改变了。
所以我们就可以计算出每一层成功加入边数的增量的增量（即求一遍前缀和后我们可以得到每一层之间相差多少），这是个二阶差分，所以求两遍前缀和就可以得到每一层成功加入的边数了。
枚举边权$0\sim29$做$30$遍即可。
因为连通性至多改变$O(n)$次？所以复杂度是对的，为$O(30m\alpha(n))$。

Day5 yjqa(DP 线段树 单调栈)

$f[j]>t[i]$时，$f[i] = \min(\ f[j]+2\max(A[j+1...i])\ )$。
对于一段$\max(A[j+1...i])$相同的数，我们只需要保留最靠前的$j$（$f[j]$单增）。
可以直接用两个单调栈，如果一段数的$max(A[j+1...i])$相同，我们维护此时最靠前的$f[j]$。
有用的状态只有当前单调栈里的元素，所以二分满足$f[p]\leq t[i]$的位置$p$时，直接在存$f$值的单调栈里二分位置就可以了。
查询就维护一棵线段树，然后在单调栈里对应的区间查询。
复杂度$O(n\log n)$。

如果存在$i<j$且$A[i]\leq A[j]$，那么送$j$的时候也一定可以把$i$顺便送走。所以可以删掉这样的$i$，然后序列的$A[i]$就是单减，即$\max(a[j+1...i])=a[j+1]$，就可以直接单调队列维护了。
复杂度$O(n)$。

Day5 yjab(DP Splay)

https://www.cnblogs.com/Jessie-/p/10211995.html

Day7 yjqaa(数位DP)

https://ac.nowcoder.com/acm/contest/296/D
https://www.cnblogs.com/SovietPower/p/10227151.html

$x:\ 11010011$
$y:\ 10011110$
（下标是从高位往低位，依次是$1,2,...,n$）
比如对于这两个数，先找到最高的满足$x$是$0$，$y$是$1$的一位$j$，显然我们还要找比$i$高的最近的一位$i$，满足第$i$位$x$为$1$，$y$为$0$。
然后我们要将$x$中$i$之后的位上的$1$全变成$0$，然后$x$-=$1$，才能使得$x$在$j$这一位为$1$。这样$x$的第$i$位变为$0$，之后全变为$1$，显然此时还需要的代价就是 $n-i-\ y的后i位中1的个数$。
而之前的代价就是 $x后i位中1的个数$。再算上$i$及前$i$位的代价，记$cnt(x)$为$x$的二进制表示中$1$的个数，$x$变成$y$的总代价其实就是 $cnt(x)-cnt(y)+n-i$。
这样就可以数位DP了。
$f[i][las][0/1][0/1][0/1]$表示 当前考虑到第$i$位，最近的满足$x$是$1$，$y$是$0$的位是$las$，是否处于上界，是否$x$已经大于$y$（要保证$x\geq y$），是否已统计过答案（只在最高的那位$j$统计答案），此时的总答案。
同样还需要记$g[i][las][0/1][0/1][0/1]$表示方案数，用来统计答案。
转移时枚举$x,y$当前位填什么就行了。
状态数$O(n^2)$。代码在这儿。

---

也有$O(n)$的解法（我用记搜写了下，代码在这儿）：
orz $tangjz$的题解后，发现$las$这一维很容易就省去了...
原本记$las$是为了计算$n-i$这部分贡献，放到代码中就是$ans$+=$g*(n-i)$（$g$是方案数）。
现在我们只记是否出现过$i,j$（状态是三进制，分别表示未出现$i,j$、出现过$i$还没出现$j$、$i,j$都出现了），如果出现过$i$，转移的时候就$ans$+=$g$。
这样对于$i$，$g$的贡献还是会算$n-i$次。
这样复杂度就是$O(n)$了。

---

解释一下$tangjz$的代码。。
写的从低位往高位的递推，每次枚举当前要计算的位$i$，然后枚举$j,k$（$j$是上界，$k$是那个三进制），据此枚举（要满足这个状态）第$i$位$x,y$填$0$还是$1$。
因为是从低位往高位（要注意转移对状态），所以$k=2$是说还没有找到$v$；$k=1$是指找到了$v$但没有确定$u$；$k=0$是指$u,v$都已经确定了。
那么看转移，$j$这维和记搜写法是一样的...（其实哪一维和记搜都差不多）。
下面忽略$j$这一维，只考虑$k$。为了不混用，下面的$u,v$就是最上面$x$变成$y$这一过程中的$i,j$，代价还是$cnt[x]+cnt[y]+n-u$。
$k=0$，$f[i][0]$可以$f[i-1][0],f[i-1][1]$转移。但要从$f[i-1][1]$转移就是令第$i$位为$u$，也就是需满足$x=1,y=0$，此时既可以$f[i-1][0]$也可以从$f[i-1][1]$转移。
$k=1$，$f[i][1]$可以$f[i-1][1],f[i-1][2]$转移。同理要从$f[i-1][2]$转移就是令第$i$位为$v$，也就是要满足$x=0,y=1$，且此时只能从$f[i-1][2]$转移。
上面两个转移虽然形式像但是不同。
$k=2$，$f[i][2]$只能从$f[i-1][2]$转移。
当$k=1$或$2$时，也就是$u$还没出现，此时$ans$+=$g$，这样就能统计$n-u$这个答案了（后面n-u位中，算每位的时候答案都加上一个当前的方案数g'，合起来就是那个(n-u)*g）。

可能还会不懂...我再写一下：
假设有三位$1,2,3$，现在考虑第$1$位，本来是在这里加$(n-1)*g[2]$，$g[2]$是填$2$及后面的位的方案数，$g[2]$就等于$\sum g[3]$，所以$(n-1)=2，2*g[2]$就是$g[2]+\sum g[3]$。
所以你在$g[2]$统计一次，每个$g[3]$那统计一次，就是$g[2]+\sum g[3]=2*g[2]=(n-1)*g[2]$。
再扩展几位也是这样。

还不懂的话看代码吧...感觉说不太清楚啊QAQ

Day8 color(区间DP 贪心)

$1\ 2\ 3\ 3\ 2\ 1\ 4\ 4\ 5\ 6\ 6\ 5$
假设我们当前要处理的区间是上面这样的。那么我们要找出其中的所有极长颜色段，也就是$1...1,\ 4...4,\ 5...5$。因为在该区间中我们能染这三种颜色，剩下的只需要递归到每个极长区间内部去做就行了。
那我们现在要算怎么染这三段（$1...1,\ 4...4,\ 5...5$）颜色使得贡献最大。
把这三段颜色拿出来记为$1,2,3$，每一段的价值分别是这一段的长度。
令$f[i][j]$表示合并$i$到$j$段的最大贡献，答案就是$f[1][3]$。
合并显然就是个区间DP：$f[i][j]=\max\{f[i][k]+f[k+1][j]+sum_j-sum_{i-1}\}$，其中$sum$是价值的前缀和。这样复杂度是$O(m^3)$的。
容易想到每次染色一定是染左右两边的，所以实际不需要枚举中间点$k$，直接$f[i][j]=\max\{f[i+1][j],f[i][j-1]\}+sum_j-sum_{i-1}$就可以了。这样就是$O(m^2)$了。

Day8 path(期望 递推 Dijkstra)

令$f_i$表示从$i$出发到$n$期望最短时间，则

$$f_x=\frac{\sum f_v+m}{dgr_x}$$

在最优策略下，只有$v$能使$f_x$变小，$x$才会走到$v$。$dgr_x$也是指$x$会走到多少个$v$。
但是我们不知道是哪些$v$能转移到$x$，所以$Dijkstra$的时候判一下$v$是否能使$f_x$变小就可以了。
$Dijkstra$中当前出队的点的$f$肯定已经是更新完了。

Day9 aa

23:30 G

Day9 bb(后缀数组/后缀自动机 零和博弈)

https://www.bilibili.com/video/av38542305 44:28 J
https://www.cnblogs.com/SovietPower/p/10269997.html

$Description$
题面在这儿（或者去牛客 EC-Final J上看）。
简要题意：给定一个长为$n$的字符串，记$s_i$为从$i$开始的后缀。
两个人进行博弈，先手任意确定一个概率序列$p_i\geq0,\sum_{i=1}^np_i=1$。后手确定一个后缀$j$。先手想要最大化下式的值，后手想要最小化下式的值，两人按照最优策略决定，求最后下式的值：

$$\max_{\{p_i\}}\left(\min_{j=1}^n\left(\sum_{k=1}^np_k\mathbb{lcp}(s_k,s_j)\right)\right)$$

多组数据，$n\leq2\times10^5,\sum n\leq 5\times10^5$。

$Solution$
一个最大化一个最小化，可以看做先手的收益是$\sum_{k=1}^np_k\mathbb{lcp}(s_k,s_j)$，后手的收益是$-\sum_{k=1}^np_k\mathbb{lcp}(s_k,s_j)$，所以这就是一个零和博弈，答案会在纳什均衡点处取到。即第一个人选择一种混合策略，使得自己在最坏情况下收益最大，也就是对面不管怎么决策，收益都一样。
SAM：
大概就是找出后缀树上的后缀节点，然后令它们的收益相同，从而解出各个位置的$p$和收益。（然而我不知道用SAM怎么标记后缀节点QAQ）
复杂度$O(n)$。

（随便记的忽略下面这一段吧）
$p_1f_1=p_2f_2=p_3f_3,\quad p_1+p_2+p_3=1$
$pf_1=(1-p)f_2$
求出这个的$p$，然后令$f'=pf_1$，求$pf'=(1-p)f_3$，算出来的$1-p$就是原方程的$p_3$。

SA：
我们知道排名在$[l,r]$中的后缀的LCP是$\min\limits_{i=l+1}^r\{height_i\}$，设最小值的位置是$p$，如果当前的两个后缀$j,k$在$p$的两边，那么此时的LCP就是$height_p$；否则$j,k$在同侧，可以考虑递归到两边去做。
能够想到的是，局部最优决策下的概率比等于全局最优决策下的概率比。也就是说令左边子区间在最优决策下，各位置的概率比为$p_1:p_2:p_3...$，那么在于右区间合并，也就是在全局中，左区间各位置的概率比仍为$p_1:p_2:p_3...$。
这个结论不难证明，当$j,k$同在左区间中的时候，答案是和右区间无关的（否则$j,k$有一个在右区间的话，答案和$height_p$有关，等会再讨论）。
所以我们可以分治去做，最后合并左右两区间，也就是$j,k$在$p$的异侧的时候。
设左区间的答案为$L$，整体分到的概率是$x$，右区间的答案是$R$，整体分到的概率就是$1-x$。
假如后手选择$j$在左区间，那么$k$在右区间时先手的收益是$Lx+ht_p(1-x)$；$j$在右区间，收益就是$R(1-x)+ht_px$。
先手会令这两个式子相等，所以我们能解出$x$，然后代到左式或右式就能得到当前区间的答案了。
分治复杂度$O(n)$，建$SA$的复杂度$O(n\log n)$。

Day9 cc

54:30 K