这是本文档旧的修订版！
2020牛客暑期多校训练营（第六场）
Results
Summary
- Solved 5 out of 11 problems
- Rank 95 / 1120 in official records
- Solved 6 out of 11 afterwards
| # | Who | = | Penalty | A | B | C | D | E | F | G | H | I | J | K | Dirt |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 12 | 大吉大利，今晚吃 mian(); | 5 | 516 | -2 | +1 00:52 | + 00:48 | + 00:13 | -5 | +1 03:08 | +2 02:15 | 44% 4/9 |
Member Distribution
| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Pantw | √ | O | √ | ||||||||
| Withinlover | √ | √ | |||||||||
| Gary | - | √ |
(√ for solved, O for upsolved, - for tried but not solved)
Solutions
A
B
找规律。1 3 21, 2 8 64，就直接猜了。
具体证明没看懂，回头补。（大概吧）
C
D
E
F
G
如图所示，将边按照右/下点的坐标和的奇偶性分成红绿两类。
按照蓝色箭头和粉色箭头的顺序加入一个队列里，然后染色的时候从一个队列里取即可，切换颜色的时候需要切换所取的队列。
但是这样做会碰见一个问题，那就是有可能最后两个队列各剩 4 条边，但你只剩一个颜色，这个颜色要求 8 条边。
那么这就造成了闭合回路。
解决方法是我们把红色边的队列倒过来。这个使用 deque 非常方便，因为 std::deque::iterator 是 $\mathtt{LegacyRandomAccessIterator}$，可以直接使用 std::reverse。
倒过来之后，我们会发现，队列中最后剩下来的只会是左上角的一点点红色边和右下角的一点点绿色边，把这些都取上也造不出同色闭合回路。
那么这个题就这么做完了。
你问我为啥没过？
别问，问就是我是傻逼。
1 1 2 1 2 1 2 我居然觉得没问题，我是傻子呜呜呜
H
I
J
K
直接维护一个 cnt[i] 表示目前 i 的数量，维护一个 cntcnt[i] 表示目前 cnt[x] 为 i 的 x 的数量，然后扫一遍，即可判断出某区间是否是 1-k 的排列。
然后维护一个 Canp[i]，表示 1-i 的前缀是否合法。（Canp : can_this_prefix_be_part_of_permutation） Cans[i] 同理，suffix 版本。
然后有了这三个东西，我们就可以直接枚举第一个分点在哪了，这个枚举最多枚举 k 个，判断最多判断 n/k 个点的标记，所以是线性的。
啥？你问我元素太大存不下咋办？
那我直接 a_i > k 判 NO 就完了
k 也很大咋办？k > n 的时候按照最多两段做就完了，用个 sort 整一整就没了
Comments
ptw:
- 别 再 看 错 特 例 了 (G)
- 特例可以 double-check 一下，稳一点 (G)
- 可以早点想 A 和 J
