20231004

23/10/04 NOIP模拟赛总结

时间安排

7:40-8:00

看题，感觉都没有思路，有点慌。

8:20-9:00

思考T1，先把暴力打了，打表找规律找了20分钟。

9:00-9:30

写T2暴力，感觉前两题都是DP，但不会设状态，原因在反思总结中有提到。

9:30-10:20

想到了T3的 \(n^2\) 做法，但是没想明白细节，弃疗。

10:20-11:00

T2有了50的思路，后来发现假了，连大样例都过不掉。

11:00-11:40

想了想T4，感觉连暴力都很难打，回T3调题。

反思总结

1.思考DP时，不能将DP过程具象化，这样只会写成暴力。

2.在题目想不到正解时，多拿几档暴力分。

简要题解：

T1:

设 \(f_{n,k}\) 表示用 \(n\) 个节点构造一棵深度小于等于 \(k\) 的二叉树的方案数。

\(f_{i,j}=\sum_{k=1}^{i} f_{k-1,min(k-1,j-1)}\times f_{i-k,min(i-k,j-1)}\times C_{i-1}^{k-1}))\)

官方题解

T2:

因为 \(sqrt(500)=22\)，所以每个数至多有一个质因子大于等于23。

所以直接根号分治+DP。

T3:

两个人要相互靠近直到相遇，所以分为相遇前和相遇后。

• 相遇前的贡献：经过点的子树大小。

• 相遇后的贡献：按奇偶性来挑选最大的子树。

按这种贪心方法计算答案即可。

T4:

不会。