2021年7月做题记录

[JSOI2009]球队收益（紫）

(https://www.luogu.com.cn/problem/P4307)

标签

网络流，差分

思路

又有胜利又有失利，很麻烦，所以考虑先让所有人除了一开始的 $a$ 场外全部失利，再用费用流跑出胜利的费用。

初步思路，对于一场比赛，从源点向它连容量为 $1$ 价值为 $0$ 的边， 从它向两个球队各连容量为 $1$ 价值为 $0$ 的边，表示每场比赛可以选择一只球队获胜，然后从每个球队向汇点连容量为 $m$ 费用为多获胜一场后奖金的变化量的边

然后求一下变化量,设已经获胜 $a$ 场, 失败 $b$ 场.

$[C(a + 1)^2 + D(b - 1)^2] - [C(a)^2 + D(b)^2]\\ = [Ca^2 + C + 2Ca + Db^2 + D - 2Db] - [Ca^2 + Db^2]\\ = C + 2Ca+ D - 2Db\\$

失败场次等于总场次减获胜场次，总场次是 $a_i + m + b_i$ 设为 $k$，所以 $b = k - a$

所以

$C + 2Ca+ D - 2Db\\ =C + 2Ca + D - 2D(k - a)\\ =C + 2Ca + D - 2Dk + 2Da\\ = C + D - 2Dk + 2(C + D)a$

变化量不是定值，而是一次函数，但因为 $C + D > 0$, 所以这个一次函数是单调增的， 所以对于每个变化量建一条容量为 $1$ 费用为变化量的边即可。

Code

[WC2007]剪刀石头布（黑）

(https://www.luogu.com.cn/problem/P4249)

标签

网络流，差分，二项式系数，容斥

思路

简化题面：给出一张竞赛图，有一些边已经被定向，一些边未被定向，问如何给未被定向的边定向，使得图中三元环个数最多。

从图中任选三个点，这三个点构成环当且仅当在选出的图中三个点入度出度均为 $1$.

令三个点同时满足条件很难，考虑正难则反，先求出三元组总数，再减去无法构成三元环的情况数。对于一个点，如果入度为 $k$ 那么这 $k$ 个入点中任选两个点和这个点都不构成三元环，方案数即 $\tbinom{k}{2}$,因为这是张竞赛图，所以可以不重不漏. 考虑这个点，这个点的一个入点，这个点的一个出点，显然构成三元环。考虑这个点和这个点的两个出点，由于这是竞赛图，所以出点之间也有边，那么在这两个出点中一定有且仅有一个出点有两条入边。所以这种情况会在计算其它点时被计算。

类似于上一道题，考虑增加一个点入度的贡献，发现 $\tbinom{a+1}{2}-\tbinom{a}{2} = \tbinom{a}{1} = a$ , 贡献递增，用和上一题一样的方法就行.

Code

[NOI2008]志愿者招募（紫）

(https://www.luogu.com.cn/problem/P3980)

标签

网络流

思路

第 $i$ 天至少需要 $a_i$ 个人可以用上下界网络流来满足，从 $i$ 向 $i + 1$ 连一条上界为正无穷，下界为 $a_i$ 的边。

想办法表示出招募志愿者，志愿者从 $s_i$ 工作到 $t_i$。 所以可以从 $t_i + 1$ 向 $s_i$ 连一条下界为 $0$，上界为正无穷的边，费用为 $c_i$，这条边刚好可以为 $s_i$ 到 $t_i$ 提供流量。

跑无源汇上下界最小费用可行流即可.

Code

[S2oj493]

(https://sjzezoj.com/problem/493)

标签

$dp$ + 二分

思路

想一个简单的情况， $a = b$， 这时候这道题就是一道很水的 $dp$ ， 设 $f_i$ 表示以 $i$ 为根的子树最少要几个回合，贪心的想，显然要先解决 $f_i$ 更大的子树，再解决 $f_i$ 更小的子树，于是按照 $f_i$ 从大到小给子树排个序，$f_i = f_j + j$. 复杂度 $O(n\lg n)$

然后思考 $a \neq b$, 以 $a$ 为根, 显然对于 $b$ , 优先占领自己的子树一定是最优的，因为 $a$ 占领 $b$ 的子树前要先到达 $b$，一定没有 $b$ 占领快。然后 $b$ 可以考虑向子树外占领，显然的是它占领的一定是以它的祖先为根的一整棵子树，证明同上。

算出 $b$ 占领所用的时间，和抛去 $b$ 占领的子树后，$a$ 占领其它部分所用的时间。取最大值即为所求。

于是考虑到 $b$ 占领到的子树一定是以它的祖先为根的一整棵子树，随着祖先深度的减小，$b$ 占领所用的时间会变长，$a$ 占领所用的时间会变短，取两者最大值，那么两者的最大值是一个非严格凸函数。可以通过二分求出第一个 $f_b > f_a$ 的点，再和它左侧最近的点（最后一个 $f_b \leq f_a$ 的点）取最值。注意因为不是严格凸函数，所有不能三分.

复杂度 $O(n\lg^2n)$ 桶排可以优化到 $O(n\lg n)$ 但是因为二分和排序的常数小，所以没有问题。

Code(https://sjzezoj.com/submission/14644)

[S2oj496]

(https://sjzezoj.com/problem/493)

标签:

$dp$ + 计数 + 矩阵

思路

简化题面：多次询问，求区间本质不同子序列个数

考虑对于每次询问暴力，即单次求本质不同子序列个数。

设 $f[i][j]$ 表示 $dp$ 到第 $i$ 个字符，以字符 $j$ 结尾的本质不同子序列个数。$f[i][0]$ 表示空串

设 $c[j]$ 表示第 $i$ 个字符。

对于 $j \neq c[i]$ $f[i][j] = f[i - 1][j]$

对于 $j = c[i]$ $f[i][j] = \sum_{k=0}^{26} f[i - 1][k]$

复杂度 $O(nq26)$

考虑优化到多次询问，根据经验需要前缀和求。把转移改成矩阵. 发现矩阵长这样.

$10010\\ 01010\\ 00110\\ 00010\\ 00011\\$

意会一下吧，$26 \times 26$ 挺难画。

设第 $i$ 个字符的转移矩阵为 $A_i$ .

那么区间本质不同子序列个数就是.

$(100000) * A_l ...A_r * (111111)^{\tau}\\ (111111)A_r^{\tau} ... A_l^{\tau} * (100000)^{\tau}\\ (111111)A_r^{\tau} ... A_1^{\tau} * A_1^{\tau'} ... A_{l - 1}^{\tau'} * (100000)^{\tau}\\$

$A^{\tau}$ 和 $A^{\tau'}$ 分别如下.

$10000\\ 01000\\ 00100\\ 11111\\ 00001\\$

$10000\\ 01000\\ 00100\\ -1-1-11-1\\ 00001\\$

先计算 $(111111)A_r^{\tau} ... A_1^{\tau} * A_1^{\tau'}$ 。我们只关注每一列的和.

设当前位置的字符为 $c_i$, 第 $i$ 列的和为 $s_i$. $C_{i,j}$ 表示矩阵 $i$ 行, $j$ 列.

那么 $s_j^{'} = 2s_j - C_{c_i,j},$ $C_{c_i,j}^{'} = s_j$

再计算 $A_1^{\tau'} ... A_{l - 1}^{\tau'} * (100000)^{\tau}$ ， 我们只关注第一列的每一项。

发现减法操作对于除了第 $c_i$ 列外每一列是一样的。都会减去第 $c_i$ 列

所以记录一下修改标记，第 $c_i$ 列单独修改。要用到某一列时减去修改标记，用完后记得加上.

Code

[NOI2019]弹跳 （黑）

(https://www.luogu.com.cn/problem/P5471)

标签

最短路 + 线段树 + 数据结构优化建图。

思路

先考虑 $n \leq 100$ ，我不会做，因为 $Floyd$ 复杂度直接爆炸.

考虑 $h = 1$ , 即点向区间连边，可以直接线段树优化建图跑最短路。

那么在二维平面上怎么搞，可以使用 $KD-tree$ ，也可以用二维线段树。这里使用二维线段树。

但是线段树套动态开点线段树空间复杂度 $O(n\lg ^2 n )$ 过不去. 考虑优化空间复杂度.

内层不一定要套动态开点线段树，可以套 $set$ 。

边不一定要真的建出来，直接取出时间最小的矩形，通过线段树求出它包含那些点，记录这些点的最短路长度，并把这些点拓展（把这些能跳到的矩形放到堆中），并在 $set$ 中删除这些点（因为这些点不会在被用来修改或被其它点修改）。每个点会被删除和用来拓展一次. 时间复杂度$(n \lg^2 n)$ ，空间复杂度 $(n \lg n + m)$

Code

CF487E Tourists （3200）

(http://codeforces.com/contest/487/problem/E)

标签

树剖 + 园方树

思路

考虑如果这是一棵树，那显然是树剖裸题。但这些操作在一张图上，考虑转化成树上问题。

用园方树，因为对于一个点双，点双内的两个点一定可以通过至少两种方式互相到达，因为如果只有一种方式，那么割掉必经点，图不联通。所有任意一个点，可以在经过最小点后到达其它任意一个点。

对于一个方点，它的值为相邻圆点的值的最小值，圆点为本身的值。

但这样在修改一个圆点时最多有 $O(n)$ 个方点被修改，复杂度不对。

所以让一个方点的值为子节点的最小值，这样修改一个点时只用更新父节点。

但这样父亲节点就不能贡献给方点了，所以处理询问时对于每个方点要算一下父亲节点，其实只用处理 $lca$ 处方点的父亲.

Code

[SHOI2016]黑暗前的幻想乡（紫）

(https://www.luogu.com.cn/problem/P4336)

标签

矩阵树定理 + 容斥

思路

如果没有每个公司至少修一条路的限制，那么就只需要对于每条边设边权为可以修建它的公司数。跑矩阵树定理求生成树边权积的和。

但是这里规定每个公司必须都有路修。可以用容斥，算出至少有 $k$ 个公司没有修路的情况 $f_k$。$ans = \sum_{i=0}^{n}(-1)^if_i$

Code

[CQOI2011]放棋子（紫）

(https://www.luogu.com.cn/problem/P3158)

标签

$dp$ + 二项式系数 + 计数 + 容斥

思路

设颜色为 $i$ 的棋子有 $d_i$ 个

先考虑一维的情况，答案显然是 $\tbinom{n}{d_1, d_2,d_3...d_c}$.

把它拓展到二维上. 枚举当前在放颜色为 $k$ 的棋子， 已经占了 $i$ 行 $j$ 列. 设 $f[k][i][j]$ 表示放了 $k$ 个棋子，$g[k][i][j]$ 表示用 $k$ 个棋子占 $i$ 行 $j$ 列的方案数, 有 : $f[k][i][j] = \sum_{l=0}^{i - 1}\sum_{r = 0} ^{j-1} f[k-1][l][r] \times \tbinom{n - l}{i - l} \times \tbinom{m-r}{j-r} \times g[d_k][i-l][j-r]$

还有一个难题，那就是求出 $g$.

用容斥 g[k][i][j] = \tbinom{ij}{k} - \sum_{l = 0}^{i} \sum_{r=0}^{j}g[k][i][j](l\neq i \or r \neq j 且 ij \geq k)

最后 $ans = \sum_{i=1}^{n}\sum_{j=1}^{m}f[c][i][j]$

Code

[POI2006]PAL-Palindromes（紫）

(https://www.luogu.com.cn/problem/P3449)

标签

思维 + 性质 + 哈希 + 字符串

思路

很棒的一道性质题，最后我还是看了题解.

收集一下条件 :

1. 每个串都是回文串
2. 把两个串拼起来
3. 求拼起来是回文串的方案数

每个串都是回文串一定是一个非常重要的性质。可以通过这一点证出下面的性质：

当且仅当两个回文串的最小循环节相同时，它们拼成的串是回文串

证明如下:

显然回文串的循环节一定是回文串。

先证明必要性, 如果两个串的最小循环节不相同，设两个串的最小循环节分别为 $u$ 和 $v$ ，那么拼成的串一定存在一对前缀和后缀满足最小循环节不同。所以拼成的一定不是回文串。

证明充要性，如果两个串的最小循环节相同。如果拼成的串最小循环节个数为偶数，显然是回文的。否则的话，因为中间的串是回文串，两边的串又一一对应。所有拼出的是回文串

证毕。

有了这个性质，这道题就很好解决了，求出每个串的最小循环节，寻找有多少个串的最小循环节和它一样。可以用字符串哈希处理。

Code