转载注明地址：https://www.cnblogs.com/syc233/p/13771723.html

前言

没有前言 其实是咕咕咕了 。

P6835 [Cnoi2020]线形生物

题面

题解

月赛时没做出来的题，下来看了题解才会。

令从 \(x\) 走到 \(y\) 的期望步数为 \(E_{x\to y}\) ，\(x\) 的返祖边集合为 \(S_x\) ，\(S_x\) 的大小为 \(deg_x\) ，则：

\[\begin{aligned} E_{x\to x+1}&=\frac{1}{deg_x+1}\times 1+\frac{1}{deg_x+1}\sum_{(x,y)\in S_x}(E_{y\to x+1}+1)\\ &=1+\frac{1}{deg_x+1}\sum_{(x,y)\in S_x}\sum_{i=y}^xE_{i\to i+1}\\ \end{aligned} \]

令 \(sum_x=\sum_{i=1}^xE_{i\to i+1}\) ，则：

\[\begin{aligned} E_{x\to x+1}&=1+\frac{1}{deg_x+1}\sum_{(x,y)\in S_x}(sum_x-sum_{y-1})\\ &=1+\frac{1}{deg_x+1}\sum_{(x,y)\in S_x}(sum_{x-1}-sum_{y-1})+E_{x\to x+1}\\ \end{aligned} \]

为了让 \(E_{x\to x+1}\) 能通过递推求出，将等式右边与 \(E_{x\to x+1}\) 有关的项移到左边去，并且消去分母：

\[\begin{aligned} E_{x\to x+1}&=1+deg_x+\sum_{(x,y)\in S_x}(sum_{x-1}-sum_{y-1})\\ \end{aligned} \]

然后记录个前缀和就好了。

P3899 [湖南集训]谈笑风生

题面

题解

对 \(b\) 的位置分类讨论：

  • 若 \(b\) 在 \(a\) 上方，这种情况对答案的贡献为 \(min(dep_a-1,k)\times (size_a-1)\) 。
  • 若 \(b\) 在 \(a\) 下方，则答案为 \(a\) 的子树中与 \(a\) 相距不超过 \(k\) 的结点的子树大小减一的和，线段树合并即可。

P5384 [Cnoi2019]雪松果树

题面

题解

求 \(k-cousin\) 个数可以转化为求 \(k-father\) 的 \(k-son\) 个数。

将询问离线，线段树合并即可。

用到一堆奇技淫巧可以让线段树合并的空间复杂度降到 \(O(n)\) 。

P2050 [NOI2012]美食节

题面

题解

P2053 [SCOI2007]修车 的加强版。

直接连一个完全二分图显然边数爆炸，所以得动态加点。

若一个厨师在上一轮增广中做了菜，那么给这个厨师新增一个结点。

这样能避免添加很多无用结点，总结点数与总人数同阶。

CF280D k-Maximum Subsequence Sum

题面

题解

贪心思想，选取不超过 \(k\) 段不相交的子段使子段和最大，那么一定在子段和最大到前 \(k\) 大的子段中选。

模拟费用流。

对于所有 \(i\in[1,n]\) ，连边 \(i\to i+1\) ，容量为 \(1\) ，费用为 \(a_i\) 。

建立源点 \(s\) 和汇点 \(t\) 。从 \(s\) 向结点 \(i\in[1,n+1]\) 分别连一条容量为 \(1\) ，费用为 \(0\) 的边；分别从结点 \(i\in[1,n+1]\) 向 \(t\) 连一条容量为 \(1\) ，费用为 \(0\) 的边。这样一单位流经 \(s\to i\to j\to t\) 的流代表选取了区间 \([i,j-1]\) 。

为了使子段和最大，每次跑最大费用流且只推送一单位的容量，直到推送了 \(k\) 个单位的容量，或者费用为负数，停止增广。结合上面的贪心思想可知这样做是对的。

注意到每次跑费用流的过程中，一单位流经 \(s\to i\to j\to t\) 的流会将区间 \([i,j-1]\) 取相反数，那么可以用线段树模拟这个过程。

线段树维护区间最大子段和和子段和最大的子段的左右端点，和区间最小子段和和子段和最小的子段的左右端点用于取相反数的操作。

P4843 清理雪道

题面

题解

有源汇上下界最小流。

每条边都得经过至少一次，且能在任何一个点放下一个人，在任何一个点结束。

连边 \(s\to i,i\in[1,n]\) ，容量上界为 \(+\infin\) ，下界为 \(0\) 。

连边 \(i\to t,i\in[1,n]\) ，容量上界为 \(+\infin\) ，下界为 \(0\) 。

对于原图中的边 \(u\to v\) ，连边 \(u\to v\) ，容量上界为 \(+\infin\) ，下界为 \(1\) 。

跑有源汇上下界最小流。

至于有源汇上下界最小流怎么跑，先不连边 \(t\to s\) ，跑一遍可行流，尽量填充非必须流，在连上 \(t\to s\) 增广，最后边 \(t\to s\) 中的流量即为最小流。

P3119 [USACO15JAN]Grass Cownoisseur G

题面

题解

容易发现，若逆行的边的起点和终点在同一个强连通分量中，则对答案没有影响。

于是先缩点，跑出起点为 \(s\) 所在的强连通分量和终点为 \(s\) 所在的强连通分量的最长路，枚举逆行的边。

CF547E Mike and Friends

题面

题解

将所有字符串插入AC自动机中，建出fail树。

那么问题就转化为：询问 \(s_k\) 在AC自动机上的结束结点的子树中，有多少结点属于 \(s_{l \cdots r}\) （即插入Trie时经过的结点）。

线段树合并即可。

SP1811 LCS - Longest Common Substring

题面

题解

对第一个串建SAM，用类似AC自动机上匹配的方法让第二个串在SAM上匹配。

令当前匹配到的结点编号为 \(u\) ，以 \(u\) 结尾的最长匹配长度为 \(now\) ，初始时 \(u=1,now=0\) 。

设当前加入的字符为 \(c\) ，则：

  • 若 \(u\) 有 \(c\) 对应的出边，则 \(u\) 跳到对应出边到达的结点，匹配长度 \(now\) 加一。
  • 若 \(u\) 没有 \(c\) 对应的出边，则从 \(u\) 沿着parent树向上跳，直到第一个有 \(c\) 对应出边的结点 \(u'\)：
    • 若不存在 \(u'\) ，则令 \(u=1,now=0\) ，重新开始匹配。
    • 因为 \(u'\) 对应的等价类中的子串一定是 \(u\) 中对应等价类中子串的后缀，所以 \(u'\) 结点处的最长匹配长度即为 \(len(u')\) 。在 \(u'\) 类中的最长串后加入一个字符 \(c\) ，令 \(now=len(u')+1\)，\(u\) 跳到 \(u'\) 的 \(c\) 对应出边到达的结点。

每次跳到一个结点时更新最长公共子串长度即可。

SP1812 LCS2 - Longest Common Substring II

题面

题解

上面那题的加强版，依然采用上题的方法。

先对第一个串建SAM，然后让其他串在SAM上匹配。

这道题和上一道的不同之处是，这道题需记录 \(now\) ，即匹配到结点 \(u\) 时的最长匹配长度。令 \(Max_u\) 为当前串在SAM上匹配到结点 \(u\) 时的最长匹配长度。

由parent树的性质，若点 \(u\) 的最长匹配长度为 \(Max_u\) ，则 \(u\) 在parent树上的祖先 \(a\) 的最长匹配长度 \(Max_a=\max(Max_a,\min(Max_u,len(a)))\) 。

每个点 \(u\) 记录一下每个串在 \(u\) 的最长匹配长度的最小值 \(Min_u\) ，则答案即为 \(\max_{u\in SAM}Min_u\) 。

P3975 [TJOI2015]弦论

题面

题解

求一个串字典序第 \(k\) 小的子串。

对这个串建立SAM，每个点处理出它的endpos类的大小 \(size\)，这个可以在parent树上统计。每个点的endpos类的大小代表了在SAM上，从源点到这个点构成的子串在原串中的出现次数。

再在SAM上处理出经过每个点的子串个数 \(sum\) 。显然，\(sum_u\) 即为 \(u\) 在SAM上能到达的结点的 \(size\) 大小之和。

求第 \(k\) 大的子串只需要从源点开始匹配即可。

P4094 [HEOI2016/TJOI2016]字符串

题面

题解

二分最长公共前缀长度 \(mid\) ，于是只需要判断 \(s[c\cdots c+mid-1]\) 这个字符串是否是 \(s[a\cdots b]\) 的子串。

对 \(s\) 建立SAM，记录每个点的endpos类（线段树合并），和所有前缀在SAM上对应的结点。

每次找到 \(s[1\cdots c+mid-1]\) 在SAM上的对应结点，在parent树上倍增找到最后一个 \(len\geq mid\) 的祖先 \(u\) ，\(s[c\cdots c+mid-1]\) 即在点 \(u\) 内。若点 \(u\) 的endpos类中存在一个数在 \([a+mid-1,b]\) 内，那么串 \(s[c\cdots c+mid-1]\) 即是 \(s[a\cdots b]\) 的子串，在线段树上查询区间 \([a+mid-1,b]\) 即可。

P3181 [HAOI2016]找相同字符

题面

题解

将两个串塞进广义SAM中，分别处理出两个串在每个点的endpos类大小 \(size_{0,u},size_{1,u}\) ，那么答案即为：

\[\sum_{u\in SAM}size_{0,u}\times size_{1,u}\times(len(u)-len(fa(u))) \]

P4081 [USACO17DEC]Standing Out from the Herd P

题面

题解

广义SAM。

插入每个字符串时，\(bl_u\) 记录每个结点属于的串的编号，若属于多个串则 \(bl_u=-1\) 。

因为每个结点的信息可以更新它在parent树上的祖先结点的信息，所以最后跑一下拓扑排序更新祖先信息即可。

最后遍历所有结点，若 \(bl_u\not =-1\) ，那么这个点会对串 \(bl_u\) 的答案产生 \(len(u)-len(fa(u))\) 的贡献。

CF666E Forensic Examination

题面

题解

广义SAM+线段树合并。

对所有 \(T\) 串建立一个广义SAM。在parent树上线段树合并记录区间出现次数最多的串。

查询时在parent树上倍增找到 \(S[p_l\cdots p_r]\) 所属的结点，在线段树上查询区间 \([l,r]\) 的信息即可。

SP8093 JZPGYZ - Sevenk Love Oimaster

题面

题解

题解

因为屑SPOJ不给看错误信息，这题调得我心力交瘁

对所有模板串建立一个广义SAM，每个结点用vector记录它存储的串的信息的编号。

然后将询问离线下来区间数颜色即可。

P2336 [SCOI2012]喵星球上的点名

题面

题解

将每只喵的姓和名用一个特殊字符连接起来，插入到广义SAM中。

问题一就是区间数颜色问题，用莫队和树状数组均可。

问题二是求每种颜色被多少个区间数到了。在跑莫队的时候给每种颜色记录一个存在时间，即最后一个这种颜色的数被弹出区间的时间减去第一个这种颜色的数加入区间的时间，那么每种颜色的答案就是它存在时间之和。

P6257 [ICPC2019 WF]First of Her Name

题面

题解

按输入建出AC自动机，再把询问串插入AC自动机中

只需要求询问串在fail树上对应的结点的子树中有几个结点对应了一个夫人的名字。

建出fail树后dfs统计子树答案即可。

P1453 城市环路

题面

题解

基环树最大独立集。

在树上和环上分别做一次DP即可。

CF123E Maze

题面

题解

考虑每条边的期望经过次数。令 \(S\) 为根，对边 \(e\) 的位置分类讨论：

  • 若边 \(e\) 在 \(T\) 的子树内，则期望经过次数为 \(0\) 。
  • 否则，令 \(e\) 连接的深度较小的结点为 \(u\) ，\(u\) 和 \(T\) 的LCA为 \(v\) ，那么在 \(v\) 访问子结点时，只有 \(u\) 所在的子树在访问 \(T\) 所在的子树之前被访问到，\(e\) 才会被经过，这样的概率是 \(\frac{1}{2}\) 。则 \(e\) 的期望经过次数为 \(\frac{1}{2}\times 2+\frac{1}{2}\times 0=1\) 。

所以只有 \(T\) 子树之外的边才会对答案产生贡献。

枚举 \(T\) ，分 \(S\) 在 \(T\) 的子树内和 \(S\) 在 \(T\) 的子树外两种情况统计答案。

P3647 [APIO2014]连珠线

题面

题解

换根DP。

先考虑根确定时怎么DP：令 \(f_{u,0/1}\) 表示点 \(u\) 用第一/二种方式插入图中，指定点 \(u\) 的子树中的边的颜色所能得到的最大得分。

分类讨论 \(u\) 与儿子 \(v\) 之间的边的颜色进行转移：

\[\begin{aligned} f_{u,0}&=\sum_{v\in son_u}\max(f_{v,0},f_{v,1}+w(u,v))\\ f_{u,1}&=\max_{v\in son_u}\{f_{u,0}-\max(f_{v,0},f_{v,1}+w(u,v))+f_{v,0}+w(u,v)\}\\ &=f_{u,0}+\max_{v\in son_u}\{f_{v,0}+w(u,v)-\max(f_{v,0},f_{v,1}+w(u,v))\} \end{aligned} \]

记录最大值和次大值换根DP即可。

CF1051F The Shortest Statement

题面

题解

好题啊好题。

注意到 \(m-n\leq 20\) ，于是这个图可以看作是一个生成树上加入了 \(m-n+1\leq 21\) 条边。

这样两个点的最短路要么只经过树边，要么会经过非树边。若经过非树边，则一定会经过非树边对应的两个端点，而这样的端点个数不超过 \(2\times(m-n+1)\leq 42\) 个，于是可以以每一个端点为起点跑一遍Dijkstra，求出从每个端点到每个点的最短路。

令树上两点距离为 \(dist(u,v)\)，非树边端点所属的集合为 \(S\)， 那么答案即为：

\[\min(dist(u,v),\min_{x\in S}\{dis(u,x)+dis(v,x)\}) \]

CF1096F Inversion Expectation

题面

题解

令未知数个数为 \(x\) ，将逆序对分为三类：

  • 已知数之间的逆序对。用树状数组可以算出。

  • 未知数之间的逆序对。随机选两个数，它们能成为一个逆序对的概率为 \(\frac{1}{2}\) ，则一对未知数贡献 \(\frac{1}{2}\) 个逆序对。则这种逆序对数期望有 \(\frac{x\times(x-1)\times\frac{1}{2}}{2}\) 个。

  • 未知数与已知数之间的逆序对，考虑每一个已知数 \(p_i\) 与所有未知数构成的逆序对的期望个数：

    • 令 \(cntr\) 为未知数可选的数中大于 \(p_i\) 的数的个数，则一个未知数比 \(p_i\) 大的概率为 \(\frac{cntr}{x}\) ，令 \(i\) 之前有 \(y\) 个未知数，则 \(p_i\) 与它前面的未知数构成的逆序对个数期望有 \(y\times \frac{cntr}{x}\) 个。

    • 令 \(cntl\) 为未知数可选的数中小于 \(p_i\) 的数的个数，令 \(i\) 之后有 \(z\) 个未知数，同理， \(p_i\) 与它后面的未知数构成的逆序对个数期望有 \(z\times \frac{cntl}{x}\) 个。

    \(cntr,cntl,y,z\) 都可以前缀和预处理出来。

把三种情况的答案加起来即可。

P3159 [CQOI2012]交换棋子

题面

题解

有次数上限的限制容易想到网络流，但是这个建模难想。

一种显然的建模方式是将相邻格子互相连边，容量为 \(+\infin\) ，费用为 \(1\) ，表示移动棋子。但是这样无法满足次数上限限制。

于是想到将每个点拆成入点和出点，分别连接入点和出点，入点和出点连边表示这个格子最多使用多少次。但是在这道题中移入和移出棋子都会使用这个格子，只拆两个点也无法表示出这道题的限制。

于是就拆成三个点，分别为入点、出点和内部点，连边入点 \(\to\) 内部点 \(\to\) 出点。那么流从内部点流向出点表示棋子移出这个点，流从入点流向内部点表示棋子移入这个点。

那么现在只需要解决如何将次数限制分配到两条内部边上。

若次数限制为偶数，直接均分即可。否则分类讨论：

  • 若初始和目标状态这个格子的棋子颜色相同，那么移入这个格子的棋子数应该和移出这个格子的棋子数相同，那么只需要将限制均分到两条边上即可。

  • 若初始状态有黑棋而目标状态没有黑棋，那么一定有一个棋子移出，让连接内部点和出点的边的容量多一即可。

  • 否则，让连接入点和内部点的边的容量多一。

然后就是费用流模板。

然而这道题有一个坑点：相邻是指有公共边或公共顶点。

P3163 [CQOI2014]危桥

题面

题解

先跑一遍网络流，再交换一对起点和终点再跑一遍，若两次的最大流均为 \(2\times (a_n+b_n)\) ，那么可行。证明。

我是不会证的了/fad

CF1427A Avoiding Zero

题面

题解

令所有正数的和为 \(sum1\) ，所有负数的绝对值的和为 \(sum2\) 。

发现当且仅当 \(sum1=sum2\) 时无解。

当 \(sum1>sum2\) 时，可以将所有正数放在前面，这样所有前缀和都大于 \(0\) 。

否则将所有负数放在前面，所有前缀和都小于 \(0\) 。

LOJ2348 「JOI 2018 Final」美术展览

题面

题解

这题被葛队用不到10min切掉了/fad。

发现若固定 \(A_{min}\) 和 \(A_{max}\) ，那么一定将尺寸在 \([A_{min},A_{max}]\) 中的物品选完，那么 \(S\) 的值就很好求得。将物品按 \(A\) 升序排序，那么选择的物品一定是一段区间。

同时固定两个值有些困难，先固定一个值 \(A_{min}\)。令 \(A_{min}\) 在排好序的物品中下标为 \(i\) ， \(A_{max}\) 的下标为 \(j\) ，有 \(i\leq j\) 。则需要最大化的值即为：

\[\sum_{k=i}^jB_k-(A_j-A_i) \]

令 \(sum\) 表示 \(B\) 的前缀和，则有：

\[sum_j-sum_{i-1}-(A_j-A_i)=sum_j-A_j-(sum_{i-1}-A_i) \]

从右到左枚举 \(i\) ，记录 \(sum_j-A_j,j\in [i,n]\) 的最大值，依次更新答案即可。

P5212 SubString

题面

题解

SAM+LCT毒瘤。

用LCT动态维护parent树，并动态更新endpos类大小。

新加入一个点相当于将它到根上的点的endpos大小加一，LCT链加、单点查询即可。

CF1430E String Reversal

题面

题解

将一个字符串翻转，每次可以交换相邻两个字符，求最少交换次数。

将每个位置赋值为它的目标位置。若没有相同字符，那么答案即为这个序列的逆序对数。

有相同字符的话，让相同字符组成的子序列的目标位置单调递增，即可让逆序对数较小。

CF570D Tree Requests

题面

题解

线段树合并维护子树中同一深度结点的异或和即可。

P4616 [COCI2017-2018#5] Pictionary

题解

题解

对于一个结点 \(i\) ，枚举编号是 \(i\) 的倍数的结点建边。这样建出的图是和原图等价的。

建出图查询最小瓶颈路。

P6228 [BalticOI 2019 Day2]汤姆的餐厅

题面

题解

转化成背包题。

将每道菜的准备时间分成基本时间 \(K\) 和额外时间 \(A_i-K\) ，那么每个厨师最多只会对每道菜的基本时间做出1h的贡献，对所有总的基本时间做出 \(\min(n,B_i)\) 的贡献，其余的时间分配到额外时间中。

一个合法的方案满足下面两个条件：

  1. 所有厨师的总雇佣时间 \(\sum_{i=1}^mB_i\) 大于等于所有菜的准备时间 \(\sum_{i=1}^nA_i\)。
  2. 所有厨师对基本时间的贡献 \(\sum_{i=1}^m\min(n,B_i)\) 大于等于 \(N\times K\) ，多出的部分分到额外时间中。

在满足条件的前提下，要让总雇佣时间最小。

这是一个背包问题，令 \(f_{i,j}\) 表示考虑了前 \(i\) 个厨师，总雇佣时间为 \(j\) 时对基本时间的贡献最多为 \(f_{i,j}\) ，则：

  • 不选 \(i\) ，\(f_{i,j}=f_{i-1,j}\) 。
  • 选 \(i\) ，\(f_{i,j}=f_{i-1,j-B_i}+\min(n,B_i)\) 。

做一遍背包即可。

P3240 [HNOI2015]实验比较

题面

题解

树形背包。

将 \(=\) 关系缩成一个点，\(<\) 关系看作一条边，于是可以建出一个树。

发现 \(=\) 关系中顺序不会对方案数造成影响，于是可以将一段由 \(=\) 相连的质量序列看成一个整体，这样一个质量序列会被 \(<\) 分成若干段。

考虑树形背包，令 \(f_{u,i}\) 表示 \(u\) 的子树内的条件组成的质量序列分成 \(i\) 段的方案数。

令 \(f'_{u}\) 表示 \(u\) 枚举到儿子 \(v\) 之前的DP数组，则 \(f_{u,i}\) 应该由 \(f'_{u,j}\) 和 \(f_{v,k}\) 合并而来。

\(f_{u,i}\) 中的 \(i\) 段，第一段一定只有点 \(u\) ，其他 \(i-1\) 段要么是 \(f'_{u,j}\) 中的一段，要么是 \(f_{v,k}\) 中的一段，要么由 \(f'_{u,j}\) 和 \(f_{v,k}\) 中各一段用 \(=\) 连接起来。

因为 \(f'_{u,j}\) 中第一段一定是 \(u\) ，所以 \(f'_{u,j}\) 只有 \(j-1\) 段可用，第一段一定在 \(f_{u,i}\) 中的第一段，所以 \(j-1\) 段放入 \(i-1\) 段的方案数为 \({i-1 \choose j-1}\) 。

为了使 \(i\) 段中每一段都不为空，\(f_{v,k}\) 的 \(k\) 段中先要用掉 \(i-j\) 段用于填补空缺，剩下的 \(k-i+j\) 段可以放在 \(j-1\) 段中，方案数为 \({j-1 \choose k-i+j}\) 。

那么状态转移为：

\[f_{u,i}=\sum_{j,k}f'_{u,j}\times f_{v,k}\times {i-1\choose j-1}{j-1\choose k-i+j} \]

做树形背包即可。

P3645 [APIO2015]雅加达的摩天楼

题面

题解

直接bfs。

状态为 \((b,p)\) 表示一个在 \(b\) 号楼房的doge的跳跃距离是 \(p\) ，可以证明状态数是可以接受的。

若 \(p<\sqrt{n}\) ，则最多可能跳到 \(n\) 个位置，状态数是 \(O(n\sqrt{n})\) 级别的。

若 \(p>\sqrt{n}\) ，则每个这样的doge都可能跳到 \(\sqrt{n}\) 个位置，状态数是 \(O(m\sqrt{n})\) 级别的。

所以总共也只有 \(O((n+m)\sqrt{n})\) 级别的状态，bfs可以通过。

状态判重用bitset，用数组判重会开不下。

P3708 koishi的数学题

题面

题解

推一下式子可以发现：

\[f(x)=\sum_{i=1}^nx\ {\rm mod}\ i=\sum_{i=1}^n(x-\lfloor\frac{x}{i}\rfloor\times i)=nx-\sum_{i=1}^n\lfloor\frac{x}{i}\rfloor\times i \]

令 \(g(x)=\sum_{i=1}^n\lfloor\frac{x}{i}\rfloor\times i\) ，考虑从 \(g(x)\) 到 \(g(x+1)\) 改变了什么。

发现若 \(i|x+1\) ，则 \(\lfloor\frac{x+1}{i}\rfloor=\lfloor\frac{x}{i}\rfloor+1\) ，那么：

\[g(x+1)=\sum_{i=1}^n\lfloor\frac{x+1}{i}\rfloor\times i=\sigma(x+1)+\sum_{i=1}^n\lfloor\frac{x}{i}\rfloor\times i=g(x)+\sigma(x+1) \]

线性筛出 \(\sigma\) ，即可递推求出 \(g\) 。

P3749 [六省联考2017]寿司餐厅

题面

题解

因为选取了一个区间，那么它的子区间也会被计算贡献，并且所有区间的贡献只会计算一次，那么区间建一个点，\([l,r]\) 向 \([l,r-1]\) 和 \([l+1,r]\) 连边，求最大权闭合子图即可。

P3709 大爷的字符串题

题面

题解

手模一下可以发现，其实是询问区间众数的出现次数，莫队即可。

P3763 [TJOI2017]DNA

题面

题解

建出SAM，在SAM上dfs，因为可修改的字符数和字符集都很少，所以复杂度依旧是 \(O(n)\) 。

P2391 白雪皑皑

题面

题解

由于每个位置的颜色只会被最后一次与它有关的修改影响，考虑倒着处理询问。

维护一个并查集，记录每个位置开始的向右的极长连续已染***间的右端点，这样处理询问时可以直接跳过这一段。

每个点只会染一次色，所以复杂度 \(O(n)\) 。

CF920E Connected Components?

题面

题解

求图的补图的连通块个数。

开一个set存未被访问到的点，每次从这个set中取出一个点开始在补图上bfs。因为这个set的大小减小得很快，所以能够通过此题（好像也找不出数据能卡掉这种做法）。

CF842D Vitya and Strange Lesson

题面

题解

对多个数进行xor操作，想到用01trie。

由于01trie无法进行全局xor，所以不修改，记录所有数应该xor上哪个数即可。

AT4826 [ABC160F] Distributing Integers

题面

题解

首先一个 \(n\) 个结点的树的拓扑序个数为 \(\frac{n!}{\prod siz_u}\) ，那么我们只需要知道以每个点为根时的 \(\prod siz_u\) 即可。

令 \(dp_u\) 表示以 \(u\) 为根时的 \(\prod siz_u\) ，先dfs一遍求出 \(dp_1\) 和以 \(1\) 为根时所有结点的子树大小。

做一个换根即可：

\[dp_u=dp_{fa}\times \frac{n-siz_u}{siz_{fa}}\times \frac{n}{siz_u}=dp_{fa}\times \frac{n-siz_u}{siz_u} \]

AT3537 [ARC083D] Collecting Balls

题面

题解

解题方法不是概率DP，kono环套树da！

贴个题解 懒得写了

P3802 小魔女帕琪

题面

题解

令 \(sum=\sum_{i=1}^7a_i\) 考虑连续的7个数的期望答案数，为：

\[7!\times \prod_{i=1}^7\frac{a_i}{sum-i+1} \]

因为期望的线性性，所以答案只需要乘上一个 \(sum-6\) 即可。

P3761 [TJOI2017]城市

题面

题解

求树上重连一条边之后的最小直径。

考虑数据范围很小，可以枚举重连的边。断掉一条边后，原树会分成两个树。在两个树中分别找出一个点，使得在它所属的树中，离它最远的点离它的距离最小，将这两个点连接起来可以使直径尽量小。

对两个树分别做一次换根DP，找出这两个点。因为新树的直径一定不会小于这两个树的直径，所以还需要分别求一下这两个树的直径。

P4098 [HEOI2013]ALO

题面

题解

这个次大值不好维护，所以枚举一个值，看它在哪些区间中是次大值。因为答案要求的是最大值，所以区间应该尽量大，才有可能出现更优的答案，所以只需要找出它作为区间次大值的最大区间即可。

令 \(i\) 前面第一个比 \(a_i\) 大的数的位置为 \(l_1\) ，第二个比 \(a_i\) 大的数的位置为 \(l_2\) ，\(r_1,r_2\) 的定义类似。则 \(a_i\) 在区间 \((l_2,r_1)\) 和区间 \((l_1,r_2)\) 中是次大值。

考虑如何处理出 \(l_1,l_2,r_1,r_2\) 。每个位置维护前驱和后继，按权值从小到大删数。这样可以保证删一个数时，其他数均比它大，那么 \(l_1\) 即为它的前驱，\(l_2\) 即为它前驱的前驱，\(r_1,r_2\) 同理。

求出区间后，用可持久化Trie查询即可。

CF915F Imbalance Value of a Tree

题面

题解

将最大值和最小值分开考虑。

考虑如何求所有点两两之间路径上的最大点权之和。对每一个边赋边权为它连接的两点的点权中的较大值，将所有边按照边权从小到大的顺序加入图中。

发现加入一条边时，它连接的两个点集中的其中一个集合中的任意一个点到另一个集合中的任意一个点的路径上的点权最大值即为加入这条边的边权，那么这条边的贡献即为两个集合的大小相乘。处理最小值类似。

这类似一个Kruskal重构树，不如说Kruskal重构树的思想有助于理解本题。但是这道题并不需要建出Kruskal重构树，只需要边加边边统计即可。

CF1428F Fruit Sequences

题面

题解

这场考的时候，觉得F题非常可做，像是线段树（迫真。结果做了1h无果，体验了一场下分的***。

考虑扩展右端点 \(r\) 时，什么时候 \(f(l,r),1\leq l\leq r\) 会发生变化。

发现若加入了一个 \(0\) ，无变化。

若加入一个 \(1\) ，设以这个数为结尾的极长 \(1\) 区间长度为 \(x\) ，则原来所有的 \(f(l,r)\leq x\) ，在加入这个数后都会增加 \(1\) 。发现 \(f(l,r)\) 在右端点固定的时候是关于左端点单调不升的，也就是说只需要找到最后一个使得 \(f(l,r)=x\) 的 \(l\) ，令区间 \([l,r]\) 加一即可。

CF242E XOR on Segment

题面

题解

按位考虑，每一位建一棵线段树，维护区间 \(0\) 和 \(1\) 的个数。

异或操作在线段树上区间取反，查询时查询每一位区间内 \(1\) 的个数即可。

P3599 Koishi Loves Construction

题面

题解

Task #1

有以下结论：

  1. 不能存在区间 \([l,r],l\not =1\) 的区间和模 \(n\) 等于 \(0\) ，若存在这样的区间，则 \(sum_r\equiv sum_{l-1} \ ({\rm mod} \ n)\) 。
  2. 由 1 得，\(a_1=n\) 。
  3. 由 2 得，\(\sum_{i=2}^na_i=\frac{n(n-1)}{2}\) ，当 \(n\) 为奇数时，这个式子模 \(n\) 等于 \(0\) ，即区间 \([2,n]\) 的区间和模 \(n\) 为 \(0\) ，由 1 得，\(n\) 为奇数时无解

发现能够将序列构造成这样（模 \(n\) 意义下为原序列）：

\[0,1,-2,3,-4,5,\cdots,-n \]

则对应的前缀和为：

\[0,1,-1,2,-2,3,\cdots,\frac{n}{2} \]

满足了前缀和模 \(n\) 意义下互不相同。

Task #2

有以下结论：

  1. \(a_n=n,a_1=1\)。
  2. 当 \(n\) 为除了 \(4\) 以外的合数时不合法，因为这时 \(1 \sim n-1\) 中一定有 \(n\) 的两个因数，那么就会存在两个前缀积等于 \(0\) 。

发现运用逆元可以解决这个问题，使得前缀积依次为 \(1\sim n\) 。

P5666 树的重心

题面

题解

首先以 \(x\) 为根的树的重心一定在 \(x\) 所在的重链上，于是就可以倍增向重儿子跳。

令树根为 \(u\) ，当前跳到的结点是 \(x\) ，则能够继续跳的条件是 \(siz_u-siz_{p_{x,i}}\leq \lfloor\frac{siz_u}{2}\rfloor\) 。

枚举断掉的边，用换根DP维护 \(siz\) 数组和倍增数组。

LOJ2395 「JOISC 2017 Day 2」火车旅行

题面

题解

考虑倍增，令 \(f_{i,j}\) 表示从 \(i\) 开始跳 \(j\) 次所能到达的最左边的位置，\(g_{i,j}\) 表示从 \(i\) 开始跳 \(j\) 次所能到达的最右边的位置。\(f_{i,0},g_{i,0}\) 可以用单调栈预处理出来，对于 \(i>0\) ，有：

\[\begin{aligned} f_{i,j}&=\min (f_{f_{i,j-1},j-1},f_{g_{i,j-1},j-1})\\ g_{i,j}&=\max (g_{f_{i,j-1},j-1},g_{g_{i,j-1},j-1})\\ \end{aligned} \]

查询时，可以用倍增处理出从 \(A\) 开始跳不超过 \(x\) 步所能到达的最大区间 \(I_{A,x}\) ，用同样的方法处理出 \(I_{B,y}\) ，\(I_{A,x}\) 和 \(I_{B,y}\) 相邻时，\(A\) 和 \(B\) 就能花费 \(x+y\) 互相到达。

LOJ2758「JOI 2014 Final」年轮蛋糕

题面

题解

二分答案，用三指针（？）贪心地找出前两个区间，若三个区间和均大于二分出的答案，那么这个答案就是合法的。

待添加