2023NOIP A层联测25 总结

T1 让你构造 $40\times 40$ 的只含 r,y,x 的矩阵，含有 $ryx$ 的个数恰好为 $n$，$n\le 2222$。看完题后就开始想构造，一开始想构造 $3\ast 3$,$5\ast 5$ 的单位矩阵的，但是始终不够数。后面去看 T2，是期望，类型从未见过，没多想回去看 T1。大概 9 点时想到了 $n=2217$ 的做法，感觉非常可做，就继续看。但是后面快十点了还没想出来，就先打了暴力，大概十点四十调过大样例，自己又造了极限数据也过了，去看 T2。

T2 $n$ 间教室，教室 $a_i$ 个人在打游戏，学生可以让一间教室的人停止玩游戏，老师去抓一间教室的玩游戏的人，学生和老师都有最优策略，问老师期望抓到多少人，$n\le 30,a_i\le 40$。没什么思路，后面打暴力时间就水了 $n\le 2$ 的数据，感觉两个人答案应该是 $0.5\min (a_1,a_2)$。赛后发现做法假了，正解二分答案，用概率去做。

T3 对于排列 $p$，定义 $f(k,i)=\underset{j=k}{\overset{k+i-1}{\min }}{a}_j$，$F(k)=\underset{i=1}{\overset{n-k+1}{\max }}f(k,i)$，问有多少排列 $p$ 所生成的 $F$ 满足输入的 $F$，$n\le 50$。由于做到这里就是打暴力时间了，就直接打阶乘暴力，10min 打完，后面又去打 $F(i)=n-i+1$ 的特殊性质。

T4 一个 01 权无向图，你要给每个点赋一个字母 $A,B,C,D$，满足边权为 $1$ 的边两端的点字母满足要求，$n\le 10^6$。本来想打暴力的，结果不会骗。看题解用了 2-sat，挺巧妙的逻辑转换。

期望得分：80+20+30+0=130pts

实际得分：20+0+30+0=50pts

总结：挂分了，T1 只造了大数据，没考虑 $1,2$ 这些小的情况；T2 $n=2$ 时策略不是我想的那样。造hack 数据时要大小都要造，要针对写代码时不是很明的地方造hack。小技巧：博弈论局面不明的情况考虑用概率去做。现在发现 T3 用了之前积累过的技巧赛时忘了，要多复习这些技巧写在博客里。