2021 BUPT Welcome Wagon 题目集锦
Contest 2
B
题意
构造出一个树，使得直径数量恰为 $k$，且节点数最少。
多次询问。
$q,n\le 500$。
题解
考虑树的重心，分类讨论：
重心在边上，左边挂 $x$ 个点，右边挂 $y$ 个点，此时能构造出 $x\times y$ 的形式，总点数 $x+y+2$。
重心在点上，且为是菊花图的形式，此时能构造出 $x*(x-1)$ 的形式，总点数 $x+1$。
重心在点上，但不为菊花图。可以发现，若以重心为根，最优方案中重心的若干子树一定是一个菊花图的形式（也就是连一个点，然后这个点连出去若干条边）。若对于每个子树中，叶节点个数为 $a_i$，则能构造出 $\sum_{1\le i < j\le m}a_ia_j$。总点数为 $1+m+\sum a_i$。
前两种都非常好求，对于第三种，考虑DP，设 $f_{i,j}$ 表示构造出总数为 $i$ 的方案，且 $\sum a_k=j$ 时的最小点数。初始时 $f_{0,i}=2+i$。
枚举下一个子树选什么，类似背包的转移，并记录从上一个位置方便输出方案。
三种做法取一个最小值。
时间复杂度 $O(n^2\log n+q\log n)$。
C
题意
给定 $n$ 个物品，重量为 $a_i$，价值为 $w_i$。
$m$ 次询问，每次给定一个 $q_i$，求选出若干物品（可重复选）使得物品重量之和为 $q_i$，且价值和最小。
输出价值和对 $10^9+7$ 取模后的结果。
$n\le 100,a_i\le 100,m\le 10^6,q_i\le 10^{18}$。
题解
显然是个完全背包，但是 $q_i$ 极大。
设 $c=\max_{i=1}^n {a_i}$。
如果存在某个数组 $b$ 表示每个物品取出的次数，使得 $q=\sum_{i=1}^na_ib_i$。那么对于每个 $j$，都可以通过调整 $b$，使得存在 $\sum_{i=1}^na_ib’i=q$ 且 $\sum{i\neq j}a_ib’_i< n a_j^2$。
证明：若 $b’_i\geq a_j$，则可以将 $b’_i$ 减去 $a_j$。
也就是说，最终的 $b’i$ 都是小于 $a_j$ 的。那么 $\sum{i\neq j}a_ib’i<\sum{i=1,i\neq j}^na_ia_j \leq n c^2$。
可以发现，$nc^2$ 是 $10^6$ 级别的。
当 $q_i$ 大过 $nc^2$ 时，通过贪心，找到 $\frac{w_i}{a_i}$ 的最小值，一直选这个，直到 $q_i<nc^2$，然后通过预处理 $nc^2$ 以内的背包来找到最小值。
时间复杂度 $O(n^2c^2+q)$。
G
题意
给定 $7\times n$ 的网格，你需要在上面填进 $k$ 个L型的网格（共3个格子），以及 $7n-3k$ 个 $1\times 1$ 的格子。
有 $m$ 个格子不能填 $1\times 1$ 的格子进去。问合法的方案数对 $10^9+33$ 取模后结果。
$n\le 100,7n-20\le 3k\le 7n,m\le 7n$。时限4s。
题解
口胡一下，还没写。
设 $f_{i,j,k}$ 表示搞到第 $i$ 列且第 $i$ 列目前的状态（是否填了格子进去）为 $j$，一共用了 $k$ 个 $1\times 1$ 的方案数。
时间复杂度 $O(2^{14}nk’^2)$，其中 $k’=7n-3k$。
Contest 3
B
题源
题解
首先，对于每个连通块，只有一个入度为 $0$ 的点。只有这个点以及只与这个点相连的点才有可能成为第二大的。
于是其他点可以完全删掉。剩下 $m$ 个类似于菊花图的东西。
而这 $m$ 个连通块至少要通过 $m-1$ 次询问才能确定谁最大，从而确定次大值。
贪心，维护菊花图的大小，从小到大将最小的两个大小为 $x,y$ 的菊花合并为 $y+1$ 即可。
时间复杂度 $O(\sum (n+m))$。
G
题源
题意
给定一个字符串 $|S|$，对于每个 $i(1\le i \le |S|)$，求出其某个长度为 $i$ 的子串的出现次数的最大值。
$|S|\le 2\times 10^5$。
题解
搞完题意发现有点简单，不管了
直接建出SAM，拓扑排序后对每个节点算出出现次数，SAM中的一个节点代表的是若干长度连续的字符串。然后求个后缀最大值就可以了。
时间复杂度 $O(|S|\Sigma )$。
SA做法？
H
题意
给定一个 $n\times m$ 的格子。格子上写着 $0\sim 9$ 的数字，在上面任选起点，上下左右可多次经过同一个格子地走行程一个数字。问最小的无法走出的正整数。
$n,m\le 100$。
题解
设这个最小的正整数位数为 $x$，需要满足 $nm\times 4^{x-1}\geq 10^x$，解得 $x\le 8$。
于是只需最多走 $8$ 次，然后判断即可。
时间复杂度 $O(nm\times 4^{7})$。
Contest 4
F
题意
定义与两个字符串 $S,T$ 相关的函数 $f(S,T)$ 为它们最长公共子串的长度。
给定 $n$ 个字符串，多次询问两个字符串间的 $f$ 值。
$n\le 50000,q\le 10^5,\sum |s_i|\le 10^5$。
题解
如何求 $f$ ？
对于某个串建出SAM后，另一个串在上面跑匹配即可。
每次询问都去建出后缀自动机？
显然不可能。
设字符串总长为 $k$ 。考虑设定阈值 $L$，并对询问离线。
对于 $|s_i|$ 都 大于 $ L$ 的询问一共最多只有 $\frac{k^2}{L^2}$ 种。找到匹配时暴力跑SAM，时间复杂度 $O(\frac{k^2}{L})$。
对于存在 $|s_i|<L$ 的询问，用短串在长串的SAM上匹配。这样每个串只用建一次SAM，每次询问都要花短串长度的时间。时间复杂度 $O(mL)$。
取 $L=\sqrt{k}$，时间复杂度 $O(k^{1.5}+mk^{0.5})$。
G
题意
给定 $n(n \le 3\times 10^6)$，问 $\sin(x)+\sin(y)+\sin(z)$ 的最大值，其中 $x,y,z$ 均为正整数且 $x+y+z=n$。
题解
显然先把 $z$ 换了，变成求 $\sin(x)+\sin(y)+\sin(n-(x+y))$ 的最大值。
第三个 $\sin$ 中的 $x+y$ 启发我们对 $\sin(x)+\sin(y)$ 进行和差化积的变换：
$$
\sin(x)+\sin(y)=2\sin(\frac{x+y}{2})\cos(\frac{x-y}{2})
$$
枚举 $x+y=k$，变成求 $\cos(\frac{k-2y}{2})$ 的最大值。
对 $k$ 的奇偶性分类讨论，作前缀最大值即可。
时间复杂度 $O(n)$。
Contest 5
G
题源
Codeforces570D
题意
一棵以 $1$ 为根的有根树，每个节点上有一个小写字母。
多次询问某个子树中，将所有深度 $=k$ 的节点的字母，是否能通过随意组合形成回文串？
$n,q\le 5\times 10^5$。
题解
首先一定要解决的问题是：如何判断若干字母是否能形成回文串？
显然，这个问题等价于最多有一个字母的出现次数为奇数。
于是，用二进制的某一位表示每个字母的出现次数模二的结果，变成若干个数异或后，判断是否是 $2^i$ 或 $0$。
对树：算出dfs序，以及每个子树的节点的dfs序区间。
对于每一层，开一个vector，按dfs序存节点进去。
每次询问二分找到相应层数对应的dfs序区间，通过预处理出前缀异或和 $O(1)$ 判断能否组成回文串。
时间复杂度 $O((n+q)\log n)$。
H
题源
Codeforces704B
题意
$n$ 个点排成一列，从 $s$ 出发，到 $t$ 结束，每个点必须且只经过一次。
从 $i$ 到 $j$ 的花费为：
- 若 $i>j$ ，则为 $x_j-x_i+d_i+a_i$；
- 若 $i<j$ ，则为 $x_i-x_j+c_i+b_j$ 。
求最小花费。
$n\le 5000$。
题解
有一种超级厉害的贪心方法，可是不会啊QAQ。
考虑十分经典的DP，设 $f_{i,j}$ 表示考虑前 $i$ 个点时，向右伸出去多少条链时的最小花费。
但这个链是有方向的呀，难道不用处理方向吗？
是的没错，就是不用处理，因为不同方向的链的数量的差不会超过 $2$，且这个差跟起点终点有很大关系。
于是只需要考虑每个点如何转移。
有四种情况：
- 合并一条出去和另一条回来的链。
- 多出一条出去和回来的两条链。
- 延伸一条出去的链。
- 延伸一条回来的链。
大力分类讨论，并注意特殊情况即可。
起点终点需要特判。
时间复杂度 $O(n^2)$。
程序
1 |
|
I
题源
Codeforces286E
题意
给定 $n$ 个数 $a_1,a_2,\cdots a_n$，以及 $m$ 。求一个长度最小的序列 $b_1,b_2,\cdots,b_k$，使得对于每个 $a_i$，都能在序列中找到若干个数（能多次选同一个数）相加等于它；且从 $b$ 中选出若干个加起来不超过 $m$ 的数（能多次选同一个数），这些数的和在 $a_i$ 中。
若无解，输出 $-1$。
$n,m,a_i\le 10^6$。
题解
将 $a$ 从小到大排序后可以发现，$b$ 中一定要有 $a$ 最小的那个数。
如果有 $a_i$ 等于若干 $b$ 的和，则这里面最小的 $b_i$ 一定是某个 $a$。那么 $a_i-b_{min}$ 也就是其他 $b$ 的和也要是某个 $a_i$，否则就违反了限制。
因此，$b_i$ 中全是 $a$ 序列中的数。显然，将整个 $a$ 序列全选上去最有可能有解。
如何判断无解？也就是存在某两个 $i,j$ 使得 $a_i+a_j$ 不在序列 $a$ 中？
FFT搞一搞即可。
如何找到最优解？
显然，如果对于某个 $a_k$，使得不存在 $a_i+a_j=a_k$ 的，这个 $a_k$ 就要选了。
于是就做完了，只需跑一遍FFT。
时间复杂度 $O(n+m\log m)$。
Contest 6
I
题源
题意
空字符串，每次有 $p$ 概率在后面加一个 a，有 $1-p$ 概率加一个 b，问第一次 ab 出现该字符串的子序列中次数 $\geq k$ 的期望时间，对 $10^9+7$ 取模。
$k\le 1000$。
题解
设 $f_{i,j}$ 表示字符串中一共 $i$ 个 a，且 ab 出现了 $j$ 次时的概率。
DP一下即可。
边界条件为 $i+j\geq k$，此时再加一个 b就会超过 $k$ 个，于是求个等比数列什么的就可以了。
时间复杂度 $O(n^2)$。
Contest 8
H
题源
题解
显然，第一个人只会选一个话题。
枚举选了哪个话题，然后看有哪些话题能被这个话题所到达。
传递闭包。
时间复杂度 $O(\frac{n^3}{w})$。
Contest 9
2019ICPC南京站。
B
题源
题解
显然，最近的距离就是曼哈顿距离。
考虑现在已经走完了一个 $a\times b$ 大小的矩形，且当前位置在矩形的顶点上。
由于题目的限制，可以知道此时如果在当前的位置走出去一个，开出了新的一行或一列，那么之后就一定要马上填完这一行或一列，否则就不合法了。
于是相当于从一个 $1\times 1$ 的矩阵向外扩展到 $n\times m$。每次可以使行数或列数+1，问方案数。
答案即为 $4\times \binom{n+m-2}{n-1}$。乘 $4$ 是因为刚开始有四个方向。
J
题源
题解
KM算法模板题，然而刚开始写了个假的 $O(n^4)$ 的KM，需要用bfs才能保证其正确性。
Contest 10
E
题意
给出字符串 $s,t$，求满足 $1\le i \le j \le |s|,1\le k \le |t|,j-i+1 > k$，且 $s[i,j]+t[1,k]$ 为为回文串的 $(i,j,k)$ 对数。
$1\le |t| \le |s| \le 10^6$。
题解
由于 $j-i+1 > k$，有 $s[i+k,j]$ 是回文串。
于是枚举 $i+k$ 的位置 $l$，变成统计有多少个 $x$ 满足 $s[x,l-1]$ 的反串为 $t$ 的前缀，有多少个 $y$ 满足 $s[l,y]$ 为回文串。
分成两部分，第一部分是扩展KMP模板，也可以二分+hash或SAM或SA；第二部分是manacher模板，也可以二分+hash或PAM。
大概可以有 $4\times 3=12$ 种不同的做法。
F
详见：“Tournament”
Contest 12
A
题意
给定 $L,R,k$，求最大的 $j-i+1$，使得 $L\le i \le j \le R$，且 $[i,j]$ 间的整数的异或和 $\le k$。
$T\le 5\times 10^5,L,R\le 10^{18}$。
题解
显然，$4x,4x+1,4x+2,4x+3$ 的异或和为 $0$。
于是整 $4$ 的倍数段的都可以。剩下的暴力枚举就可以了。
时间复杂度 $O(16T)$。
C
题意
给定 $[L,R]$，判断是否满足 $\frac{\sum_{i=L}^{R}[i\in \mathbb{P}]}{R-L+1}<\frac{1}{3}$。
$T\le 100,L,R\le 10^9$。
题解
$n$ 以内质数个数约为 $\frac{n}{\ln n}$ 级别。当 $[L,R]$ 越大，越难满足。
于是当 $R-L+1\geq K$ 的时候直接输出 No，剩下的用区间筛判断一下就好。
$K$ 取 $10^4$ 就可以了。
或许也可以直接跑Min-25筛？
E
题意
求最大的 $i$，满足 $X^i\prod_{j=1}^na_j!$ 为 $Y!$ 的约数。
$\sum a_i\le Y \le 10^{18},X\le 10^{18}$。
题解
对 $X$ 进行质因数分解后，对每个质因数的项 $p^k$，算出最大的 $x$，满足 $p^x|\frac{Y!}{\prod_{i=1}^n a_i!}$。那么答案就是 $\min(\lfloor \frac{x}{k} \rfloor)$。
$x$ 十分容易算，于是只需要写个Pollard-rho就好了。
F
直接打表。
打表时间复杂度 $O(200\times 10^8)$。
H
题意
给定一序列，支持单点修改，查询区间的子集的mex，即最小的正整数 $x$，使得不存在在某个区间中选出若干个数的和为 $x$。
$n,q\le 2\times 10^5$，数为正整数。
题解
假设对于某个区间，如何计算这个mex呢？
显然，看区间的mex能否为 $1$，统计出所有 $\le 1$ 的数的和，假设为 $x$，若 $x\geq 1$，则统计所有 $\le x+1$ 的数的和，然后一直下去。
每次统计，$x$ 至少乘二。于是只需求区间小于等于某个数的和。
由于有单点修改，只需写一个树状数组套线段树。
时间复杂度 $O(n\log ^2n+q\log ^3n)$。
J
题意
给定一个 $n$ 个点的完全无向图，将所有的边分成 $n-1$ 条路径，每个边恰在一条路径内，第 $i$ 条路径经过的边数为 $i-1$。
$n\le 10^3$。
题解
当时人傻掉了，以为 $n$ 个点的完全图都存在欧拉路。
当 $n$ 为奇数时，存在欧拉路。
当 $n$ 为偶数时，不存在欧拉路。
最麻烦的显然是长度最长的那些路径。
观察 $n=4$ 时可以发现，$n-1$ 和 $n-2$ 的路径可以通过 $n,n-1$ 号点及其与其他点相连的边的搞出来，然后变成一个 $n-2$ 的子问题。
发现当 $n>4$ 时，$n,n-1$ 号点相连的边一共有 $2(n-2)+1=2n-3$ 条，恰好就是 $(n-1)+(n-2)$，而且也能构造出来。
于是就做完了。
L
Trie上建SAM模板，然后来个parent-tree上倍增定位字符串。注意建SAM一定要bfs建，不然会被卡成 $O(n^2)$。
M
题意
给定一棵有根树，求每棵子树的所有重心。
$n\le 2\times 10^5$。
题解
重心的若干性质：
- 将两棵树拼起来，新树的重心必然是两棵原来的树的重心的最短路径上。
- 对于一棵树，其重心一定是自己，或在其重儿子中。
- 若割掉某个点后，剩下的子树中存在一个大小超过原树的一半，则该点一定不是重心。
于是树剖，考虑重儿子的重心往上跳，直到成为子树的重心。是否继续往上则根据第三条性质。
时间复杂度 $O(n)$。注意可能有多个重心，需要特判。
一棵树存在多个重心当且仅当删掉某条边后树分裂成两棵且大小一样。
Contest 15
A
题意
将 $1\sim n^2$ 填进 $n\times n$ 的矩阵内，记 $|S|=|{a_1,a_2,\cdots,a_n}\or {1,2,\cdots,n}|$，其中 $a_i$ 为矩阵第 $i$ 行的最小值。求所有矩阵的 $|S|$ 的和。
$n\le 5000$。
题解
记 $f_i$ 表示 $i$ 这个数对 $\sum |S|$ 的贡献，即有多少个矩阵满足某一行的最小值为 $i$。
显然有：$f_i=n^2\binom{n^2-n}{i-1}(i-1)!(n^2-i)!$ 。
时间复杂度 $O(n^2+Tn)$。
C
树形DP模板。
D
线段树模板题。
E
$6n$ 即为答案。
G
如果不能填格子，那么显然一定要在前 $i$ 个格子中滑下且这 $i$ 个格子都已经有球。枚举合法方案中最小的下标 $i$ 满足第 $i$ 个格子没有球。那么，前 $i$ 个格子都要有数，且后面的 $n-1-i$ 个格子随便乱放。
设 $g_{i,j}$ 表示长度为 $i-1$ 的格子随便乱放 $j$ 个，没有一个滑下的方案数。
设 $f_{i,j}$ 表示长度为 $i$ 的格子放了 $j$ 个，$1\sim i$ 的格子都放了球的方案数。
需要求出 $f,g$ ，还需要一个 $h_i$ 表示 $i$ 个格子放 $i$ 个球，且没有滑下的方案数。
$f,g$ 的转移枚举第一段，然后转移。
时间复杂度 $O(n^3)-O(n)$。
显然 $f,g$ 的转移是一个卷积的形式，可优化到 $O(n^2\log n)-O(n)$，但完全没必要。
H
显然奇数一定不行。
那么操作就变成 $\times 2,/2,+1,-1$。
利用快速幂的思想，算出从 $1$ 出发向下走的步数 $x$，以及向右走的步数 $y$，
开始先向下走一步变成 $2$，之后每向下一步或向右一步都会 $\times 2$ 变成 $4$，需要经过某些转换转变回 $2$。
显然某种兜一圈的方法可以完成这个操作。
于是就做完了，最多不会超过 $197\times 5+1=986$ 次操作。
I
签到题。
K
边权从大到小排序，然后并查集按秩合并。
M
模拟即可。