20240712NOIP模拟赛复盘
总结
T1:其实不难,但是认为自己推出来依旧很难。但是暴力分 \(15\) pts 应该是好拿的。
T2:推了一个正解,但是因为一些细节问题写挂了。以后应该先把暴力分全部拿完再写正解,写代码时也需要注意细节。
T3:赛时口胡出了正解,但是边界没有考虑完全,导致样例没过,最后也没有交。暴力分 \(50\) pts 其实十分好写 但是会正解谁会写暴力啊
T4:能力就是只能爆零,但是有人告诉我输出 0
可以获得 \(20\) pts?
以后代码可以这样写:
void bruteforce ()
{
// write your code here
}
void std ()
{
// write your code here
}
signed main ()
{
if (暴力可以过) bruteforce ();
else std ();
return 0;
}
这样可以大大降低风险。
题解
数学高手(math)
考虑先计算前 300 项,然后大力分讨。
code
墅居结垢(ds)
对于每次删掉的数,单调队列维护,然后动态维护 \(\text{mex}\)。
code
染色(color)
每个颜色向相邻颜色的点连边,长度为相隔的没有相邻的球的个数。计算每个颜色最多可以有的球的数量,然后使用这个为基准,用大根堆维护。
code
超级马里奥(mario)
设 \(d_{i,j}\) 为某次在 \(i\) 吃饭后,一直饿着走到 \(j\) 再吃饭,满足 \(i\) 到 \(j\) 不超过 \(c_i\) 条边的最长路径。现在考虑如何求这个 \(d_{i,j}\)。
可以进行倍增。设 \(f_{i,j,k}\) 表示从 \(i\) 出发,走了不超过 \(2^k\) 到 \(j\) 的最长路。每次枚举中间点,对 \(d_{i,j}\) 进行转移。
设 \(F_{i,j}\) 表示从 \(i\) 出发,用了 \(j\) 元(恰好用完)的最长路。发现这个东西具有单调性,所以可以每次二分找所需要的钱。转移感觉比较显然。
code