2024-CSP赛前集训总结

guanyf-blog / 2024-10-08 / 原文

Todo List

9.11 😓

190pt。

比赛界面

T1

对 $n!(1 \le n \le 10^6)$ 进行质因数分解。

Solution

赛时

直接枚举 $1 \to n$，暴力 $O(\sqrt n)$ 质因数分解。时间复杂度并不优越，理论 $O(n \sqrt n)$，实测 457 ms，大概 $O(n \log \log n)$。

玄学算法建议算一下时间复杂度再交，可以多拍几组数据。

题解

A. 预处理出每个数的最小质因数，$O(\log n)$ 分解。

B. 埃氏筛考虑每个质数的贡献，显然 $p$ 的贡献为 $1$，$p ^ 2$ 贡献依然为 $1$（容斥），依然是 $\log$ 级别的。

T2

求树上最多不相交路径，$n \le 2\times 10^5$。

赛时

口胡了一下转 dfn + 序列贪心，做不了一点。

然后开始转 DP，易发现 $f_i$ 表示以 $i$ 为根的子树内的答案。

\[f_u = \max(\sum f_v, 1 + \sum s_j - f_j) \]

显然需要数据结构维护树上单点修改+链求和。

A：数链剖分

B：DFS 序+数据结构维护

LCA 调了我将近 1h。

都不会不如写暴力。玄学评测机跑了 90pt。

没有正解直接交暴力，不要浪费时间

赛后

不需要树剖的方法

显然，赛时脑抽了。可以发现此类问题可以转换成子树修改 + 单点查询，转 dfn 变成区间修改单点查询直接秒了。

要善于转化问题，比如单点修改区间查询问题可以转换成区间修改单点查询。树上问题最方便的就是子树修改 + 子树查询。

3.题解

首先有一个性质：如果一条链选了，那么以这条链的 LCA 为根的子树里的点都不能选了，因此可以从下往上考虑。

显然这非常可以贪心。直接从下往上考虑，能选就选。

因为每个点最多只会被标记一次，因此为 $O(n \log n)$。

多推性质，不要忙于解决问题。

T3

给定一个 $n(1 \le n \le 25)$ 点 $m(1 \le m \le 500)$ 边的有向图，每条边都有边权 $w(1 \le w \le 15)$。初始时你的价值 $c$ 为 $0$。经过每条边可以选择 $1$ 个时间单位通过或 $2$ 个时间单位通过并把 $c = c | w$。求从点 $1$ 出发经过 $T$ 个时间单位回到 $1$ 且价值变为 $15$ 的方案数。

赛时

无。

题解

矩阵快速幂。

如果直接 DP，那么矩阵的大小为 $2 * 50 * 15$，达到了惊人的 $1500$，显然不可取。

考虑容斥，用总的方案数减去某种材料没经过的方案数。

正难则反。

T4

给定 $n$ 个左开右闭区间 $[l,r)$，要分成 $k$ 组，要求每组的交集非空。求这 $k$ 组交集长度之和的最大值。

\[1 \le n \le 8000, 1 \le l < r < 10^5 \]

1.赛时

以为是贪心 or 构造，方向错了，推到比赛结束后都没有推出来。

2.题解

可以把人分为两类（A：包含别人；B：不包含别人）。

A 类的元素可以单独成为一组或者加入它包含的人的那一组。

问题转换为求出 B 组分走 $k$ 组之后的最大值，显然可以用 DP 来求。

此时可以把 B 中的元素按照 $l$ 排序，显然此时 $r$ 也是从小到大排序的。

则此时最优分组一定是连续的。可以构造证明。

$f_{i,j}$ 表示 B 组中前 $i$ 个元素用了 $j$ 组的最大值。

\[f_{i,j} = \max_{k = 1}^{k \le i-j+1}(f_{i-k,j-1} + r_{i-k+1} - l_i) \]

\[ans = \max(cost_i + f_{n,j-i}) \]

显然，可以使用单调队列优化。

9.16 😫

比赛界面

T1

给定 $n$ 个 $1$ 到 $m$ 之间的整数 $a_i$，你可以把三个编号相等或者三个编号连续的分为一组。求有多少组分组方案（组和整数都没有编号）。

数据约束：

\[1 \le a_i \le m \le n \le 3 \times 10^4 , n \equiv 0 (\operatorname{mod} 3) \]

赛时

DP。把 $a$ 分类。显然，不相连的一块可以看作是独立的。再者，我们可以通过预处理把同一块内的元素全部推平成 $3$ 的倍数。如果此时有元素小于 $0$ 或者依然不是 $3$ 的倍数，则 $ans = 0$。

接下来可以把 $a$ 中元素除以 $3$，每次操作就等价于把相邻三个元素减去 $1$。

一直死磕 $n ^ 2$ DP，结果假了，只剩下 30min 了。。。

赛后

这道题正解就是 $n ^ 2$，因为 $n_{max} = 30000$，因此常数够小就能过。

状态设计成 $f_{i,x,y}$，表示位置 $i$ 最后两位为 $i,j$ 的方案数。转移很容易推，就省略了。转移的过程可以用前缀和优化掉，状态可以用滚动数组减少 $1$ 维。

时间复杂度：$\operatorname{O}(5000 * 5000 * 2 \approx 5 \times 10^7) $，十分优异。

T1 不仅赛时调了我 $3$ 小时，赛后调了一下午。绷不住了。

9.22 😣

比赛界面

T1

1. Statement

给定正整数 $n$，计算 $n$ 个元素的集合 $\{1, 2, \dots, n\}$ 所有非空子集和的乘积取模 $998244353$ 后的结果。

\[1 \le n \le 200 \]

2. 赛时

5min 推出正解，然后唐了，《$a^b = a ^ {b \bmod p}$》。一个小时时间直接没了，心态爆炸。

其实就是枚举子集和 $s$，通过 DP 求出凑出 $s$ 的方案数，注意 $f$ 数组需要写高精度。

3. 题解

欧拉函数求得 $f$ 可以对 $p-1$ 取模。

T2

1. Statement

有 $n$ 栋楼，每栋楼有 $k$ 房子。$m$ 个询问，每次询问给定 $x,y$，表示这 $y$ 个人要分配到 $[x, x + d]$ 栋楼中（$d$ 是定值）。对于每次询问都需要输出能否成功分配。询问之间会相互影响。

\[1 \le n,m,d \le 5 \times 10^5 \]

2. 赛时

基本上所有时间都花费到这道题上面了。根据显然的贪心可以得出把所有限制按照左端点排序。能尽量往左排就尽量往左排。然后接下来就在想怎么用线段树维护。可以维护，但是非常难写。

3. 赛后

设 $a_i$ 表示当前左端点为 $i$ 的线段的数量。

思考一下分配不了的必要条件：必定有一个区间 $[l, r]$ 满足 $\sum_{i = l}^{r} a_i > k(r-l+1+d)$。证明这个条件为充分条件：按照之前所述的贪心可以把所有限制排成若干个首尾相连的线段，则必定存在一个区间使得区间内的限制和大于区间内的容量。

设 $s_i = \sum_{i=1}^{i} a_i - ki$，则可以分配时一定满足 $s_r - s_l \le kd$。

显然可以用线段树维护。

T3

T4

1. Statement

给定一个包含 '01?' 序列 $a$，相邻的任意 $11$ 可以随便移动，求最终序列的方案数。

2. 赛后

DP。设 $f_{i,j,k,0/1}$ 表示前 $i$ 为填了 $j$ 个 $11$，$k$ 个 $0$，并且 $i$ 是否可以在后面接一个 $1$ 变成 $11$。

最后对于每种 $f_{n,i,j}$，把 $0/1$ 两种情况加起来乘上 $\binom{i+j}{j}$ 就好了。

解释一下 $\binom{i+j}{j}$ 是怎么来的。

你发现一个 0 是无法跨过长度为奇数的 1 的连续段的。
所以对于序列中的任意两个 0，中间的 1 的奇数段的数量是一定的。
所以答案是 $\binom{i+j}{j}$。

9.24 😞

2024-09-24 数学场

T1

1. Statement

有 $a$ 个 $0$，$b$ 个 $1$，$c$ 个 $2$。两个人轮流做操作。如果当前没有数可以选或者当前选之后所有数的和是 $3$ 的倍数，则这个人输了。求先手赢还是后手赢。

赛时没开 long long，证明无论什么题都要对拍或造样例。

2. 赛时

开局 1h 推结论看错题了。以为是每个人单独的和。以后一定要先把题目看清楚再写题。显然初始时只能选 $1$ 或 $2$。一个人选了 $1$ 或 $2$，另一个人只能选 $0$ 或另一个数。再者，$0$ 无论什么时候选都不会影响最终答案。

T2

1. Statement

对于所有长度为 $n$ 排列 $a$，求满足第一个 $i > a_i$ 的期望（如果不存在 $i$ 则为 $n+1$）。

2. 赛时

问题可以转换成对于每个 $i$，求出所有排列中，$i > a_i$ 且这个 $i$ 为第一个的方案数。枚举第 $i$ 位为 $j$，则需要满足 $\forall 1 \le k \le i, a_i \ge i, a_i \not= j$。赛时急了，没有仔细往下推，以为有什么神秘性质可以直接求。

3. 题解

看来赛时真是唐了，稍微推一下就可以得到下面的式子。对于每个 $i$ 的贡献为：

\[t = n - i + 1 \]

\[\newcommand {\*} {\times} \begin{equation*} \begin{aligned} C &= i \* (n-i)! \* \sum_{j=1}^{i-1} (t-1)^j \* t^{i-j-1} \\ &= i \* (n-i)! \* (t-1)^{n-t+1} \* \frac{t-1}{t} \* \sum_{j=0}^{n-t} (\frac{t-1}{t}) ^ j \\ &= i \* (n-i)! \* (t-1)[t ^ {n - t + 1} - (t-1) ^ {n-t+1}] \end{aligned} \end{equation*} \]

T3

1. Statement

设 $x(x \in \N) = \sum_{i=1}^{n} \text{fib}_{a_i}$，满足 $\forall i \in [1, n), a_i < a_{i+1}$，则 $a$ 为 $x$ 的唯一斐波那契分解。

定义 $val(x)$ 表示 $\oplus_{i=1}^{n} \text{fib}_{a_i}$，现在给定 $m$ 次询问。每次询问给定 $l,r$，求 $\oplus_{i = l}^r val(i)$。

2. 赛时

Joker 了。前两题花了太多时间，只够打个前缀和暴力。

3. 赛后

推了一下发现有一种做法是枚举求出第 $i$ 位在 $[l,r]$ 中出现的次数。不太好做。

然后把斐波那契联想成二进制发现这类题最好做的方法就是 数位 DP。设 $f_i$ 表示 $\oplus_{i=1}^i val(i)$，找到最高位的值 $j$，则 $f_i = f_{j-1} \oplus f_{j \to i}$，观察到 $f_{j \to i}$ 中的每一个数都带有 $j$，因此

\[f_{j \to i} = f_{i-j} \oplus \begin{cases} j &\text{if} ~ i - j + 1 ~ \text{is} ~ \text{odd} \\ 0 &\text{otherwise}\end{cases} \]

显然，斐波那契数列的增长是 $\log$ 级别的。

T4

1. Statement

给定 $n,m$ 和长度为 $n$ 的数组 $a$，表示有 $n$ 种面值的货币。每种货币有无数张。求 $[1, m]$ 中最大的不能被凑出来的数。

2. 赛时

依然是没有时间，T3 时间都不够了，更别说 T4 了。

3. 赛后

完全背包可以水过大部分分，加了 bitset 卡卡甚至能水过去。

显然题目中的随机性是非常重要的性质。可以设置一个模数 $mod$，跑一遍同余最短路。$mod$ 是越小越好。如果一个数 $x$ 凑不出来，则答案更新为 $x$；如果 $x$ 凑得出来，则答案更新为 $x-mod$。

随机数据中一个小数为 $\frac{m}{n+1}$，时间复杂度为 $\operatorname{O}(\frac{m}{n+1} \log^2 n)$

9.25 😵

比赛界面

T1

1. Statement

给定一个长度为 $n$ 的数组 $a$，如果 $i \in [2,n-1],a_{i-1} > a_i, a_i < a_{i+1}$ 则定义 $a_i$ 为低谷点。你可以把至多 $k$ 个值减小，求操作之后的最大的所有低谷的和。

\[1 \le k \le n \le 2000, 1 \le a_i \le 10^9 \]

2. 赛时

先推性质。显然如果前面操作之后，那么这个点再操作一定不是最优的。看到数据范围果断放弃贪心选择 DP。调了 30min 还是调了出来，整体节奏还是可以的。

T2

1. Statement

给定一个长度为 $n$ 的数组 $a$。进行 $n - 1$ 次操作。设每次变换之后的 $a$ 为 $a'$ ，第 $T$ 次操作具体如下：

\[1 \le i \le n - T, a'_i = \begin{cases} a_i - a_{i+1} &\text{if} ~ n-T ~ \text{is} ~ \text{odd} \\ a_i + a_{i+1} &\text{otherwise}\end{cases} \]

显然，所有操作之后 $a$ 将只有一个元素，求这个元素。

\[1 \le n \le 10^9, 1 \le a_i \le 10^9 \]

2. 赛时

观察到最终答案对应 $a$ 中每个元素的系数一定与杨辉三角有关，这很容易感性理解。但数学知识储备不够多，没有推出来通项公式。中途尝试使用矩乘，显然不可行，2h 浪费了。

3. 赛后

如果 $n$ 是奇数，则每一项的系数为 $\sum_{i=0}^{\frac{n-1}{2}} C^2_{\frac{n-1}{2}} \times (-1)^i$。如果为偶数，则操作一次之后可以变为奇数。

T3

1. Statement

$2^n$ 个人打淘汰赛，编号为 $1$ 的人初始时收买了 $m$ 个人。每场比赛都会让编号更大的人赢，但是 $1$ 遇到被他收买的人他会赢。求有多少种排列方式使得 $1$ 能赢且中途打比赛遇到的人构成的序列的最长上升子序列长度 $\ge k$。

\[1 \le k \le n \le 9, m \le 16 \]

2. 赛时

DP。时间不太够了，没有仔细推。打了暴力还挂了。

3. 赛后

枚举 LIS 作为状态进行 DP，详见代码。

T4

1. Statement

题面过于复杂，见原题面。

2. 赛后

大模拟先攒着，之后补。

需要暴力出所有的五元组，然后把这些五元组排序，以及存一下每个三元组，可能构成哪些 $rank$ 的五元组。写完以后对于每组询问，就直接在对应的三元组里面二分就好了。

9.27 😰

0 + 0 + 0 + 30 = 30pt

比赛界面

T1

1. Statement

给定一个长度为 $n$ 的数组 $a$，你可以按任意顺序排列这个数组，求是否有一种排列方案使得拆分数组 $d$ 不存在元素 $x$，如果有，则输出方案。

\[1 \le T \le 2 \times 10 ^ 5, -10^9 \le x \le 10^9, 0 \le a_i \le 10^9, \sum{n} \le 2 \times 10^6 \]

2. 赛时

构造。想了一会发现可以分讨，先讨论 $x = 0$ 的情况，发现同一种元素中需要插空插其他元素，很容易就可以把不合法的情况判掉。需要注意的是，如果第一个数是 $0$，则需要把第一个数换掉。

如果 $x < 0$，直接从小到大排，赛时没看到 $x$ 为非负数，还讨论了一下第一个数是负数的情况。。。

如果 $x > 0$，从大往小排，如果第一个数为 $x$，则需要与后面的数交换。

细节比较多，没有注意就会全挂掉。

3. 赛后

$x = 0$ 的情况赛时准备写链表的，后面发现可以用 vector，但依然比较复杂。这是一类比较经典的模型，每两个元素相消，可以使用 优先队列 来做。每次把出现次数最多的元素排出去，正确性显然。

一定要对拍啊。不然很容易挂分的。

T2

1. Statement

给定一个 $n$ 点的树，每个点有一个点权 $a_i$，定义 $\operatorname{happy}_{s,t}$ 为 $s$ 到 $t$ 的简单路径上的最大点权减去边数，求 $\sum_{s \not= t} \operatorname{happy}_{s.,t}$。

\[2 \le n \le 10^6, 0 \le a_i \le 10^9 + 7 \]

2. 赛时

显然可以把问题分成减边数和加最大值这两个子问题。前一个子问题非常轻易的就可以做到。

赛时尝试过枚举一条路径上深度最浅的点，不好算；也试过枚举路径的起点做换根，也不好算。推出来了每个点有一个 作用域 但是不知到怎么去维护它。。。最后只好打了个暴力，还是想复杂了，写了在线查询的，没想到可以直接 $n$ 便 DFS，不出意料的挂了。

3. 赛后

我是什么品种的废物啊 $\texttt{QWQ}$。其实可以把点权排序，如果从大到小排序，就变成了删边求联通块大小，不好做。如果从小到大排序，就变成了加边求连通块大小的问题，可以用并查集轻易的解决。

多从几个方面去想，这道题涉及到了 $\max$ 自然而然地就应该想到排序。不要觉得题目难做法一定就难。

T3

1. Statement

给定一个长度为 $n$ 的只包含 NOIP? 这五个字符的字符串。对于每个 ? 你可以填入前四个字符中的任意一个。接下来会给你一个 $4 \times 4$ 的矩阵，对应着相邻两个字符所代表的权值。一个字符串的价值就是任意相邻字符的权值之和。求所有权值 $\le x$，按字典序降序排列第 $k$ 大的解。

\[2 \le n \le 10^3, 1 \le k \le 10^3 \]

2. 赛时

现在看到这类状态数量很大的就认为是 DP 了，看到 DP 就有点 ptsd 了。以为又要花很多时间，跳过去了。其实就算给我那么多时间我也想不到可以用搜索来解决这道问题。

3. 赛后

刷新了我对搜索的认知。

其实搜素只要剪枝得当，时间复杂度就会从指数调到正解。就类似于暴力 DFS 与记忆化搜索的区别。在这道题中，因为 $k$ 很小，所以可以直接按照字典序从大到小，把所有合法的答案搜出来。如果当前答案不合法，就直接剪掉。至于怎么判合不合法，只需要当前状态往后填的最优价值 $\le x$ 就行了。当然不可能对于每个状态都做一次 DP，因此可以从后往前预处理出每一位选每个字符的最大权值。搜索时记录出当前的权值，加起来判。时间复杂度是优异的 $\operatorname{O}(nk)$。

你说得对，但是这其实就是广义上的 A* 算法。

T4

1. Statement

给定一个长度为 $n$ 的字符串 $s$，求 $s$ 所有子串的所有 border 的长度之和。

2. 赛时

如果直接暴力写 KMP，显然是过于暴力的。发现这道题本质上就是在求每个子串的出现次数，不会 SAM，SA 也没学懂，只能通过 Hash 莽了 30pt。

3. 赛后

对于 SAM 来说，这道题就是板子。对于 SA 来说，可以利用 $height$ 数组来模拟。从左往右看，就是一个区间不断分分分的过程，但是区间并不均匀，不好做。但是如果从右往左看，就变成了区间合并问题，可以使用并查集来做。

9.29 😕

比赛界面

70 + 90 + 0 + 0 = 160pt

T1

1. Statement

有四盏灯，在一个四方格内。你可以调节每一盏灯的耗电量，每一盏耗电为 $x$ 的灯可以为当前位置提供 $x$ 的亮度，为旁边两格提供 $\lfloor \frac{x}{2} \rfloor$ 的亮度，为对角线的格子提供 $\lfloor \frac{x}{4} \rfloor$ 的亮度。现在给定每个格子最低的亮度要求，求四盏灯最低的耗电量之和。

2. 赛时

一开始推式子，天真地以为可以 $O(1)$ 算。显然不好算。看到数据范围选择 $n ^ 2$ 枚举。又试了一下能不能再直接 $O(1)$ 算，显然不行。尝试了一下里面套个二分检验，觉得是三分，常数太大了，且不好写。已经浪费较多时间了，选择 $n^3$ 暴力然后开下一题。

3. 赛后

赛时只要往三分的方向去想，就输了。以后做这类数学题，一般要主动往有单调性的方向去想。比如这道题，就完全没必要去对一盏灯的亮度去考虑。而是可以直接二分总耗电，然后去检验合法性。检验可以直接 $n ^ 2$ 枚举对角线两盏灯的耗电，此时这个不等式就变成了一元不等式。因此可以求出其中一盏灯的大约范围，直接枚举取最小值就行了。

此外，还有一种做法。当枚举对角线的两个点时，会发现它很具有连续性，因此每次剩下两盏灯的波动并不会太大，这种做法比上一种做法优异很多。

T2

1. Statement

给你一个 $n$ 点的树，每个点上都有一个带有权值的蚂蚁，每个蚂蚁可以留在原地或者向上爬到父亲，且最多只能爬一次（位于节点 $1$ 上的蚂蚁只能留在原地）。当所有蚂蚁都爬过之后，每个点上的权值为：如果当前点的蚂蚁数量小于等于 $1$，则这个点没有贡献；否则贡献为这个点上所有蚂蚁权值的异或和。求所有情况的权值和。

2. 赛时

一眼 DP。设 $f_{i,0/1}$ 表示以这个点为根的子树的所有情况中这个点的蚂蚁上不上去的价值和。转移很好像，把 $f$ 和蚂蚁的贡献分开来求。对于蚂蚁的贡献来说，可以从二进制位的方面去考虑。思路比较简单，但是细节较多，调了我好久。

3. 赛后

其实这道题正解可以算是递推或者组合数学，赛时做法过于复杂了。

T3

1. Statement

你有 $n$ 个字母 A，$m$ 个字母 B。每连续 $a$ 个 A，且下一个依然是 A，则价值会加上一。每连续 $b$ 给 B，也同理。当这个字母与前面一个字母不一样时，价值加一。求最大价值。

2. 赛时

真的写 DP 写到 ptsd 了，看什么都是 DP。。。觉得又是什么神秘 DP，选择开下一题。

3. 赛后

很难想象 C 会放比较容易的贪心。其实这道题贪心策略是非常容易想的。显然，交错次数过多，答案相对会更优。但是这个交错次数有一个界限，因此可以枚举这个界限。由于 A 转换到 B 是没有条件的，因此每一组应该被分成 $c$ 个 B 和 $1$ 个 A，类似于 BBBABBBA。如果还剩下 A，就往开头填；如果还剩下 B，就往结尾填。还剩下 A，每 $a$ 个可以加一贡献。还剩下 B，可以先把 $c$ 填满，再继续填。

T4

1. Statement

有一个函数 $f(x)$，这个函数有 $n$ 个步骤，第 $i$ 个步骤如下：

\[x = \begin{cases} x + val_i &\text{if} ~ op_i ~ \text{is} ~ 1 \\ \min(x, val_i) &\text{if} ~ op_i ~ \text{is} ~ 2 \\ \max(x, val_i) &\text{otherwise}\end{cases} \]

接下来有 $q$ 次操作，每次操作要么改变 $f$ 第 $i$ 步的 $op$ 和 $val$，要么给定 $x$，求 $f(x)$。

2. 赛时

Subtest 2 + 暴力已经想出来了，时间不够了，匆匆忙忙结果写错了🤡。

3. 赛后

路上想出来了 Subtest 3 的二分做法和 Subtest1 堵塞做法，推出来了每一段答案可以表示成一段区间。

通过题解得知，每一个答案不仅可以表示成区间，还要表示成加上某个值。这个操作可以通过线段树维护。

\[\colorbox{black}{。。。} \]

9.30 😭

比赛界面

44 + 20 + 25 + 20 = 109

T1

1. Statement

$n$ 个点的树，有边权。选择一对点 $(u,v)$，这段路径上的边权极为 $S$。A 先手，B 后手。每个人轮流选走一个小于等于上一个数的数。如果当前没有数可选，则这个人输。求有多少对 $(u,v)$ 使得 A 能赢。

2. 赛时

绷不住了，1min 出正解 30min 思考如何求答案，我是什么品种的弱智。。。先思考博弈策略，显然，序列中只要出现一个出现次数为奇数的数，则先手必胜。然后这个东西可以抽象成二进制异或，然后就可以简化成每个点到根节点。考虑容斥，出现不好求，求逆变成所有都为偶数。回到刚才的点到根节点，因为只要两个点异或起来为 $0$，即连个点所对应的二进制数相同，则答案要减去对应值。

但是这个二进制数有 $5 \times 10 ^5$ 位，所以很自然就会想到 Hash。但是赛时弱智了，一直想到用数据结构维护。

3, 赛后

除了刚才说的 Hash 做法，还可以使用一种非常新的技巧：随机化。把每个边权赋一个随机值，只需要记录跟到每个节点的异或和就行了。

T2

1. Statement

给定长度为 $n$ 的序列 $a$，初始时你在位置 $1$.你可以跳 $k$ 次，如果 $k$ 是奇数，则可以跳到你右边的任意一个格子，否则可以跳到左边的任意一个格子。每次跳跃的价值定义为跳跃时经过的所有点之和。求 $k$ 次跳跃之后的最大价值。

2. 赛时

DP。看到 $k$ 很大，要么 $\log_2$，要么数学。显然 $\log$ 做法时不可行的。数学有两种做法，一种是循环节，一种是最大子段和。个人认为循环节最有可能，写了。赛后才发现假了。。。

3. 赛后

先说另外一种人类智慧做法，因为 $n$ 很小，所以可以先处理出前 $\min({k, T})$ 跳到某个位置的最大价值，然后剩下的就来回跳以 $i$ 为端点的最大子段和。事实上，$T$ 只需要取到 $8$ 就行了。这种做法达到了惊人的 $\operatorname{O}(N)$。

对于最大子段和这种做法来说，也是 DP。不过必须先推出几个性质：

钦定一个点，在这个点经过若干次跳跃之后，接下来来回跳以这个点为右端点的最大子段和。对于若干个转移来说，时间最小的最优（这并不难证明）。因此转移到这个点的价值就变成了附带属性。
如果以这个点为右端点，无论怎么跳，都不会跳到这个点右边。

接下来的转移随便转就行了。

T3

1. Statement

$n$ 个节点的树，可以把数量位于 $[B, 3B]$ 之间的若干个点分为一个省（这些点不一定联通）。每个省都要确定一个省会 $y$，一个点可以是多个省的省会。但是对于同一个省里面的任意点 $x$，都需要满足 $(x,y)$ 路径上点和 $x$ 在同一个省。给出一种划分方案。

2. 赛时

贪心，赛时时间不够了，糊了一个连样例都没过的乱搞。竟然有 25pt。

3. 赛后

从底到跟去考虑。对于每个点来说，假设它所有的城市个数小于 $B$ 的子树，利用优先队列把它们合并，这个点作为这些省的省会。此时可能会存在一个省的大小依然小于 $B$，可以把它与当前这个点划分成同一个省，往上传，就变成了子问题。

对于根节点来说，没法往上传，但是由于此时任意一个省的大小都 $< 2 * B$，且根节点所属的省的大小 $< B$，只需要随便找一个合并就行了。

T4

1. Statement

给定长度为 $n$ 的排列 $a$，每次操作可以把区间 $[l,r]$ 循环右移 $k$ 位，求出每次操作之后是否存在上升三元组。

2. 赛时

一直以为是 $n \sqrt n$ 做法。

3. 赛后

循环右移等同于把一段区间交换，只能使用 FHQ-Treap 来做。需要维护出一个子树内的最大值，最小值，两位的前面最大值，两位的后面最小值。

发现后面两个值并不好维护，因为子树内的值并不具有单调性。可以通过先把 ok 的情况判掉来构造单调性。

10.2 😔

36 + 5 + 80 + 0 = 121pt

这场比赛时间分配真的不好。。。

比赛界面

T1

1. Statement

给以一个 $n$ 点的树，树上每条边都有一个边权 $w(1\le w\le10^{100})$，每经过这条边代价就要加上 $w$，树上有 $m$ 个初始点和 $m$ 个终点，每个初始点都要移动到一个终点上，且一个终点只能对应一个初始点。求最终最少的代价。

2. 赛时

本来准备贪心切掉的，每个点移动到子树内最远的点。发现并不好维护，接下来推出两个性质：

当出现类似于 A1...B2...B1...A1 时必定不是最优的。
A1...A2...B2...B1 和 A1...A2...B1...B2 的代价是一样的。

接下来就有一个更优的贪心策略了：对于子树内的点，如果还剩下多余的起点，就往上移；对于每对起点和终点，随便找一个消掉就行了。

但没必要这么做，可以换一种角度来想，把起点挪动终点相当于把起点和终点都分别挪到它们的 LCA。这时只需要对于同一个节点内的起点终点两两相消。

但是，我赛时因为神秘错误大样例挂了调了 3h 死活调不出来😡，我甚至开始怀疑我贪心的正确性，心态爆炸，后面的题直接寄了。赛后才发现我高精 fill 没清完。这是人能调出来的错误吗。。。

T2

1. Statement

有 $n$ 种价值的物品，第 $i$ 种物品的价值为 $v_i$，出现次数为 $c_i$。你每次可以选择两个物品，它们所浪费的价值为 $m - ((v_i + v_j - 1) \bmod m + 1$。求最优匹配下的最小浪费价值。

2. 赛时

推了式子，以为是 DP，没有往贪心的方向想。

3. 赛后

其实只要往贪心这方面想，这道题就直接秒了。显然，设一个数浪费的值为 $b_i$，先不考虑其他情况，无论怎么分配，浪费价值都为 $\sum{b_i}$。当 $b_i + b_j \ge m$ 时，总浪费价值就会减去 $m$。这时贪心策略就出来了：尽可能然更多的 $b_i + b_j \ge m$。这类题可以直接排序 + 双指针秒了。

T3

1. Statement

$n$ 个学生，第 $i$ 个学生的做题数为 $f_i$，成绩为 $t_i$，只有当 $a_j \le t_i \le b_j$ 时且 $c_i \le t_j \le d_i$ 时，$i$ 才会帮 $j$ 完成它的 $f_i$ 道题。

2. 赛时

没有时间推了，时间给够一定可以推出来。

3. 赛后

显然，这道问题可以转换成 $t_j$ 在 $[a_i, b_i]$ 这段区间中的 $[c_j, d_j]$ 这些区间中包含 $t_i$ 的区间个数，这玩意很显然可以前缀和。可以从把所有值离散化，在值域中由小到大枚举。对于每个点记录出它是哪些 $[a_j, b_j]$ 的左端点或右端。枚举的过程中用数据结构维护在区间 $[c_i,d_i]$ 加 $f_i$，单点查询 $t_j$。然后这道题就没了。

T4

1. Statement

给你一个序列和若干个询问，每次询问给出一个区间，求出这个区间所有数字乘起来之后，莫比乌斯函数值，
约数个数，约数和。

2. 赛时

以为有什么神秘性质可以通过线段树维护。

3. 赛后

先攒着，等题过后更新。

10.3 🥴

45+100+0+100 = 245

比赛界面

信心赛考成这样。。。

T1

1. Statement

长度为 $n$ 的序列 $a$，每一位可以填入 $[1,m]$ 中的任意整数，对于序列 $a$ 和 $b$ 来说，定义它们相同仅当满足 $\exists k, \forall i, a_i \equiv b_i + k \pmod m$。求有多少个不同的 $a$。

2. 赛时

显然，在不考虑相同的情况下，方案数为 $m ^ n$。更显然，每个相同组的大小都为 $m$，因此答案就是 $m^{n-1}$。

3. 赛后

还有一种思考方式，先假设第一位固定为 $1$，那么接下来的方案数为 $m^{n-1}$。此时把第一位的限制拿掉，会发现无论怎么变，都会与之前的相同，因此答案就是 $m^{n-1}$。

T2

1. Statement

有 $n$ 个果园，每个果园有 $a_i$ 个果子。有两个工厂，每个工厂有 $b_i$ 个机器。每个果园可以把果子以任意一种分配方式分给两个工厂。设第 $i$ 个园子给了第 $j$ 个工厂 $w_{i,j}$ 个果子，则运输时间为 $d_{i,j}$，加工时间为 $u_{i,j}$，如果 $w_{i,j}$ 不为 $0$，则需要用掉第 $j$ 个工厂 $c_{i,j}$ 个机器。任意时刻都不能让任意工厂机器 $<0$。最终所耗时间为 $\max(w_{i,j} \times d_{i,j}) + \max(w_{i,j} \times u_{i,j})$。求最小耗时。

2. 赛时

阅读题面花了好久。

因为数据范围很小，先考虑暴搜，发现常熟过大，且 Meet in middle 不好实现，放弃暴搜。

考虑 DP，发现状态数量很大，怕炸空间，且不好优化，放弃 DP，选择开下一题。

回到这一题，发现真正的难点是 $\max$，考虑枚举 $T_d$，DP 求出最小的满足条件的最小的 $T_u$。发现 $T_d + T_u$ 近似于单峰函数，选择三分。

3. 赛后

不出意料，赛时挂了 55pt，既有 DP 的锅，也有三分的锅。很容易就会发现，这个函数会出现重复值，就不能用三分。因此只能枚举每个可能的 $T_b$，二分跳掉重复值。

除此之外，这道题确实可以 DP。设 $f_{i, b1, b2, j}$ 表示考虑前 $i$ 个果园，第一个工厂用了 $b1$ 个机器，第二个工厂用了 $b2$ 个机器，第一个工厂运了 $j$ 个果子的最小运输时间。同理 $g_{i, b2, b2, j}$ 表示同一个情况的最小加工时间。转移很简单，随便转就行了。赛时没考虑到状态数量其实很小。。。

这道题还可以用暴搜做，Meet in middle 肯定可以做的，暴搜加点最优性剪枝也可以过。

T3

1. Statement

有 $n$ 个位置，$m$ 个人，每个人加入时会走进离其他人最远的位置，如果有多个，则进入编号最小的。现在有 $2 \times m$ 个事件，每个事件代表一个编号。当这个编号第一次出现时，代表这个人加入了位置。第二次出现时，代表这个人离开了位置。求每个人加入时他走进的位置。

2. 赛时

一眼 set 维护直接秒了。维护两个 set，分别代表点集和所有的区间。加入操作时，相当于找到在点集中找到前驱后继，删除大区间，加入两个小区间。删除操作时，相当于在点集中找到前驱后继，删掉两个小区间，加入大区间。

另外注意还要考虑两边的情况。细节有点多，90 多行代码调了 1h。

T4

1. Statement

给定一个 $n$ 点 $m$ 边的带边权无向图。现在你要设计一条路线（可以重复经过点和边），要求要按顺序经过给定的 $k$ 个点，且路线一定要在 MST 上。经过一个点时时间加上 $t0$（起点终点不算），经过一条边时时间加上边权 $w_i$，求满足要求的最短时间。

2. 赛时

时间不够了……

Lca 板题，建个最小生成树直接查就行了。很抽象的题目，不知道为什么要放 T4。

10.6

150。

比赛界面

T1

1. Statement

给定一条线段的两个端点和一个半径为 $r$ 的圆和它的圆心，保证线段和圆不相交。分别求出线段上任意一点到圆上任意一点的最小距离的最大距离。

2. 赛时

光是理解题目就花了 20min。先考虑 $r=0$ 的情况，就是求出线段到点的距离。有很多种求法，赛时真的有点懵了，尝试了一下计算几何发现忘得差不多了。函数法也不好求，最后有点急了，只好写了个三分莽过去。

3. 赛后

其实真的有很多种方法求。考虑 $r \not= 0$ 的情况，实际上最短距离就是到圆心的距离减去 $r$（显然），而最长距离就是到圆心的最长距离加上 $r$。

T2

1. Statement

有 $m$ 个红绿灯，每个红绿灯只有在 $a_i$ 的若干倍时刻才会亮绿灯。从一个红绿灯到下一个红绿灯的时间不计。求出从时刻 $1 \sim n$ 出发的到达终点的时间。

2. 赛时

各种子问题全部写完用不了多久，有 70pt。看到随机数据决定觉得时间复杂度有点玄学。发现可以维护一个把若干个点合并成区间，但是怕过不了，一直在想没那么玄学的思路，反而浪费了思考下面几道题的机会。

3. 赛后

还有一个优化：当操作的数是 $\gcd_{i=1}^{n} a_i$ 的因数时，这次操作没有意义。加上之后基本就能过了。

T3

1. Statement

给定可重集 $S$，定义 $F_0(S) = [\sum_{x \in S} x = M]$ 以及 $F_k(S) = \sum_{T \subseteq S} F_{k−1} (T)(k > 0)$。给定 $M$ 和 $k$，求 $F_k(S)$。

2. 赛时

心态有点炸了，有点懵。发现是背包，且答案一定要快速求出与 $k$ 有关的部分。但是看到式子推了好久推不出来。。。

3. 赛后

设 $F_0(T) = 1$，则它对答案的贡献为 $k^{|S| - |T|}$。然后 60pt 暴力背包就出来了。发现可以把长度这一维优化掉，可以通过逆元来转移，也可以重新设计状态直接变成 $f_{i,j} = k \times f_{i-1,j} + f_{i-1, j-a_i}$。

T4

1. Statement

给定长度为 $n$ 的双元组 $a$，$a_i$ 包含种类和稳定程度。定义选出 $k$ 种不同种类的 $a_i$ 的价值为将这些双元组的稳定程度排序后最小的相邻两项的稳定程度之差。求出最大的价值。

2. 赛时

二分答案 + 检验。额，然后就卡在这里不知道怎么做了，由于种类数量太大，不可以状压。

3. 赛后

其实最近经常遇到这类的题，就是值的值域特别大不好维护，或者数据范围特别大，不好做。这就可以用随机化这种技巧。就像这道题，可以把每个 $a$ 的颜色赋值成 $1\sim k$ 中的随机数，跑一遍状压，发现答案只会更劣，且取到最优答案的概率大约在 $3\%$ 左右，因此跑 $200$ 遍取 $\max$ 就行了。

但是题目还没有结束。这时候发现时间复杂度会直接爆炸。第一种做法是对 $n$ 进行分段处理，$n$ 越小，跑二分的次数就越大。第二种做法是对状压状态再进行状压，因为 $2 ^ k$ 最大只有 $32$，因此可以用 unsigned int 存，转移优化成 $\operatorname{O}(1)$。

心声

从开始集训到今天，每一场比赛都脱离了我的掌控。比赛结果也不尽人意。

我赛时思维真的很混乱，想题的时间反而比做题的时间长，而且写一道题正确率很低，要么要调很久，要么赛后要挂分。现在真的是到低谷了，思维跟不上，算法也不怎么会，心态爆炸，做题能力不行。就算我赛后听懂了题目的做法，但是我还是不能保证我在第二天的比赛时能调整状态做出来同样类型的题。

我想要提升自己的能力，但是我不知道从哪里开始补起。时间很紧张，三周不到的时间就要复赛了，还要赶文化课，呵。。。

迷茫

10.7

40 + 0 + 55 + 0 = 95

比赛界面

T1

1. Statement

有一些三元组 $(a,b,c)$，满足 $a \in [1, A], b \in [1, B], c \in [1, C]$，定义一个三元组小于等于另一个三元组当且仅当第一个三元组的每个元素都小于等于第二个三元组的对应元素。有 $n$ 次操作，每次操作给定一个三元组，把所有小于等于给定三元组的三元组全部删掉。求 $n$ 此操作一共删掉多少三元组。

2. 赛时

看到题目心态爆炸，没有一点正解的思路。看了一会只发现数据一定满足给定三元组一定是 $(A, ?, ?)$ 或者 $(?, B, ?)$ 或者 $(?, ?, C)$。然后思考了很久容斥，都没有思路，只能开后面的题。

回过头来看题，发现二维的情况非常好处理，单调栈可以直接解决。打满了暴力之后才发现三元组可以联想到坐标轴上的 $x,y,z$。但是这时已经有点急了，推不出来正解。

3. 赛后

其实可以枚举切面。假设枚举的是 $z$ 轴上的切面，发现对于 $C$ 固定的三元组就转换成了二维的问题。处理完是一个类似于阶梯的形状。对于 $A$ 固定的三元组从侧面看也是一个阶梯，转换到切面就变成了把所有 $y \le val$ 的位置切掉，这里 $val$ 指对应的侧面的高度。同理，$B$ 固定的就变成了把所有 $x \le val$ 的位置切掉。发现 $x,y$ 这两根线具有单调性，可以用双指针维护。

T2

1. Statement

$n$ 个物品要经过 $n-1$ 道工序。对于每个工序来说，如果此处只剩下一个物品，就必定将它排除。否则按照编号从小到大的概率考虑，对于每个物品有 $p_i$ 的概率将它排除，然后把剩下所有物品全部传给下一道工序；有 $1 - p_i$ 的概率把它留给下一道工序。显然，最后只会留下一个物品，求出最后一个物品的编号的期望。

2. 赛时

时间不太够了，60pt 的状压期望 DP 没时间写了。

3. 赛后

期望 DP 有一个显然的优化技巧就是分类分组，合并具有相同性质的状态。这道题就类似，可以枚举最后的编号，然后算出它的概率。DP 的时候所有的物品就分成了三组：编号小于它的物品，它自己，编号大于它的物品。设 $f_{i,j}$ 表示考虑了前 $i$ 个物品，当前枚举物品的排名为 $j$ 的概率。

\[f_{i,j} = f_{i-1,j} \times (1 - p_{i-1}) ^ j + f_{i-1,j+1} \times (1 - (1 - p_{i-1})^j) \]

T3

1. Statement

给定长度为 $n$ 的数组 $a$ 和 $b$，找到最大的正整数 $k$，满足序列中存在长度为 $k$ 的子段，使得这个子段中出现的所有数的出现次数 $\ge b_k$。

2. 赛时

信息太多啦，脑子有点乱。首先观察到 $b$ 单调递减，尝试二分发现不可做。尝试枚举 $l,r$ 然后优化，想了挺久发现依然不可做。尝试枚举 $k$ 然后检验，依然不可做。观察 $b$ 的单调性以为可以优化时间，避免不必要的枚举，想了挺久依然没有思路，打了暴力会过去做 A。

3. 赛后

首先观察到一个性质：对于一个任意不成立的子段，这个子段的子段也一定不成立。这个性质的本质是：如果在一个子段内一个数的出现次数小于 $b_k$，那么对于这个子段的子段来说，它的 $b$ 只可能越来越大，就更不可能合法，这其实就是 $b$ 单调性引出的性质。根据这个性质，很自然的就会想到分治做法，但是单纯分治的时间复杂度是 $\operatorname{O}(n \sqrt{n})$ 的，因此需要优化。

显然这个分治的瓶颈的一个重要因素就是分成了太多的区间，发现只要找到任意一个不合法位置的把区间分成两部分就行了，发现并不能做到每次都把区间分成均匀的两部分，因此要换一种思路去优化。

考虑启发式合并，只要每次分治的时间复杂度都为 $\operatorname{O}(\min(mid-l,r-mid))$，时间复杂度就是对的。显然可以实现，只需要找到最短的一个段，然后把它分成两部分分治就行了。

但是最短的一个段不一定在一侧，所以需要用双指针（Meet in middle）的思想来做。

还没有结束。在分治的过程中还需要维护 $cnt$ 数组，记录每个数的出现次数。只需要先把小区间的数删掉，然后分治大区间，再把小区间的数加上，分治小区间就行了。注意在无法分的区间还需要把这一段的 $cnt$ 清空。

T4

1. Statement

给定长度为 $n$ 的数组 $b$，满足 $\forall i \in [1,n], b_i \in [0, m]$，若 $b_i = 0$，则表示 $b_i$ 的值在 $[1,m]$ 中均匀随机。定义 $f(l,r)$ 表示 $b_l \sim b_r$ 这一段区间中的所有极长相等子段长度的平方和。

现在有 $q$ 次操作，每次操作要么把 $b_x$ 修改成 $y$，要么查询 $f(l,r)$ 的值。