第一周 备战决赛

第一周备战决赛，和原队友进行了四次训练，恢复了状态。

ECF2017

A1 签 组合数求和

求：

$$\sum_{i=k}^nC_n^i$$

$$T\le10^2,n\le10^9,k\le10^5$$

因为 $k$ 比较小，所以转化为前缀和问题。组合数前一项到后一项的转移是容易的。直接一边求一边加就行了。

J10 铜 思维题

给一个非负整数数列，每次可以给连续 $3-5$ 个数减一，问能否得到全零。

连续的 $3-5$ 个数，等价于连续的 $3$ 个及以上的数。

差分，正数表示区间的开头，负数表示区间的结束，区间的长度大于等于三，所以一个负数只能用至少三位之前的正数去抵消。求一下前缀和，看中间有没有出现负数就行了。

ECF2020

学长说这一场的体验很好，确实如此。整场比赛有一直有事情做，让人感觉非常充实。

A1 银 计数 动态规划

求一个字符串中有多少最小字符表示为 abcdcd 的子序列。

从后往前DP，维护有多少形如 d,cd,dcd的 子序列，然后：

1. 计算每种以当前字符开头的形如cdcd的子序列各自有多少。
2. 对于每种以当前字符开头的形如cdcd的子序列，计算前面有有多少形如ab的子序列。
3. 相乘后累加到答案就行了。

时间复杂度为字符集大小乘字符串长度，空间复杂度为字符集大小的平方。

B2 银 计数 单调栈

给定一个 $n\times m$ 的棋盘，棋盘上的格子会依次消失，给出消失的顺序，求每个时刻棋盘上有多少个长方形。

举例来说，第0时刻棋盘上有 $\frac{n(n-1)m(m-1)}4$ 个长方形。

$n,m\le500$，需要 $n^3$ 的做法。

只要计算每个时刻消失的长方形的数量，最后求前缀和就行了。

我们枚举长方形的上下端点，求出每一列的最小值，即这一列消失的时间。

注意求最小值可以在移动下端点的时候动态更新。

每一列消失的时候，会有许多长方形消失。

长方形的左端点可以是这一列到这一列左边第一个已经消失的列。

长方形的右端点可以是这一列到这一列右边第一个已经消失的列。

所以可以用单调栈维护每一列左遍第一个比它小的列，以及每一列右边第一个比它大的列。

长方形的数量就是两个差量的积。

最后因为爆 int WA 了好几发，果然爆 int 是最常见的错误，没有之一。

G7 金 静态数列 数据结构

给定一个静态数列，每次询问一个区间里有几个子区间有奇数个不同的数。

赛时有思路但没写，赛后卡常卡过去了。我写的是莫队，复杂度比标算慢。

莫队要支持左插、左删、右插、右删，这里以右插为例，其它都是对称的。

每次插入一个数，都会增加许多子区间，统计有多少子区间需要计入答案。

记录上次插入操作增加的子区间的奇偶数量，本次增加的子区间的奇偶数量在上次的数量上更新：

1. 如果当前区间没有和右端点相等的数，每个区间的奇偶性都会反转。最后加上单个数的区间。
2. 否则，从右端点到第一个和右端点相等的数，以这些点为左端点的区间奇偶反转，其它区间的奇偶性不变。

所以我们需要预处理：

1. 每个数的左边第一个和它相等的数的位置。
2. 这个数为右端点，这个数到前一个相等的数中的点为左端点的区间的奇偶数量。

前者非常容易，后者可以用线段树来维护，每次查询一个区间和，再改变这个区间的奇偶性就行了。

HDU02

A1 银 树链剖分

给定一棵有根树，每次询问给出三个节点集合 $A,B,C$ ，问有多少节点 $u$ 满足条件：

1. 存在 $A$ 中元素 $a$ 是 $u$ 的后代。
2. 存在 $B$ 中元素 $b$ 是 $u$ 的后代。
3. 存在 $C$ 中元素 $c$ 是 $u$ 的祖先。

其实没啥思维难度，就写个板子练练手。

树链剖分之后：

1. 给 $A$ 中元素 $a$ 的所有祖先打上标记一。
2. 给 $B$ 中元素 $b$ 的所有祖先打上标记二。
3. 给 $C$ 中元素 $c$ 的所有后代打上标记三。
4. 线段树上每次维护一个区间，都给修改过的所有点和它们到根的路径打上标记四。
5. 打完所有标记，遍历线段树，查询有打上所有标记的区间长度之和，最后再次遍历，清空所有标记。

通过压位技术和非递归线段树，以及快读，代码在OJ上排在第三。

F6 银 概率期望 动态规划

一直以为概率期望是自己的强项，结果连这种套路题都不会做，

要在一个游戏里从 Lv.0 升到 Lv.n，每次抽卡会随机抽出两个整数$0\le a<A,0\le b<B$，表示有 $\frac a A$ 的概率升级，升级失败的话有 $\frac b B$ 的概率降到Lv.0。可以自由选择是否使用每张卡片，问在最优策略下升到Lv.n的期望抽卡次数。

直觉上看，一开始肯定可以使用所有的卡片，随着等级的升高，会越来越不愿承担降级的风险。

总之，用 $ans_i$ 表示最优策略下升到 Lv.i 的期望抽卡次数，则 $\Delta ans_i$ 表示从 Lv.i 升一级的期望抽卡次数。

根据题意：

$$\Delta ans_i=1+\frac 1{AB}\sum_{0\le a<A}\sum_{0\le b<B}min(\Delta ans_i,\frac{A-a}A\Delta ans_i+\frac{(A-a)b}{AB}ans_i)$$

$$0=1+\frac 1{AB}\sum_{0\le a<A}\sum_{0\le b<B}min(0,-\frac{a}A\Delta ans_i+\frac{(A-a)b}{AB}ans_i)$$

$$AB=\sum_{0\le a<A}\sum_{0\le b<B}max(0,\frac{a}A\Delta ans_i-\frac{(A-a)b}{AB}ans_i)$$

注意到等式右边是过原点的、在第一象限单调递增的分段函数，且每段的斜率递增。因此方程有唯一解。

把每个分段函数按照转折点的顺序排序，注意到这个顺序和 $ans_i$ 无关。

一开始答案在所有转折点的右边，随着 $ans_i$ 的增大，转折点会移动到答案左边，这个时候求出来的答案不准确。

不断更新求答案的公式，直到答案落在公式对应的区间内为止。

说得不够清晰

第二周 拿银跑路

第二周去西安比赛，发挥一般，最后拿银跑路。

ECF2021

A1 签 树的遍历

一开始还挺顺利，每人一道签到题。

给定一棵有根树，求出每个节点的 DFS 序的最小值和最大值。

最小值就是深度，最大值就是节点总数减子树大小加一。

B2 银 计数 字符串

接下来就变成多线程卡题。队友怎样我不知道，反正我是被卡常了。

一个字符串分割成六个非空子串，必须具有 $114514$ 的模式（相同的必须相同，不同的可以相同）。

给定一个字符串，求出所有子串的合法分割方案数之和。

$$n\le5000, \sum n\le30000$$

看数据范围应该可以用 $n^2$ 的算法。我的思路是这样的：

1. 对于每个子串，求出以它作为开头 $14$ 的 $14514$ 串的数量 (1)
2. 对于每个子串，求出以它作为结尾 $14$ 的 $114$ 串的数量 (2)
3. 两者相乘求和即为答案
4. 对于每个子串，求出以它作为结尾 $1$ 的 $11$ 串的数量 (3)，最后求个前缀和就得到 (2) 了

我的做法是暴力建一棵后缀树，每个节点按逆序记录对应的所有子串，然后双指针扫一扫得到 (1) 和 (3) 了

使用压位技巧，清空后缀树的复杂度和字符集无关。

最后是一个玄学的事情，每次处理后缀树的一个节点会TLE，但是每次处理一个子串能过，在本机上也能测出这个区别，估计和内存的访问顺序有关。（感谢队友帮我造数据，不然这场真的要拿铁了)

听说正解是 KMP，其实前一周刚刚学习过，仔细一看跟动物园那个题长得真像。不过因为是 $n^2$ 就没想到 KMP 上。

第三周 新队磨合

决赛结束了，新的赛季开始了。回去之后就和新队友接连进行了七场训练赛。

牛客02

D4 铜 二分答案 判断负环

就是说有 $n$ 种货币，以及 $m$ 种单向的汇率，要求一个系数 $w$，使得每个汇率乘上这个系数之后，刚好不存在通过汇率把钱变多的可能。题目保证初始状态存在把钱变多的可能。

$$n\le1000,m\le2000$$

取个对数，二分答案，就变成了经典的判负环问题。然而我不会，还是考场上现学的。

每个节点的初始距离为 $0$ ，然后轮流松弛每条边，如果第 $n$ 轮还是有边被松弛，说明有负环。

I9 铜 合并同类项

$X_k$ 为 $b$ 维列向量，$Y_k$ 为 $c$ 维列向量，求 $Z_k=\sum_{i=1}^nX_kX_iY_i$

$$b\le50,c\le50,n\le10^4$$

这题乍一看好像有很深的数学背景，其实就是个合并同类项。

$$Z_{kl}=\sum_{i=1}^n\sum_{j=1}^bX_{kj}X_{ij}Y_{il}=\sum_{j=1}^bX_{kj}\sum_{i=1}^nX_{ij}Y_{il}$$

把后面那个和式的内容预处理出来，然后去求每个 $Z_{kl}$ 就行了，时间复杂度 $b\times c\times n$ 。

L12 铜 分层图 最短路

有一个分层图，一共有 $n$ 层，每层有 $m$ 个节点，每条单向边只会从一层指向下一层。

首先每个节点都都有边指向下一层的同一个节点，其次还会依次输入另外的 $o$ 条边。

求最少保留连续的几层，可以从第一层的 $1$ 号节点走到最后一层的 $m$ 号节点。

$$n\le10^4,m\le2\times10^3,o\le10^6$$

空间限制比较特殊，不能存下所有的边，只能读一个处理一个。

其实也不难。求出每层的终点可以被走到的最后的起点就行了。

至于怎么求，维护每个节点可以被走到的最后的起点。加入一条边就进行一次松弛操作。拓扑图上的最短路就是这么简单。至于空间，用滚动数组就可以了。

牛客03

A1 签 最近公共祖先

给定一棵有根树和一个节点的集合。求集合中每个元素的补集的最近公共祖先。

最近公共祖先具有可加性，所以就是求前缀和以及后缀和，每次对一个前缀和和一个后缀和求和就行了。

不过还有更优的算法，就算数据量乘上一百倍也能过这个题。其实答案最多只能有两种。

可能成为答案的节点，必须是至少 $k-1$ 个节点的祖先。如果发现一个节点是 $k-1$ 个节点的祖先，就用它来更新剩下的那个节点，如果发现一个节点是整个集合节点的祖先，就用它来更新所有节点的祖先。这样就可以线性求答案了。

B2 银 模拟费用流

有 $n$ 个员工要派到 $m$ 个城市，每个城市需要 $a_i$ 个员工，且 $\sum_{i=1}^m a_i=n$，求最小费用。

$$n\le10^5,m\le10$$

就是个最小费用流，只不过要根据图的性质优化求最短路的算法。

左边是城市，右边是员工，每次找一条最短路，必然是先走到左边的点，再经过若干次反悔，最后走到右边的点。

一次反悔，指先从左边走到右边，再从右边走到左边。于是右边的每一个被选中的点，都可以看成左边的图上的 $m-1$ 条单向边，反悔之后这些边就都不可用了。我们用堆来维护左边每个有序点对之间的最小边权，每次找增广路都在左边跑一次全源最短路，然后找到源点到汇点之间的最短路，增广就行了。

其实完全不会费用流，只会一点最短路。这题是我给出想法，学长去实现的。标算的复杂度要更优一些。

HDU03

这场没有一个题是我写的，震惊。

铜 伪计算几何

空间中有一些线段，求一个平面最多能和多少线段有交。线段的端点都是整点。

$$T\le10,n\le50$$

假设一个平面是答案，它可以在一定范围内移动，在范围的边缘，平面被线段的端点卡住了。

就是说除非所有线段共线，作为答案的平面可以由三个端点确定。

每次任选三个不共线的端点，就可以枚举所有这样的平面，至于如何判断线段与平面相交，只要有向体积之积不为正数就行了。

因为除了求四面体的有向体积没有其它操作，而且都是整数运算，所以是伪计算几何。

HDU04

这场就写了两题，一题只要输出 No 就行了，一题（可以）是线段树，还调了半天。

E5 铜 矩阵乘法 线段树 对顶栈

有一个分层图，一共有 $n$ 层，每层有 $m$ 个节点，每条单向边只会从一层指向下一层。

首先每个节点都都有边指向下一层的同一个节点，其次还会依次输入另外的 $o$ 条边。

求最多保留连续的几层，第一层的 $1$ 号节点走到最后一层的 $m$ 号节点的方案数不超过 $k$。

$$n\le5\times10^3,m\le20,o\le10^6$$

求方案数显然可以用矩阵乘法，线段树的预处理是 $nm^3$ ，查询的时候变成一个行向量乘一堆方阵，用结合律优化一下，单次查询的复杂度是 $m^2lgn$ 的，再双指针扫一扫就行了。

我写的时候，查询的是每个左端点的答案，变成在线段树上二分，会稍微麻烦一点，就当练手了。

题解的方法不同，说是对顶栈。就是双指针扫的时候，如果要维护一个不支持减法的区间和，可以用某种技巧做到只做线性次加法。

例题：给定长度为 $n$ 的整数数列，求所有长度为 $m$ 的区间积的和，答案对 $k$ 取模。

牛客04

B2 银 二重积分

有两个同心圆，许多过小圆的切线组成一个多边形，保证多边形在大圆内，求大圆内多边形外一点到最近的切点的距离的平方的期望值。

二重积分，作每对相邻切点的中垂线，那么每个切点都管辖着两个对称的扇形，把每个扇形减三角形的面积和面积分求出来，最后求和再相除就行了。

$$S=\frac{\alpha R_2^2-R_1^2tan\alpha}2$$

$$A=\int_{\theta=0}^a\int_{\rho=0}^{R_2}\rho((\rho cos\theta-R_1)^2+\rho^2 sin^2\theta)d\rho d\theta-\int_{x=0}^{R_1}\int_{y=0}^{xtan\alpha}((x-R_1)^2+y^2)dydx$$

$$A=\int_{\theta=0}^a\int_{\rho=0}^{R_2}(\rho^3-2R_1\rho^2cos\theta+R_1^2\rho) d\rho d\theta-\int_{x=0}^{R_1}((x-R_1)^2xtan\alpha)dx-\int_{x=0}^{R_1}\int_{y=0}^{xtan\alpha}y^2dydx$$

$$A=\int_{\theta=0}^a(\frac{R_2^4}4-\frac{2R_1R_2^3cos\theta}3+\frac{R_1^2R_2^2}2)d\theta-\int_{x=0}^{R_1}(x^3tan\alpha-2R_1x^2tan\alpha+R_1^2xtan\alpha)dx-\int_{x=0}^{R_1}\frac{x^3tan^3\alpha}3dx$$

$$A=\frac{R_2^4}4\alpha-\frac{2R_1R_2^3}3sin\alpha+\frac{R_1^2R_2^2}2\alpha-\frac{R_1^4tan\alpha}{12}-\frac{R_1^4tan^3\alpha}{12}$$

K11 签 数论

一次操作能把 $i$ 变成 $10i+x(0\le x\le9)$，求对每个模 $n$ 意义下的 $i$，最少几次操作变成 $i+1$。

$$n\le10^6$$

挺简单的题目，不知道为什么学长让我做。

每次操作之后，值域都是一个连续的区间，所以六次之内必然出解。每次对于一个右端点，求它左侧最近的点是否在区间内就行了。

CCPC

F6 铜 状压动规

一个整数 $x$ 要模 $n$ 个模数 $a_i$，可以任意排列模数的顺序，求最终结果的最值。

$$n\le21$$

直接枚举模数的排列有 $n!$ 种情况，无法接受。注意到先模小数后模大数，模大数的操作是无效的。

所以可以把模数排序之后，枚举有效的模数，这样就只有 $2^{n-1}$ 种情况（最小的模数肯定是有效的）。

J10 银 前缀树 分块

有十个四项选择题，给出若干个提交和总得分，问有几种可能的答案。

$$\sum n\le2\times10^4$$

直接枚举所有可能的答案有 $4^{10}$ 种情况，无法接受。注意到前一半的答案确定后，后一半的得分也确定了。

把后一半的每种情况对应的分数插到前缀树中，再对前一半的每种情况查询对应的后一半的得分的情况数就行了。

K11 银 计数

非常无聊的题目，根据样例猜结论猜公式就行了。

上学期

上学期打了两场正式赛，也记录一下。

ICPC

C3 银 概率期望

不断累加随机数（在 $[0,1]$ 之间随机分布），问超过 $x$ 所需要的操作次数的期望。

$$0<x\le20,T\le10^4$$

$$f(x)=\begin{cases} 0 & x < 0 \\ 1+\int_{x-1}^xf(x)dx & x \ge 0 \\ \end{cases}$$

$$f(x)=\begin{cases} 0 & x < 0 \\ e^x & 0 \le x < 1 \\ 1+\int_{x-1}^xf(x)dx & x \ge 1 \\ \end{cases}$$

我发现我已经不会做了，震惊。是时候隐退了。

不过场上第一个过的队是离散取点近似求值的，比较取巧，就当是这样做的吧。

G7 铜 概率期望

有一个无限长的数列，出现 $i$ 的概率是 $p_i(\sum_{i=1}^np_i=1)$，求从第一个数走到下一个相等的数，中间出现过的不同的数的期望个数。

$$n\le 100$$

对于每一个 $i\neq j$，求出从一个 $i$ 走到下一个 $i$，中间没有出现 $j$ 的概率。

$$a_{ij}=p_i+(1-p_i-p_j)p_i+(1-p_i-p_j)^2p_i\dots=\frac{p_i}{p_i+p_j}$$

L12 铜 投影 离散化

平面上有一些整点，每个整点会向若干个不相交的角度范围散发光线，角度范围的边界也是整数。求每个整点能够照到多少个整点。

$$n\le10^5,k\le10$$

对于每个角度范围，将每个点在两个方向向量上的投影长度作为新的座标，然后就变成了求一个点右上角有多少点的经典问题。

唯一要注意的是精度问题。存在两个整点的投影长度相同，当且仅当角度为 $45$ 的倍数，这个时候求投影要用整数和整数去运算，最后再转浮点数，这样就不会出现精度误差了。

ZCPC

E5 银 概率期望 动态规划

有点繁琐的题目，但没什么难度，注意细节就行了。