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