NOIP2025模拟赛7总结

· · 个人记录

NOIP2025 模拟赛7总结

T1

贪心。

发现是位运算，不妨按位考虑。

由于能修改高位，所以从高到低考虑。

如果最低位有奇数个一，那么答案就是 2^{61} - 1 。

否则，考虑下一位。

如果有奇数个一，那么与上面的类似，如果前面有 01 交替，答案也是如此。

于是用 set 维护一下 01 交替就完了。

顺利 AC 。

T2

树上维护信息。

赛时想到 dsu\ on\ tree ，但是不太会统计答案，于是打个暴力， 40 分。

正解是启发式合并，也不算是 dsu\ on\ tree ，就是合并两个集合。

T3

构造字典序小且逆序对数一定的数列。

先打了个暴力，然后简单优化一下。

但是还有一个问题， P\neq Q。

我贪心了一下，由于没有大样例，所以也不知道对错。

赛后发现假了，只有 25 分。

正解再调用一下之前的构造就好。

T4

多个数据结构暴力维护。

挺难的，现在还不太会做。