Preface
？？？炸完了炸完了炸完了。。。
？？？我怎么 T4 算错时间复杂度了。。。\(100\) 分就这么被吞了啊呜呜。
？？？我怎么 T3 只差一步了。。。我赛时都想到如果重合了可以让对方代替继续走了。。。
等会我好像很多题都是只差一步了啊。为什么呢。
何意味。
T1
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
T1 是橙题，好吓人啊呜。
显然如果 \(m>n\) 那么肯定有一种颜色的椅子没有出现过，直接无解。
并且不能存在 \(i \in [1,n]\) 满足 \(a_i < 4\)，否则也无解。
以及可以算出一个最大的能凑出的桌子数上限 \(\sum \lfloor \frac{a_i}{4} \rfloor\)，如果 \(n\) 比这玩意儿还大那也没救了，无解。
不难证明其他情况下一定都有解。
所以整个判一下就行。
T2
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
居然是打表题，没救了！
有救有救。首先可以根据英文单词的拼写方式写一个简单的函数算出每个 \(<1000\) 的数所对应的英文单词，然后从小到大枚举空位填入的数字，合理的话直接输出然后结束程序就行。
因为题目保证了答案 \(<1000\) 所以枚举是完全没有问题的。说实在的要是答案超过 \(1000\) 了那题目给的英文单词也就不够用了。够用的，这个时候英语老底就发挥作用了（
T3
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(?\) | \(0\) | \(?\) |
估分算是 \(0\) 吧毕竟赛时写的乱搞。我难道指望捆绑给乱搞分吗？？？
先不考虑集合的这个什么“不可重”性质，直接去做，就是让每个 \(a\) 和每个 \(b\) 一一对应上，然后按照某种顺序（比如每次修改有差别的位置的 \(\text{lowbit}\)）递推直至 \(a' = b\)。
但是现在有重合了，怎么办呢？很简单：譬如集合 \(A\) 中的元素 \(sx\) 要变到 \(B\) 中的 \(ex\)，在变化的过程中撞上 \(A\) 中另一元素 \(sy\)，这个时候 \(sx\) 过不去了，我们便考虑让 \(sy\) 代替 \(sx\) 变 \(ex\)，暂存 \(sx\)，等 \(sy\) 走完后面一程之后再回过头来让 \(sx\) 变到 \(sy\)。这样就完美解决了重合的问题。
于是思路就很清晰了：考虑每次取出一组需要匹配的 \(a\) 和 \(b\)（\(a \not= b\)），然后不断沿两数二进制位差别的 \(\text{lowbit}\) 变化，没重合就正常走，重合了则开一个栈 stack 暂存这一步，然后让重合的那位帮着继续走——当然这里并不需要真的去交换什么。\(a' = b\) 了，我们需要做的只剩把暂存的清了。由于开的是栈，越后进的反而越先处理，要是先处理前面的怕中途又撞上。
然后就做完啦。
附一个 solution 喵！
T4
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(0\) | \(100\) |
时间复杂度错的呢，你好意思说你估分 \(100\)。。。
令最初患病 \(n\) 位居民编号分别为 \(a_1,a_2,\dots,a_n\)。注意到在第 \(k\) 天，被感染的居民一定能被表示为 \(a_1^{p_1} a_2^{p_2} \dots a_n^{p_n} \pmod m\)（其中 \(p_1,p_2,\dots,p_n \le 0\) 且 \(\sum p = n\)）。
这个结构很像矩阵快速幂，但是如果你建出矩阵来就有 \(O(m^3)\) 了根本过不去。事实上这题根本用不到矩阵，我们用两个序列做相乘就行了。
怎么乘啊？譬如说我们现在有 \(a\) 和 \(b\) 两个 bool 序列，分别是在 \(k_1\) 天和 \(k_2\) 天时每位居民是否患病的情况（\(1\) 表示患病，\(0\) 表示未患病），而根据上面提到的，如果存在一个 \(a_x = 1\) 和一个 \(b_y = 1\)，显然在第 \(k_1 + k_2\) 天时居民 \(a_x b_y \pmod m\) 肯定是患病的。于是我们就能实现一个 \(O(m^2)\) 的乘法了。
用快速幂的思想做即可，总时间复杂度 \(O(m^2 \log k)\)。
贴一个贺过去的 solution 喵。
Summary
T1 T2 没话说。
T3 挺可惜的，就差一步了，我都想到变化过程重合的时候该怎么做呢，没想到直接就这样一一匹配，暂存一下中间重合时的移动最后还原即可。
T4 也挺可惜吧。我要是赛时发现自己的复杂度其实是 \(O(m^3 \log k)\) 的的话，也许能想到直接用序列乘的正解呢。。。
下次加油吧。