前言

先感谢一波，感谢qcjj、出题组、验题组、参赛者。

知识点

模拟、调和级数、二分、贪心、杨辉三角、prim、质数距离、概率、博弈、容斥、组合数、bfs、枚举

难度预估

个人认为整体难度不高。 在兰子评价为创死萌新，我也深刻的感受难度，于是加了DHE。

(感觉还是不好说(Θ﹏Θ))

(希望不会创死人。)

由于预测"阿宁指指点点"可能非常难（正赛中变最难的题了），因此挪到了比较靠后。

预测难度：

（上图题号是内测时的题号）

题解

A. 阿宁的签到题

知识点

一门编程语言 输入输出ifelse应该没啥好讲的

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783227

B. 阿宁的倍数

知识点

因子、判质数、二分

思路1

离线做法

开值域数量那么多的桶。 将输入的数组$aa$的每一个元素的下标扔到对于值的桶（下标$ii$扔到$a_{i}a\_i$的桶），包括修改操作插到数组末尾的数。

两重循环$i,ji,j$，第二重循环$jj$遍历$ii$的倍数，往桶$ii$插入所有桶$jj$的元素。桶$ii$插入完之后，排序一下。 因为一开始桶$ii$的倍数桶$jj$，没有重复元素，所以桶$ii$插入完，也不会有重复元素。 虽然是两重循环，但因为只遍历倍数，复杂度是$O(NlogN)O(NlogN)$。（调和级数）

上面操作完之后，每个桶存就是它的所有倍数的下标（位置），而且是有序的。这样就可以二分在桶中找到下标。

每次询问的具体操作：假设当前询问，数组的长度是$mm$，要询问的位置是$xx$，位置$xx$的值是$pp$（就是$p=a_{x}p=a\_x$）。那么在桶$pp$通过二分查询，找到$xx$和$mm$的位置，假设位置分别是$LL$和$RR$，那么答案就是$R-LR-L$。

（在$2\times 10^{5}2\backslash times\; 10^5$内因子数最多是160。）

代码1

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783872

思路2

在线做法

暴力枚举当前数的因子，在因子的桶$vv$对应位置+1。 并且记录，前缀中有多少个当前数，记在桶$uu$里。 （预处理数组和修改数组都做这事情）

询问时，答案就是这个数的个数，减去前缀这个数的个数，分别在桶$v,uv,u$找到。

代码2

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783845

C. 阿宁的大背包

知识点

杨辉三角 模拟、贪心

思路

预期做法：大家想出/猜出大的放中间、小的放两边，然后模拟，即可通过。

反过来看，将最后一轮的大背包拆解： 第$44$轮用了第$33$轮的背包数量分别是$1,11,1$。 用了第$22$轮的背包数量分别是$1,2,11,2,1$。 用了第$11$轮的背包数量分别是$1,3,3,11,3,3,1$。

刚好对应杨辉三角，初始背包对最终影响的个数，也就是第$nn$层组合数。组合数特点是中间大、两边小，因此让大的背包放到中间，使最终背包更大。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783830

D. 阿宁的毒瘤题

知识点

前缀和

子序列、枚举

思路

首先计算出每个位置的字符，有多少个和它关联"udu"子序列。 明显，"udu"子序列个数最多的字符，把这个字符改掉（改成不是'u'和'd'比较方便），就少了这么多"udu"子序列。

对于字符'd'，它和它两边各找一个的'u'字符，组成"udu"子序列，因此，将左右两边的'u'的数量相乘。 对于字符'u'，它和它左边的"ud"子序列组成"udu"子序列，和右边的"du"子序列组成"udu"子序列。这里通过循环找出来。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783804

E. 阿宁的生成树

知识点

最小生成树（prim）、质数距离 lcm、gcd （有验题人写nlogn的筛...）

思路

考虑prim求最小生成树的过程，节点$11$作为初始连通块。 （对于最终的生成树，把边权存到$d_{j}d\_j$里）

对于一个节点$i(i\ge 2)i(i\backslash ge\; 2)$： ①和节点$11$连边，如果有$lcmlcm$的边，边权是$ii$，否则有一条$gcdgcd$的边权$11$。与节点$11$相连作为保底，使得边权最多不超过$ii$。 ②为了使边权更小，在$gcdgcd$的边权终找到一个权值最小的。

1. 首先将$d_i(i\ge 2)d\_i(i\backslash ge2)$初始化为$ii$。
2. 显然节点$11$和节点$i(i\ge k+2)i(i\backslash ge\; k+2)$连一下，因为有$gcd(i,1)=1gcd(i,1)=1$的边权。
3. 对于节点$j(1\le j\le n-k-1)j(1\backslash le\; j\backslash le\; n-k-1)$，可能在有节点$i(i-j\le k,j\le i)i(i-j\backslash le\; k,j\backslash le\; i)$，$gcd(i,j)gcd(i,j)$更小。这一部分暴力即可，当找到一个$ii$是质数，$d_{j}d\_j$都被更新成了$11$，可以直接break。 这部分的时间复杂度为$O(dist\times n+n\sqrt{n})O(dist\; \backslash times\; n\; +\; n\backslash sqrt\{n\})$，$distdist$是$2\times 10^{5}2\backslash times\; 10^5$以内最大的质数距离，大约$100100$。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783774

F. 阿宁的二进制

知识点

二进制性质、贪心、排序

思路

$f(x)f(x)$就是将$xx$变小（除了$11$）。而且最多$44$次变成$11$。

当整个数组全$11$的时候，就该结束操作了，即便还有操作次数剩余。

对于每次询问，为了使最大值最小，最好就是$kk$次操作都选最大的数变小。

具体做法： 将整个数组都变成$11$中间出现过的数，都存到$bb$数组里面，然后排序。假设$bb$数组的长度是$tt$。 当$k\ge tk\backslash ge\; t$，说明整个数组都变成$11$，直接输出$11$。 否则输出第$k+1k+1$大的数。（前$kk$大的数都变小了）

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783727

G. 阿宁的整数配对

知识点

贪心、数的性质

思路

正数乘以负数结果是负数； 正数乘以正数结果是正数； 负数乘以负数结果是正数。

因此尽量同号的配一对。这里尽量让绝对值大的优先配对。 如果有剩余的正数或负数，则让它们和0先配一对。 最后正负数还有剩余，正负数配一对。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783703

H. 阿宁讨伐虚空

知识点

概率

思路

分类讨论一下就行了。

• $x\le Lx\; \backslash le\; L$时，脆皮都死完了，虚空蛇肯定不会被打到。
• $x>Rx\; \backslash gt\; R$时，脆皮怎么都死不玩，虚空蛇肯定会被打到。
• $L\le x<RL\; \backslash le\; x\; \backslash lt\; R$时，如果$y\in [L,x)y\; \backslash in\; [L,\; x)$，那么脆皮没有死完，区间$[L,x)[L,\; x)$长度是$x-Lx-L$，因此概率是$\frac{x-L}{R-L+1}\backslash frac\; \{x-L\}\{R-L+1\}$。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783680

I. 阿宁前往沙城

upd：看到有对大部分题面描述方式和重边、自环有意见。还有数据弱了（已加强）。 对于题面描述方式，那应该就是我表达能力问题。 感觉重边和自环都是符合题意的，不在题目里写上，我觉得是可以。

知识点

bfs

思路

可以走一条边，将刚走的这一条边毁灭，下一条边的通过时间改为$11$。 因此，除了要走的第一条边，剩下的边通过时间都可以改成$11$。

为了使第一条的通过时间也改成$11$，找到一条多余的边毁灭即可。 为了找到多余的边，从终点开始bfs，所有的边权当作$11$。 如果$11$到$nn$的距离是$m-1m-1$，那么没有多余的边。否则有多余的边。

没有多余的边的情况下，$11$到$nn$的路径就是一条链。于是路径上第一条边只能耗费原来的通过时间。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783624

J. 阿宁指指点点

知识点

模拟、自定义排序

思路

定义一个队列$qq$，按照时间升序排序，同一时刻的事件按照题面要求的顺序排序。

1. 对于每一个类型$11$的事件：①把一个查询放到队列$qq$中；②把时刻$\lfloor \frac{t}{T}\rfloor \times T\backslash lfloor\; \backslash frac\{t\}\{T\}\backslash rfloor\; \backslash times\; T$的更新放到队列$qq$中，$\lfloor \frac{t}{T}\rfloor \times T\backslash lfloor\; \backslash frac\{t\}\{T\}\backslash rfloor\; \backslash times\; T$是在$tt$时刻之前，离$tt$时刻最近的更新；③把时刻$t+Rt\; +R$的更新放到队列$qq$中。
2. 对于每一个类型$11$的事件，把一个题数更新放到队列$qq$中。

$\lfloor x\rfloor \backslash lfloor\; x\; \backslash rfloor$是小于等于$xx$最大整数，比如$\lfloor 23.3\rfloor =23,\lfloor 23\rfloor =23\backslash lfloor\; 23.3\; \backslash rfloor\; =23,\backslash lfloor\; 23\; \backslash rfloor\; =23$。 $\lfloor \frac{t}{T}\rfloor \times T\backslash lfloor\; \backslash frac\{t\}\{T\}\backslash rfloor\; \backslash times\; T$：可以理解为时刻$tt$前面更新了$\lfloor \frac{t}{T}\rfloor +1\backslash lfloor\; \backslash frac\{t\}\{T\}\backslash rfloor+1$次（第一次在时刻$00$），因此前面更新用了$\lfloor \frac{t}{T}\rfloor \times T\backslash lfloor\; \backslash frac\{t\}\{T\}\backslash rfloor\; \backslash times\; T$的时间。

然后使用两个$mapmap$，$count1count1$记录在$propro$的题数，$count2count2$记录在$rankrank$的题数。 把队列$qq$中的每个事件都取出来，再按类型做对应操作（具体可以看代码）。

代码1

priority_queue版： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783323 sort版： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783306 python： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783374

K. 阿宁大战小红

知识点

博弈的必胜态必败态

思路

初始值是$nn$。 因为题目要求不能出现曾经出现的数字，一旦除以$22$下取整，那么必定可以结束游戏。 所以对于第一次除以$22$下取整，需要当前这个人$pp$除以$22$下取整，$pp$一定能赢，否则不如选择加$11$。 可以发现如果一直加$11$，当前变成$2n2n$，就没有除以$22$下取整，只能无限加$11$，平局。

可以定义状态$(x,y,z),y\le x<z(x,y,z),\; y\backslash le\; x\; \backslash lt\; z$，表示当前的数是$xx$，曾经最小是$yy$，最大不能变成$zz$。 对于$(x,y,z)(x,y,z)$，曾经没出现过的数区间是$[1,y)\cup (x,z)[1,y)\; \backslash cup(x,\; z)$。加$11$操作不能达到$zz$。曾经出现过的数有区间$[y,x][y,x]$，因此要除以$22$下取整，需要小于$yy$。

• 当$x+1<zx+1\backslash lt\; z$，可以加$11$操作$x+1x+1$，也就是$(x,y,z)(x,y,z)$可以变成$(x+1,y,z)(x+1,y,z)$。
• 当$\lfloor \frac{x}{2}\rfloor <y\backslash lfloor\; \backslash frac\{x\}\{2\}\; \backslash rfloor\; \backslash lt\; y$并且$\lfloor \frac{x}{2}\rfloor >0\backslash lfloor\; \backslash frac\{x\}\{2\}\; \backslash rfloor\; \backslash gt\; 0$，可以除以$22$操作$\lfloor \frac{x}{2}\rfloor \backslash lfloor\; \backslash frac\{x\}\{2\}\; \backslash rfloor$，也就是$(x,y,z)(x,y,z)$可以变成$(\lfloor \frac{x}{2}\rfloor ,\lfloor \frac{x}{2}\rfloor ,y)(\backslash lfloor\; \backslash frac\{x\}\{2\}\; \backslash rfloor,\backslash lfloor\; \backslash frac\{x\}\{2\}\; \backslash rfloor,y)$。
• 如果上面两个操作都没有那么就是必败态。
• 如果上面至少一个操作，并且至少有一个操作后必败态，那么当前就是必胜态。没有操作后是必败态，那么当前就是必败态。

找每一个状态是必胜态还是必败，通过记忆化搜索实现。 谁先在必胜态除以$22$下取整，那就谁赢。

$n=500n=500$状态数最多，大约不超过$4e54e5$，将$x,y,zx,y,z$用一个$mapmap$存一下就行了。

（有验题人巨巨直接本地打表500个，O1查表过了......应该他们常数比较大......）

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783549

L. 阿宁睡大觉

知识点

预期：容斥（状压实现）+组合数 复杂度$m\times 2^{m}m\backslash times\; 2^m$

进阶$11$：$m^{2}m^2$ （CF559C）

进阶$22$：$m\sqrt{n}m\; \backslash sqrt\{n\}$（可能是吧，反正大概是这样）

有两个进阶是因为验题大佬分别发现一个类型的题和一个莫队求组合数。 没选择加强，是因为感觉变成拼拼题，没什么意思。

思路

每行最后一个格子是终点。

首先，假设噩梦格子都能经过。从$(1,1)(1,1)$走到任意一个终点的方案数是$2^{n-1}2^\{n-1\}$，因为每一步都有向下或向右走两种选择。

再分别考虑经过哪些噩梦格子的路径。

定义$cn{t}_{i}cnt\_i$为经过$ii$个噩梦格子的路径数。 这里的经过$ii$个噩梦格子，从$(1,1)(1,1)$ 到 $mm$中$ii$个噩梦格子 到 终点，路径之间存在包含关系，因此存在重复计算。 因此容斥原理的思想，多了就减少了补回去，最终答案为$2^{n-1}-cn{t}_1+cn{t}_2-cn{t}_3+cn{t}_4\mathrm{.}\mathrm{.}\mathrm{.}2^\{n-1\}-cnt\_1+cnt\_2-cnt\_3+cnt\_4...$

从输入中选$tt$个噩梦格子$(x_1,y_1)>(x_2,y_2)>(x_3,y_3)>\mathrm{.}\mathrm{.}\mathrm{.}>(x_t,y_t)(x\_1,y\_1)>(x\_2,y\_2)>(x\_3,y\_3)>...>(x\_t,y\_t)$。需要满足$x_1\le x_2\le x_3\le \mathrm{.}\mathrm{.}\mathrm{.}\le x_t,y_1\le y_2\le y_3\le \mathrm{.}\mathrm{.}\mathrm{.}\le y_{t}x\_1\backslash le\; x\_2\backslash le\; x\_3\; \backslash le\; ...\; \backslash le\; x\_t,y\_1\backslash le\; y\_2\backslash le\; y\_3\; \backslash le\; ...\; \backslash le\; y\_t$。如果不满足，说明不存在路径包含这$tt$个格子。

路径$(1,1)>(x_2,y_2)>(x_3,y_3)>\mathrm{.}\mathrm{.}\mathrm{.}>(x_t,y_t)>(1,1)>(x\_2,y\_2)>(x\_3,y\_3)>...>(x\_t,y\_t)>$终点。 $(1,1)>(x_2,y_2)(1,1)>(x\_2,y\_2)$有很多条路径。 $(x_i,y_i)>(x_{i+1},y_{i+1})(x\_i,y\_i)>(x\_\{i+1\},y\_\{i+1\})$有很多条路径。 $(x_t,y_t)>(x\_t,y\_t)>$终点。

$(1,1)>(x_2,y_2)(1,1)>(x\_2,y\_2)$和$(x_i,y_i)>(x_{i+1},y_{i+1})(x\_i,y\_i)>(x\_\{i+1\},y\_\{i+1\})$归为一类，都是左上角走到右下角。

$(x,y)(x,y)$到$(x^{\mathrm{\prime }},y^{\mathrm{\prime }})(x\text{'},y\text{'})$的路径数实际上是一个组合数，杨辉三角旋转45度（看上图感觉一下）。假设$dx=x^{\mathrm{\prime }}-x+1,dy=y^{\mathrm{\prime }}-y+1dx=x\text{'}-x+1,dy=y\text{'}-y+1$这个组合数是第$dx+dy-2dx+dy-2$层第$dx-1dx-1$(或者$dy-1dy-1$)的组合数，也就是路径数等于$C_{dx+dy-2}^{dx-1}C\_\{dx+dy-2\}^\{dx-1\}$

$(x_t,y_t)>(x\_t,y\_t)>$终点这类路径和从$(1,1)(1,1)$走到一个终点的求法一样。路径数就是$2^{n-1-(x_t+y_t-2)}2^\{n-1-(x\_t+y\_t-2)\}$

（对于组合数求法，这里使用了线性的预处理）

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60801754