 游记(VP))
省流
连蒙带猜拼尽全力 \(4t\)，表现分 \(2000\)。
10.16
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
翘课了，结果刚开始 \(vp\) 就被发微信找过来，再也不敢翘这种点名的课了。下午带着电脑去补题。
赛时
A 题按题意模拟，省略。
B 题给了一个 \(2 \leq n \leq 100\) 的矩阵，要求往矩阵中填上下左右，人到这个格子就会按照矩阵中的方向走，要求构造一种恰好有 \(k\) 个格子可以走出矩阵的。发现如果用两个箭头互相对着就走不出去，于是把两个互相对着的箭头放在左上角，然后挨个遍历把剩下不能出去的点都指向左上角就行。那么只有当 \(n * n - k\) 恰好为 \(1\) 时无解，以及 \(k = n\) 时就不放一开始的两个箭头。\(13min\) 通过。
C 题给了一排人，每个人只能让左侧的别人或右侧的别人看到，这个人永远能看到自己。给出每个人能看到几个人，问有多少种可能，对一个诡异的数取模。一开始看到题想着应该是 \(dp\)，然后考虑转移。发现对于每两个人只有四种情况，然后状态就记录当前最后一个人是左侧人还是右侧人，然后根据情况转移。此时发现情况数其实不会增加，所以答案只有 \(0\)，\(1\)，\(2\)。然后发现不过样例，因为两个人的差虽然满足，但最后整体的总数可能不满足，但是转移中间记录总数又有点麻烦。考虑答案数量，所以只有第一个人是左人还是右人两种可能，然后按照差值把整个序列存下来，最后再验证一下总数就行了。因为中间差不可能的情况没有提前退出挂了一发，\(38min\) 一发罚时通过。
D 题是交互题，给了 \(n\) 个电池，每次可以选两节电池，如果两节电池都有电就算成功。其中有未知的 \(a\) 个有电的电池，总测试次数不能超过 \(\frac{n^2}{a}\) 次。因为这个东西永远只能两个两个试，所以猜测肯定又是和概率随机这种东西相关。然后想到一个测试过的电池有电的概率就会比别的电池低，于是大胆猜测用两个当前测试次数最少且之前没一起测过的电池就行。用 \(set\) 很容易实现，一发通过于 \(53min\)。
E 题是给了一个 \(n * m\) 的矩阵，矩阵中有 \(k\) 个点，每个点可以先往左走一列，然后往上下左这三个方向随便走，不能重复，在走过的地方都留下一个新点。两个人轮流走点，问谁最后动不了另一个人赢。一开始先想广泛的，只有一列肯定后手赢，有两列则看第二列的奇偶性。然后想到第三列的数可以任意变化第二列的奇偶性，于是最后一个走最后一列的必胜，也就是只看最后一列的奇偶性。然后特判一下行数为 \(1\) 的，就是每一列往前走的所有列的贡献之和加 \(1\) 就是这一列的贡献之和，然后就可以计算总行动次数，根据奇偶性就可以得到结果了。交上去挂了几发，因为我对前面的想法怎么都找不出问题，所以把精力花在看实现上，找出了几个行数为 \(1\) 时的错误，但也没有通过第二个测试点，比赛就结束了。
赛后
看了 E 的题解，发现题解中说只要有一列是奇数就先手胜，非常懊恼。因为先手并不一定要第一步取最高位，而是可以取最高奇数位并把所有位都变为偶数个，然后后手全偶数就必败了。
看了 D 的正解，是利用鸽巢原理，遍历一段中至少出现一个好电池，再每个遍历所有电池，就可以 \(n * \frac{n}{a}\) 次必定得到了。
2025年10月16日