2023NOIP A层联测25 总结

题目

T1 构造

大意

构造一个 \(a\times b\) 的矩阵，要求 \(a,b\leq 40\)，且有 \(n\) 个 ryx。（横向，纵向，和 \(45^\circ\) 的方向上的 ryx）

赛时思路

一开始发现求出最大的构造方法后一定可以缩减到另外一个数。构造最大的过程中，一开始的做法是横着填 ryx，发现不够以后，改进一下填 ryxy，最后一列可以留出来竖着填。不过在计算个数的时候算错了，后面多想了 20 分钟，想到了按照竖着填 ryxy 的做法，算这个算个数又算对了……

先去写其他题暴力了，跑完操回来写 10 分钟左右，主要是考虑过结构以后在写的代码，速度有所提升。

赛后思路

同上。

T2 游戏

有 \(n\) 个房间，第 \(i\) 个房间里有 \(a_i\) 个人，同学可以选择一个房间进入，将 \(a_i\) 个人清空。老师选择一个房间将抓住这 \(a_i\) 个人。两人采用最优方案，决策可以基于概率，求老师抓住人最多的期望，或者说学生使老师抓住人最少的期望。

赛时思路

期望题不是很有想法，拿样例猜了个学生只选最大值的结论，可惜没过大样例，后面就没什么想法，写了 \(n=2\) 时的一个结论就换题了（其实这个结论也是错的……），最大的问题在于没有注意决策的概率。

赛后思路

题解链接：2023NOIP A层联测25 T2 游戏 - 彬彬冰激凌 - 博客园 (cnblogs.com)

分析问题，由于双方都是最优策略，所以可以说学生知道老师会选择那些教室设置概率（概率设置好就不能改变），老师也知道学生会怎样选择教室（不是知道一定会去那个）。

设老师选择的集合是 \(S\)。

那么老师在学生不清空的情况下，老师的期望为 \(\sum_{i\in S} p_ia_i\)（\(p_i\) 是概率）。

学生知道每一项 \(i\) 的贡献，所以由于学生要使老师的期望最小，那么学生肯定选 \(\max(p_ia_i)\)。

于是答案为 \(\sum_{i\in S} p_ia_i-\max(p_ia_i)\)。

对于最大的那一项 \(p_ia_i\) 来说，由于他们肯定会被选走，所以说老师不妨把 \(p_i\) 改小一点，多出来的概率分给其他的数，虽然总和减小了，但被减掉的部分也减小了，而且不会被减掉的部分增加了，所以答案将获得最优。

那么最好情况下，我们要使得 \(\sum_{i \in S} p_i=1\) 且对于任意 \(i\) 而言 \(p_ia_i\) 相等。

可以构造

\[p_k=\frac{\frac{1}{a_k}}{\sum_{i \in S} \frac{1}{a_i}} \]

这个 \(p_k\) 是符合条件的。

现在问题变为要怎样是答案最大。

答案最大要是 \(p_i\) 最小，\(p_i\) 最小要使 \(\sum_{i \in S} \frac{1}{a_i}\) 最小，也就是使 \(\sum a_i\) 最大。

设集合 \(S\) 有 \(m\) 个数，那么取最大 \(m\) 个即可。

而且这样答案合式可化为：

\[\sum_{i\in S} p_ia_i-\max(p_ia_i)=\frac{m}{\sum_{i \in S} \frac{1}{a_i}}-\frac{1}{\sum_{i \in S} \frac{1}{a_i}}=\frac{m-1}{\sum_{i \in S} \frac{1}{a_i}} \]

对答案排序后，枚举 \(m\) 即可。

T3 数数

大意

赛时思路

探究了一下性质，结果什么也没想出来，本题剩 20 分钟，果断最低档暴力分。

赛后思路

还在补。

T4 滈葕

大意

赛时思路

一开始想了一个 DP 式子，该点的选择表示出来，后来发现它没有最优子结构也存在后效性，然后就没什么想法了，开始写暴力，但时间复杂度算错了，把 \(O(4^n)\) 算成了 \(O(n^4)\)，于是最低档分也没拿到。

赛后思路

2-SAT好题，题解链接：2023NOIP A层联测25 T4 滈葕 - 彬彬冰激凌 - 博客园 (cnblogs.com)

\(z=1\) 表示配血实验发生凝集反应，设 \(a_i,b_i\) 分别表示第 \(i\) 个人有无凝集原 A,B。（无凝集原 A，肯定有抗 A 凝集素，B同理）那么发生反应的必要条件是 \(a_x \and \neg a_y\) 或 \(b_x \and \neg b_y\)，所以 \(z=(a_x\and \neg a_y) \or (b_x \and \neg b_y)\)。

若 \(z=0\) 则有 \(\neg(a_x\and \neg a_y) \and \neg (b_x \and \neg b_y)=(\neg a_x \or a_y) \and (\neg b_x \and b_y)\)。

若 \(z=1\) 则有 \(z=(a_x\and \neg a_y) \or (b_x \and \neg b_y)=(a_x \or b_x)\and(a_x \or \neg b_y)\and (\neg a_y \or b_x)\and (\neg a_y \or \neg b_y)\)。

这两个都可以使用 2-SAT 解决。