2023NOIP A层联测25 总结
T1 让你构造 40 × 40 40\times40 40×40 的只含 r,y,x 的矩阵，含有 r y x ryx ryx 的个数恰好为 n n n， n ≤ 2222 n\le2222 n≤2222。看完题后就开始想构造，一开始想构造 3 ∗ 3 3*3 3∗3, 5 ∗ 5 5*5 5∗5 的单位矩阵的，但是始终不够数。后面去看 T2，是期望，类型从未见过，没多想回去看 T1。大概 9 点时想到了 n = 2217 n=2217 n=2217 的做法，感觉非常可做，就继续看。但是后面快十点了还没想出来，就先打了暴力，大概十点四十调过大样例，自己又造了极限数据也过了，去看 T2。
T2 n n n 间教室，教室 a i a_i ai 个人在打游戏，学生可以让一间教室的人停止玩游戏，老师去抓一间教室的玩游戏的人，学生和老师都有最优策略，问老师期望抓到多少人， n ≤ 30 , a i ≤ 40 n\le30,a_i\le40 n≤30,ai≤40。没什么思路，后面打暴力时间就水了 n ≤ 2 n\le2 n≤2 的数据，感觉两个人答案应该是 0.5 min ( a 1 , a 2 ) 0.5\min(a_1,a_2) 0.5min(a1,a2)。赛后发现做法假了，正解二分答案，用概率去做。
T3 对于排列 p p p，定义 f ( k , i ) = min j = k k + i − 1 a j f(k,i)=\min\limits_{j=k}^{k+i-1}a_j f(k,i)=j=kmink+i−1aj， F ( k ) = max i = 1 n − k + 1 f ( k , i ) F(k)=\max\limits_{i=1}^{n-k+1}f(k,i) F(k)=i=1maxn−k+1f(k,i)，问有多少排列 p p p 所生成的 F F F 满足输入的 F F F， n ≤ 50 n\le50 n≤50。由于做到这里就是打暴力时间了，就直接打阶乘暴力，10min 打完，后面又去打 F ( i ) = n − i + 1 F(i)=n-i+1 F(i)=n−i+1 的特殊性质。
T4 一个 01 权无向图，你要给每个点赋一个字母 A , B , C , D A,B,C,D A,B,C,D，满足边权为 1 1 1 的边两端的点字母满足要求， n ≤ 1 0 6 n\le10^6 n≤106。本来想打暴力的，结果不会骗。看题解用了 2-sat，挺巧妙的逻辑转换。
期望得分：80+20+30+0=130pts
实际得分：20+0+30+0=50pts
总结：挂分了，T1 只造了大数据，没考虑 1 , 2 1,2 1,2 这些小的情况；T2 n = 2 n=2 n=2 时策略不是我想的那样。造hack 数据时要大小都要造，要针对写代码时不是很明的地方造hack。小技巧：博弈论局面不明的情况考虑用概率去做。现在发现 T3 用了之前积累过的技巧赛时忘了，要多复习这些技巧写在博客里。