2024宁波大学程序设计竞赛题解

A. 哈喽蘑菇

定位

入门题

思路

按照题目要求输出“NBUCPC”

B. Love You Guys

定位

入门题

说明

原本数据范围在 $10^{16}$ 范围，以下题解针对该范围，而对于化简后的范围，直接暴力解决即可。另外，好好学编译原理不会挂科。

思路

题意

给一个 $x$ ， $y$ ，依次进行若干***作：对于第 $i$ 次操作，依次进行两个动作，（1） $x=x-f(i),f(i)=a + b\times(i-1)$ （2） $x=x+y$ ，但 $x$ 不会超过最初的值（记为 $X$ ）。

求一个最小的 $i$ 使得第 $i$ 次操作后 $x <0$ 。

$x,y,a,b\in[1,10^{6}]$

解法

若 $x\le y$ ，则前面的几次操作时 $f(i)$ 不会很大， $x$ 保持不变，均为最初的值 $X$ ，直到有一次 $X-f(i)+y <0$ ，才会将 $x$ 减负值，故只需要求 $X-a-b\times(i-1)+y<0,b\times(i-1)>X+y-a$ ，即 $i> \frac{X+y-a}{b}+1,$ 则 $i$ 最小为 $\lfloor\frac{X + y -a}{b} \rfloor + 2$ 。

若 $x> y$ ，由于 $f(i)$ 单调递增，那么同理，前几个 $i$ 不会使得 $x$ 发生变化，一直是初值 $X$ ，确定第一个操作时刻 $i'$ ，满足在 $i'$ 操作后， $x$ 无法通过步骤（2）到达最初值 $X$ ，即 $X-f(i')+y< X$ ，即 $f(i')>y$ ，即 $a+b\times(i'-1)>y,i'>\frac{y-a}{b}+1$ ，则 $i'=\lfloor \frac{y-a}{b} \rfloor +2$ ，此时的 $x’=X-f(i')+y$ 。设在 $i'$ 时刻的基础上，在经过 $j$ 时刻，使得在 $i'+j$ 时刻使 $x'$ 变为负数，即 $x'-\sum_{i=i'+1}^{i'+j} f(i)+j\times y < 0$ ，确定一个最小满足上式的 $j'$ 即可，这是一个单调函数，可以直接求解或者使用二分法找到最终 $j'$ 。最终答案为 $i'+j'$ 。

$\sum_{i=i'+1}^{i'+j} f(i)=(a+b\times(i'))+(a+b\times(i'+1))+...+(a+b\times(i'+j-1))\\<br />=\frac{b\times(i'+i'+j-1)\times j}{2}+j\times a$

注意特判，例如第一天直接挂科的情况。

C. 游戏开发部的小游戏

定位

困难题

思路

考虑DP解决这道题。

我们定义状态为 $f_{i,j}$ 为当前已经分配到了 $i$ 个石头一组，且已经分配了 $j$ 个石头。则我们可以得到转移状态为：

$\sum_{k = c_i}^{d_i}f_{i, j} = (f_{i, j} + f_{i - 1, j - k \times i} \times \binom{n - j +k\times i}{k \times i}) \times pre_{i, k})$

这里我们定义 $g_{i,k}$ 为分配 $k$ 个石头，且 $i$ 个为一组的方案数，可以注意到，这个 $pre_{i, k}$ 可以用调和级数的做法算出来。

$pre_{i, j} = \frac{\prod_{k = 0}^{i \times j - k \times i > 0} \binom{i \times j - k \times i}{i}}{j!}$

答案即为 $f_{n,n}$

D. 爱丽丝，来扫除啦！（Easy Version）

定位

简单题

思路

若一个点的坐标为 $(x, y)$ ,我们可以简单的将其转换成 $(\frac{x}{\gcd(x, y)}, \frac{y}{\gcd(x, y)})$ ,用std::map<std::pair<int,int>, int>>来记录点对的数量即可，需要注意 $(0, 0)$ 的点会被射线所包含。

E. 爱丽丝，来扫除啦！（Hard Version）

定位

困难题

思路

可以注意到，这道题的范围是 $n \leq 100$ ,所以可以 $O(n ^{2})$ 去枚举点对，注意到，若在某个时刻 $t$ ，两个点的坐标分别为 $(x_1, y_1), (x_2, y_2)$ ，两个点可以在同一个射线上，我们令向量 $\overrightarrow{v_1}=(x_1 + u_1 \times t, y_1 + v_1 \times t)$ ， $\overrightarrow{v_2} = (x_2 + u_2 \times t, y_2 + v_2 \times t)$ ，当前仅当 $\overrightarrow{v_1} \times \overrightarrow{v_2} = 0$ 且 $\overrightarrow{v_1} \cdot \overrightarrow{v_2} > 0$ 。根据上式可以列出一个一元二次方程组，如果无解，不需要考虑这种情况。一解和两解是等价的，如果有无穷多解，一个简单的做法是直接令 $t = 10^9$ ，找到解之后，对于其它所有的点，计算其在相应的 $t$ 的情况下的位置，判断有多少个在一条射线上即可。

F. 奇数Alice，偶数Bob

定位

中等题

思路

可以注意到，若n为奇数，则先手只需要将任意一个石头拿空，即可必胜。

如果n为偶数，则需判断最小值的数量，在最小值是奇数的情况下，先手是必胜的，否则后手必胜。

来自验题人的思考过程

如果有一堆石子变成了0，那么剩下的操作每次都只能拿走一整堆石头这样就只需要看非0的石头堆数了。

如果有奇数堆的石头，那么Yukimi可以先手把其中一堆变成0，这样剩下偶数堆非0的石头堆，LCF必败。

如果有偶数堆的石头,且有一堆的数目为1，Yukimi必不能先把一堆拿完，否则就鸡了,那么Yukimi只能考虑将目前非1的石头堆掌成1，偶数堆的局面留给LCF，LCF也是一样的操作。比如1 1 3 4。

首先Yukimi操作变成1 1 1 4或者1 1 3 1，LCF操作变成1 1 1 1，随后局面就确定了那么相当于:最小是1的偶数堆情况下，有奇数堆非1的，Yumiki必胜，反之LCF必胜。

如果偶数堆所有的石头堆都大于1，Yumiki不能将某一堆石头变成1，这样的话会把奇数堆非1必胜的局面留给LCF相当于谁先把某一堆石头变成1他就必败了，因此都要去避免这个局面。那么也就只能是，尽可能把非最小石头堆变成最小石头堆，最后变成所有堆石头一样的局面。接下来只需要考虑所有石头堆数一样，但是非1的情况了如果这时候都是2，那么就会遇到必败局面；把一堆石头变成1，局面也确定了如果都是3，必定先变成一个2，总共偶数次操作变成全2仍为必败态。由此可以判定:如果所有数都一样，肯定是必败态那么就需要看怎么能到达这个局面了,很显然就是数和最小值不一样的个数，这与前面有1的情况一样。

G. 黑天鹅的记忆解析

定位

中等题

思路

涉及知识点：字符串处理、动态规划、深度优先搜索

方法一（动态规划）

假设字符串 $S$ 、 $T$ 的长度分别为 $lens$ 、 $lent$ 。可以考虑一下最终的情况： $S$ 的前 $i$ 位已经以某种放入方式放入 $A$ 后， $T$ 成为了 $A$ 的前缀。在这种情况下，我们往前倒推第 $i$ 位是怎么放的。有两个情况：

* $S$ 的第 $i$ 位放到了 $A$ 的开头处
* $S$ 的第 $i$ 位放到了 $A$ 的结尾处

对于第一种情况，说明了在第 $i$ 位放入前， $S[1 ...i−1]$ 构成了 $T[1 ...lent-1]$ ；

对于第二种情况，说明了在第 $i$ 位放入前， $S[1 ...i−1]$ 构成了 $T[2 ...lent]$ 。

同理，可以继续往前推第 $i-1$ 位是怎么放的、第 $i-2$ 位是怎么放的、第 $i-3$ 位是怎么放的等等，这里就不一一列举了。可以发现在考虑第 $j$ 位如何放入的时候， $S[1 ...i−1]$ 必然构成了 $T[l ...r]$ 。

由此可以用区间DP来解决这道题，设 $f[i][j]$ 表示使得 $S[1 ...j-i+1]$ 能构成 $T[i...j]$ 的方案数。转移方程如下：
$f[i][i]=2\space\space if \space (t[i]==s[1]) \\<br />f[i][j]=f[i][j]+f[i+1][j]\space\space\space if \space (t[i]==s[j-i+1]) \\<br />f[i][j]=f[i][j]+f[i][j-1]\space\space\space if \space (t[j]==s[j-i+1])$
答案就是 $f[1][lent]$ ，时间复杂度为 $O(n^2)$

方法二（深度优先搜索）

考虑使用深度优先搜索算法，从一个空字符串开始，每次往开头或者结尾处放字符，当该字符串和T的长度相同时则停止添加字符串，并比较两个字符串是否相同。若相同，则答案+1。

H. 后缀0

定位

简单题

思路

知识点：数学

$\begin{aligned} 1+\sum_{i=1}^{N}(i \times i!) &=1+1 \times 1! + 2 \times 2! + \dots + N \times N! \\ &=2!+2 \times 2! +3 \times 3!+ \dots +N \times N! \\ &=3 \times 2!+3 \times 3!+ \dots + N \times N! \\ &=3!+3 \times 3!+ \dots +N \times N! \\ &= \dots \\ &=(N+1)! \end{aligned}$

于是问题转化为求 (N+1)! 末尾 0 的个数，这是一个经典的问题，该个数取决于因子中 5 的个数。

I. 小Y.的魔法书

定位

中等题

思路

Y.？why not？

其实原题是组合数学，但是由于数据的范围比较小，因此可以考虑dp。

如何描述一种可能的情况，我们使用最后一个子串的位置，考虑最后一个子串的符合的条件，假设残缺的咒语是" $ab$ ",假设完整字符串的前 $i$ 个和残缺咒语的前 $j$ 个匹配上，前 $i+k$ 个和残缺咒语的前 $j+1$ 个匹配上，那么完整字符串的第 $i$ 个到第 $i+k$ 个中间不能出现残缺咒语的第 $j$ 个字符。再考虑括号匹配，我们可以增加一维dp记录括号匹配的情况。

设 $dp[i][j][k]$ 表示前 $i$ 个完整咒语和前 $j$ 个残缺咒语匹配，且左括号数比右括号数多 $k$ 个，转移方程代码如下, $s$ 表示残缺咒语。

//当前位置放 ( 
if(j>=1&&s[j]=='('&&k>=1)f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1])%mod;
//当前位置放 )
if(j> =1&&s[j]==')') f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
//当前位置放 (
if(k>=1&&(j==0||s[j]!='('))f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod;
//当前位置放 )
if(j==0||s[j]!=')')f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
//当前位置放字母 
if(s[j]=='('||s[j]==')'||j==0) f[i][j][k]=(f[i][j][k]+f[i-1][j][k] * 26 % mod)%mod;
else f[i][j][k]=(f[i][j][k] + f[i-1][j-1][k] + f[i-1][j][k] * 25 % mod )%mod;

J. 不确定的排列

定位

中等题

思路

题目保证给定的数据没有矛盾，考虑图模型，将一对 $a_u>a_v$ 视作从 $u$ 到 $v$ 有一条有向边，因此给定的图是DAG。

二分答案，考虑二分前 $k$ 个不等式，需要判定这 $k$ 个不等式能否确定一个唯一的排列，重新将这 $k$ 条边进行组合得到一个新图，在该图上进行拓扑排序。若出现某一时刻，同时存在大于1个入度为0的节点，则必定无法确定这两个节点所对应的变量的大小，若拓扑排序的过程中，每个时刻都只有一个入度为0的节点，则必定能够确定排列。

在确定排列的情况下，重新进行一次拓扑排序，能够知道所有节点的大小关系，确定唯一排列即可。

K. 五彩斑斓的世界

定位

困难题

思路

知识点：栈、括号匹配

对每种颜色 $C_i$ 进行考虑，记颜色 $C_i$ 出现的次数为 $cnt$ ，有以下 $4$ 种情况：
1、 $cnt=1$ ，此时没有连线，无影响。
2、 $cnt=2$ ，可能有交点。
3、 $cnt=3$ ，可能有交点。
4、 $cnt \geq 4$ ，一定有交点，直接输出"Yes"。

所以只需要对所有 $cnt=2$ 和 $cnt=3$ 的情况进行考虑。

先考虑 $cnt=2$ ，把正多边形拆成一条线，对于每 $2$ 个相同的颜色相当于括号()，于是整个序列就可以转化成括号序列，问题就转化成求括号匹配是否合法，如果括号序列不合法则有交点，这可以用栈来实现判断。

然后考虑 $cnt=3$ ，可以在不影响连线的条件下，把 $3$ 个相同的颜色拆成 $3$ 种不同的颜色，每种颜色的数量为 $2$ ，例如" $\dots X \dots X \dots X \dots$ "，我们可以拆成" $\dots XY \dots YZ \dots ZX \dots$ "，于是转化成了 $cnt=2$ 的情况。