Test：NoiOnline 2020 (20200425)

考试策略

经验和教训

第一题：(color)

期望得分：100 实际得分：100 改后得分：100

解题思路

这道题是一道数学题。还好。假设\(p_1。

以两个\(p_1\)和\(p_2\)的共同倍数之间的区间为一个单位。这中间（不包括两端）一共会有\(\frac{lcm(p_1,p_2)}{p_1}-1\)个 \(p_1\)的倍数。它们会被\(\frac{lcm(p_1,p_2)}{p_2}-1\)个\(p_2\)的倍数分成\(\frac{lcm(p_1,p_2)}{p_2}\)个部分，每个部分的个数会尽量平分，个数差不会大于1。所以就可以得到最长的连续\(p_1\)个数。和k比较就可以了。

失分原因

解决办法

第二题：(sequence)

期望得分： 50 实际得分：50 改后得分：0

解题思路

我只会暴力。\(O(N^2)\)。

实际上，这道题并不需要什么高级算法。陈亮恺举了一个样例，把每一个区间的答案列出来，发现了规律，然后就可以用线段树解决问题。

线段树维护的是函数值的区间和而不是函数值的平方区间和。l=1时的平方区间和可以\(O(N)\)算出，后面就只要把该减去的减去就可以了，不需要维护平方和本身。

失分原因

当时把这道题复杂化，以为要用到什么类似莫队的高级算法，没有对一个实例进行推演。

解决办法

做题之前先自己造几个数据玩一玩发现题目内部的性质。

第三题：()

期望得分：10 实际得分：0 改后得分：0

解题思路

连暴力都没有打完，只写了个链的解法。因为题意有歧义所以无法估分，大概是10分。

正解：首先用怎么想都想不到的dp做：

dp[i][j]表示i的子树中有j对产生贡献的点对的方案数。

然后就有了转移：

在i号点不加入的时候：

\[dp[i][j + k] = \sum_{son}dp[son][j]\times dp[i][k] \]

在i号点加入的时候：用A[i]表示i的子树中小A的点的个数，用b[i]表示小B的点的个数。

\[dp[i][j]+=f[i][j-1]\times \max((B[i]-(j-1)),0) \]

在树形DP结束之后，用到了一个叫做二项式反演的东西：

\[g(k)=\sum_{i=k}^n C_i^kf(i)\Leftrightarrow f(i)=\sum_{k=i}^n (-1)^{n-k}C_k^i g(k) \]

设答案\(H(k)=\)正好k对造成贡献的点对的方案数。

我们需要一个反演的\(G(i)\)满足：

\[G(k) = \sum_{i=k}^m C_i^kH(i) \]

yxt设的是：

\[G(k)=dp[1][k]\times (m - k)! \]

这个转化有点看不懂了。

失分原因

暴力没打完。优先写的应该是暴力。

解决办法

有时候不要纠结定理的证明。更重要的是会使用。

*说明：

期望得分：考试结束时预估分 实际得分：考后评测分

改后得分：可能不能完全改对，写上改后最高分

解题思路：可详可略，可以不写，可以写在做题记录里。

失分原因：从心态调节、时间分配、算法分析、知识点掌握、代码实现/调试能力、细节的分析和处理、审题测试等做题习惯多个维度分析。

解决办法：针对前面导致失分的每一个原因，找到一个防止以后出现同类问题的明确解决办法