题解 | 湖南师范大学2025新生赛决赛 – 逢絮聆风—

这场比赛参加了线上同步赛，也许是因为没有什么参赛经验，总觉得线下线上还是有差别的。

由于今天比较累，所以哪怕只有一点题我也选择分成上下两集发。

题目可以从牛客网的比赛界面下载，这里提供一下链接：https://uploadfiles.nowcoder.com/files/20251211/463762_1765433899562/statements.pdf

官方题解也放着这里供大家自取，感谢牛客网的技术支持：

https://uploadfiles.nowcoder.com/files/20251212/463762_1765550485929/tutorial.pdf

0x00 钝评

本次参加线上同步赛，个人感受是出题组相对比较和善。题目按照顺序难度递增，一到五题总体还可以接受（事实上，我也就A了这五题），后面三题还是比较有思维量的。下面是牛客网校外同步赛前十名的通过情况：

0x01 A题：CirnoNine 的舞萌DX

题面：

CirnoNine 最近沉迷上了舞萌！
CirnoNine 游玩了一首歌，得到 a 个 Critical Perfect 判定，b 个 Perfect 判定，c 个 Great 判定，d 个 Good 判定，e 个 Miss 判定。
每一个 Critical Perfect 判定会得到 3 DX分数，Perfect 判定会得到 2 DX分数，Great 判定会得到 1 DX分数，其余判定不得 DX分数。
现在她想知道打完一首歌后自己的 DX分数为多少。

签到题，读入五个数a,b,c,d,e，输出3*a+2*b+c即可。

0x02 B题：CirnoNine 的排列构造

题面：

Maxduan 给 CirnoNine 出了一个题，CirnoNine 需要构造一个长度为 $n$ 的排列 $^*$ $p$ 使得对于任意整数 $i\ (1 < i < n)$ 满足 $2p_i \not = p_{i-1}+p_{i+1}$ 。由于 CirnoNine 太笨了，所以这个问题就归你了。
$^*$ 长度为 $n$ 的排列是一个从 $1$ 到 $n$ 都恰好出现一次的数组。例如 $[1,5,3,2,4]$ 是一个排列， $[1,1,4,5,1,4]$ 不是一个排列。

一个升序排列本身就是一个公差为1的等差数列（如：1,2,3,4就是4的升序排列）。我们对小范围数据进行模拟，可以感受到好像不存在无法构造的情况。这个时候看到题面又是构造问题，下意识的往奇偶性构造方向尝试思考。不难发现，对于一个原始序列是升序排列n，我们可以用奇偶交替的构造方法得到合法答案。得到的构造就是：1,n,2,n-1,3,n-2...

ac code:

int n;

cin>>n;

vector<int> a(n+1);

for(int i=1;i<=n;i++) a[i]=i;

if(n==3)

{

     cout<<3<<" "<<1<<" "<<2<<endl;

     continue;

}

else

{

     for(int i=1;i<=n;i++)

     {

           if(i%2==1) cout<<(i+1)/2;

           else cout<<n-i/2+1;

      }

      cout<<endl;

}

0x03 C题：CirnoNine 的博弈游戏

题面：

CirnoNine 为了证明自己是最聪明的，他向 Maxduan 发起了挑战！
初始有一个长度为 的只有 0 和 1 组成的二进制字符串 ，从 CirnoNine 先手，Maxduan 后手，两人轮流做以下操作：
找到字符串中相邻且不同的两个字符，然后将其从字符串中删除。
如果轮到的玩家无法从字符串中找到相邻且不同的两个字符，则他输了这场游戏。
假设两人都聪明绝顶，谁会赢得这场游戏？

又又又是经典博弈论背景。如果从结果入手判断输赢通常考虑小范围打表考虑。为了方便读者尝试，这里提供样例：

思考：如果某个人执行了删除操作，那么对于原字符串，就会同时失去一个1和一个0.如果一直进行这样的操作，最后的结果就是剩下字符串全部为1/0.此时轮到的人面临着无法选择删除的情况，也就是输了。

不难想到，我们肯定需要统计原串中的1和0字符个数。而我们能够删除的肯定是两者中个数较小的，毕竟如果删除的操作是成双成对的，数量多自然无所谓删不删，但是数量少的删一个少一个，到最后全删完了整个串就没有删除的选择余地了。也就是说，对于删除操作，虽然对于两种字符删除的个数都是一样的，但是个数少的字符损失更大。

所以第一步一目了然，我们在输入过程中处理1和0字符个数，并取出他们中较少的个数数量。接下来就是判断奇偶，毕竟先手后手在场数上体现的就是奇偶性。不难发现如果 min (0的个数 , 1的个数) 是奇数，那么先手的人必然能胜利，反之就是后手者胜利。

0x04 D题：CirnoNine 的数学问题

题面：

一天 CirnoNine 晚上做了个噩梦，发现她正在进行数学考试！试卷上写了这么一道题：
有 个人分别从 2 个不同的数中选择若干个数（可以不选），分别构成集合A1,A2,A3...An 记 A1∩A2∩...∩An 中元素个数为 m，则 m>1的方案数为多少？（两种方案被认为不同当且仅当存在一个人选择的数不同）
为了使 CirnoNine 从噩梦中苏醒过来，你需要帮她解决这个问题。

为了方便大家理解题目，给出样例：

其实如果写过一点题，就不难有非常强烈的数学直觉：快速幂模版题，答案为：

如果没有这么强烈的直觉，我们也可以采用模拟样例的方式得到结论。先让我们简化题意：

简化题意：

n个人从二进制00 01 10 11四个序列选择一个，全部按位与后二进制序列至少有一个1的方案数有多少？

这下看懂了，四个选项中绝对不会选择00，毕竟两个0再怎么按位与也只能得到0。在有n个人进行选择的时候，考虑二进制第一位是1有两种情况（10或者11），方案数为2ⁿ。二进制第二位位1也有两种情况（01或者11），同样也有2ⁿ种。把他们加起来得到的是2ⁿ⁺¹种，但是由于“所有人选择都是11”这个选择被重复考虑，所以最后还需要减去1.

Fun Fact：

1.命题人在赛后解析表示，由于担心freshman不会快速幂，所以本题计算数据的强度并不需要快速幂即可切掉。

2.本题改编自2025杭州二模数学第14题。高中毕业了数学还在追我。