模拟赛一

zibenlun · 2023-10-01 20:21:09 · 个人记录

忘了得多少分了……

T1

考场上本来想多得一点分，所以没有打暴力，结果 0分。

首先二分出 a,b,c,d 四个数的总和，然后枚举 a,d(或者 b,c)，之后估算出 b,c 的大致范围，再从这个范围中找到 b 和 c 的值。

赛时只做了小范围的数据和一条链的情况。

小数据：

直接暴力求解。

链：

发现每一个点移动到他的父节点时，其他的点会有 2^n/2/2 种不同的排列，所以只要乘上方案数就行了。

首先对于 A 题目没有过多的限制，所以说我们可以将 A 放在第一个位置，之后再交替放 B。

先考虑放完所有的 A，先将 A 与 B 尽可能更多地交替放置。然后剩下的 A 每 a 个就 +1。

之后考虑 &B&。对于当前，如果最后的一位是 A,那么在后面加上一个 B 就能使价值加一，剩余的 B，每有 b 个 B，就能使价值加一。

考场上实在是看不出来这是一个分段函数，所以只能做出暴力的 5 分。但是在暴力的基础上，加了一些优化，本来希望能做对之后查询的部分……但是失败了。

优化：将修改操作中连续的操作进行合并，减少询问时操作的次数。

暴力模拟即可。

根据题意可以得出整个变化的过程中可以归结成为一个分段函数，所以只需要二分找到它的两个断点，之后就可 O(1) 地进行查询。