【考后总结】8 月 CSP-S 模拟赛 1
8.3 CSP 模拟 13
蜂鸟 - 吴青峰
传说中人类在远早
住于黑暗的地下之遥
派出了娇小的蜂鸟
找到通往光明的隧道
飞过了一座一座岛
好想有一个地方落脚
把一个一个梦制造
会不会有人能够听到
寻找太阳的梦 自不量力说
自己也变成太阳的念头
有时候寂寞 几乎扛不动
咽在喉咙里无人诉说
我们到底在追求些什么
为何一直不断往前冲
捏出血的双手
忘了也能够 稍微退后
我们总是以为能够自由
回过头那世界却依旧
哎 爱它来的时候
紧握的拳头 别忘了捉那个梦
传说中愤怒的恶魔
曾让这地球四处着火
一只蜂鸟收集云朵
火在雨中变成了彩虹
我们在孤单中探索
危险世界美丽的渴求
就算这力量再微弱
也想牵你手一起挣脱
寻找太阳的梦 自不量力说
自己也变成太阳的念头
有时候寂寞 几乎扛不动
咽在喉咙里无人诉说
我们到底在追求些什么
为何一直不断往前冲
捏出血的双手
忘了也能够 稍微退后
我们总是以为能够自由
回过头那世界却依旧
哎 爱它来的时候
紧握的拳头 别忘了捉
那个梦 来到我的身旁 收拢世界的光
我想要成为自己 也成为你的光
我们到底在追求些什么
为何不断往前冲
捏出血的双手
忘了也能够 稍微退后
我们到底在追求些什么
为何一直不断往前冲
捏出血的双手
忘了也能够 稍微退后
我们总是以为能够自由
回过头那世界却依旧
哎 爱它来的时候
紧握的拳头 别忘了捉那个梦
我那个梦
我那个梦
寂寞中拍打的翅膀
终于找到你一起飞翔
渺小却带来了神话
你看这世界开满了花
\(\text{zero4338 round}\)
T1 y
显然 \(\text{xt}\) 会选择四个角，对每个格子求出到四个角的曼哈顿距离最大值，操作一定会优先选择最大值较小的，所以把距离数组排个序就行了。
T2 s
经典套路是设答案是 \(a\)，把小于 \(a\) 的位置设成 \(0\)，大于等于设成 \(1\)，这样按照操作序列进行一次操作之后结果为 \(0\) 则答案加 \(1\)，容易发现如果原排列结果是 \(a\)，那么在 \(1\sim a\) 都有一次贡献，等价于加 \(a\)。
考虑 DP，设 \(f_{i,j,0/1}\) 前 \(i\) 个操作，排列上有 \(j\) 个 \(1\)，当前结果是 \(0/1\) 的方案数。转移平凡，复杂度 \(O(n^2)\)。
答案还要乘上 01 序列对应排列的个数 \(j!\times (n-j)!\)。
如果每个连续段看作整体 DP 也可以。也有看作多项式平移再矩阵加速的做法，目测常数较大。
T3 p
去年不会，今年还不会。
两个区间并的直径端点一定在两个区间直径端点中。线段树维护。
T4 m
容易想到二项式反演。
钦定 \(i\) 个不合法，枚举有 \(j\) 个只包含 \(1\) 次，再枚举有 \(k\) 个集合中包含钦定的这些元素，那么这些集合的其余 \(n-i\) 的元素暴力选，而另外的集合选择方案数理应是 \(\sum_{l=0}^{2^n-k}\dbinom{2^{n-i}}{l}\)，而由于 \(k\le i\)，\(2^n-k\ge 2^{n-i}\)，所以就是 \(2^{2^{n-i}}\)。
套上二项式反演再整理一下就是：
后面这个式子考虑组合意义，从 \(i\) 个元素中选取若干加入到 \(k\) 个集合，要求集合非空，可以递推，大致是 \(F_{i,k}=(k+1)F_{i-1,k}+F_{i-1,k-1}\)，也就是每个元素可以选择放或不放、加入或新建一个集合。
这样就 \(O(n^2)\) 解决了。