20230924

23/09/24 NOIP模拟赛总结

时间安排

8:00-8:20

看题

8:20-8:40

思考T1，感觉是最短路，但不知道最长距离怎么处理

8:40-9:10

感觉T2是组合数，但是有个细节不会处理，先把暴力打了

9:10-9:40

写T3暴力，感觉今天的题好难啊。

9:40-10:30

回到T1，发现这就是 \(n\) 遍 \(dijkstra\) ，写完正解又写了暴力，开始对拍。

10:30-11:00

看了看T4，看见期望直接跑路，走前输出 \(0.00\)，让我骗到20。

11:00-11:30

感觉能写T2第二档暴力，直接dfs加贪心，赛场上没想到状压。

11:30-12:00

检查了代码，发现T1没输出-1，差点\(100 \to 30\)。

罚坐。

反思总结

1.像这种NOIP级别的模拟赛，一般都要A掉T1，这样才能有一个较好的名次。

2.用dfs暴力枚举，思考能不能有状压代替。

3.复习期望，期望=每种情况的概率 \(\times\) 权值。

简要题解：

T1:

跑 \(n\) 遍 \(dijkstra\)，再建图跑 \(dijkstra\) 。

T2:

\(trick\)：将选择物品转化为矩阵，然后在矩阵中满足限制条件进行DP。

对两个端点分别作前缀和，把右端点当做状态，左端点当做限制，用组合数进行DP。

T3:

\(trick\)：\([1,x]\) 的二进制下 \(1\) 的个数为奇数的个数为 x/2+(x&1 || popcount(x)&1)

袁神的数学归纳法：

lyk的证明：

设 \(x\) 二进制表示下\(1\)的个数为 \(f(x)\)

//打表
00001 1
00010 2
00011 3
00100 4
00101 5
00110 6
00111 7
01000 8
01001 9
01010 10
01011 11
01100 12
01101 13
01110 14
01111 15

对于任意偶数 \(k\)， \(f(k)\) 与 \(f(k+1)\) 一奇一偶。
同时，\(f(1)\) 为奇数，所以对于任意奇数 \(l\) 而言， \([1,l]\) 内 \(f(x)\) 为奇数的有 \(l/2+1\)。

对于偶数情况，我们考虑是否与 \(f(1)\) 奇偶性相同

• 不同则 \(x/2\)

• 相同则 \((x-2)/2+1+1=x/2+1\)

T4:

加权概率求期望：数据结构。

\(E(x+y)=E(x)+E(y)\)：与DP转移类似。

一个人最终占据了 \(x\) 个点的方案数： \({\textstyle C_{n-2}^{x-2}}\)。

占据某个点对的概率是\({\textstyle C_{n}^{x}}/{\textstyle C_{n-2}^{x-2}}=x(x-1)/(n(n-1)))\)。

用淀粉质计算即可。