ATC ** 练习
要正视自己的 ** ，所以。。。
AGC056A
statement
给定一个 \(n\ (n \ge 6)\)，构造一个 \(n\times n\) 的矩阵，由 . 和 # 组成，这个矩阵满足：
- 每行每列都有且仅有 \(3\) 个
#。 - 定义两个
#在上下左右四个方向相连则为连通，若 \(a\) 和 \(b\) 连通，\(b\) 和 \(c\) 连通，那么 \(a\) 和 \(c\) 也连通。满足这个矩阵中由#连通组成的连通块数量恰好为 \(n\) 。
solution
由于要满足行和列两个方向的信息，所以考虑按对角线对称构造，然后通过不停的奋斗，搞出了这种东西。##.#......
###.......
.#.##.....
#.#..#....
..#..##...
...##..#..
....#..##.
.....##..#
......#.##
.......###
当然，这是偶数的，奇数的长这样：
##.#.......
###........
.#.##......
#.#..#.....
..#..##....
...##..#...
....#..##..
.....##.#..
......#..##
.......#.##
........###
然后正解是对于 \(n \% 3\) 的结果分类。
对于 \(n = 3k\) 的时候，构造：
###......
...###...
......###
###......
...###...
......###
###......
...###...
......###
然后是 \(n = 3k + 1\) ，考虑在 \(n = 3k\) 的基础上构造：
3
###.......
...###....
......###.
###.......
...###....
......###.
###.......
...###....
......###.
3..........
然后就是从上面扣下来三个，最后只能多一个连通块，然后就变成下面的样子：
###.......
...###....
......###.
##.......#
...##....#
.......###
###.......
...###....
......###.
..#..##...
但是对于 \(n = 7\) 要特判。
然后是 \(n = 3k - 1\) ，考虑从上面的 \(n = 3k\) 删去最后一行和一列。
11
###.....
...###..
1......##
###.....
...###..
1......##
###.....
...###..
然后在这些 1 在行列方向相互对出的点上选两个 # 就好了，但是这上面已经有 # 了。
然后有一个非常迷惑的操作：
#.
.#
变成
.#
#.
每行每列的数量是不变的，然后构造：
###.....
...##.#.
.....###
###.....
...##.#.
.....###
###.....
...###..
AGC055A
statement
给一个长为 $3\times N$ 的由 `A` `B` `C` 构成的字符串，其中 `A` `B` `C` 各有 $N$ 个。要求将原字符串分成 \(i\ (1\le i \le 6)\) 个子序列，使得每个子序列 \(T\) 满足：
- \(|T| = 3k, k\in Z\)
- \(T_1 = T_2 = \cdots = T_k\)
- \(T_{k + 1} = T_{k + 2} = \cdots = T_{2k}\)
- \(T_{2k + 1} = T_{2k + 2} = \cdots = T_{3k}\)
求一种构造方案。
solution
首先有一个发现 \(3! = 6\) 。
有两个想法，一个想法是做六遍，每次标记每一种的可能情况，还有一个就是对于每一个位置分别直接确定它属于哪个数字。
但是仅此而已是不够的，因为 \(3! = 6\) 的性质不足以对付形如 AAAABBBBCCCC 子序列，每一个 B 都在 A 后面的要求。
那我们对于每一种子序列，将左边、中间、右边三部分都定义成一个区间，左端点是最左边的位置，右端点是最右边的位置。
然后整个字符串 \(S\) 能被拆成 \(n\) 个形如 ABC/ACB/.../CBA 的子序列，那么你把中间的部分规范到区间 \([\frac{n}{3} + 1, \frac{2n}{3}]\) 中，然后就做完了。
AGC054A
statement
给一个长为 \(N\) 的字符串 \(S\) ，每次可以删去一个头尾不同的连续子串，求最少操作次数，如果无解，输出 -1 。
solution
一坨毒瘤中的小清新。
答案为 \(1\) 时，首尾不同，答案为 \(2\) 时，逐个判断即可。
考虑答案大于 \(2\) 的情况。
如 a----ba---bb----a ，那么必然存在一种方案减少一次操作。
所以答案只能是 \(-1, 1, 2\) 。
AGC054C
statement
Snuke 拿到了一个长为 \(N\) 的排列 \(P = (P_1, P_2, \cdots, P_N)\) 和一个整数 \(K\) ，现在 Snuke 可以使用交换两个相邻元素的操作，使得最后的排列 \(P'\) 满足以下条件：
- 对于任意 \(1\le i\le N\) ，最多不超过 \(K\) 个 \(j\) 满足 \(1\le j < i\) 且 \(P_j > P_i\) 。
由于 Snuke 是神，他总是以最优策略进行交换。
过了几天，Snuke 忘记了原排列是什么，就给你了最终的 \(P'\) ，要你求出原来的 \(P\) 一共可能有多少个，答案对 \(\rm 998244353\) 取模。
solution 2022.1.25
这个题做的异常顺利（大概
首先这个题肯定和冒泡排序和逆序对有关，先记一下 \(d_i = \sum_{1\le j < i} [P_j > P_i]\) 。
然后你发现，对于 \(d_i < K\) 的情况是和计数没有任何关系的，所以重点就放在了那些 \(d_i = K\) 的位置上。
但是搞不下去了，怎么办？ 寻找更多关于 \(P\) 和 \(d\) 之间的性质！
首先发现 \(P_i > P_{i + 1} \Rightarrow d_i < d_{i + 1}\) 以及 \(P_i < P_{i + 1} \Rightarrow d_i > d_{i + 1}\)
然后从排列 \(P\) 中拉出一段 \(P_i > P_{i + 1} < P_{i + 2} < \cdots < P_{o}\) ，那么 \(d_{i + 1} > d_{i + 2} > \cdots > d_{o}\) 。
然后在最理想的情况下，移动次数应当是 \(\sum [d_i > K] (d_i - K)\) 。
然后你发现，在上面拉出来最有可能暴毙的一段，如果从左到右枚举 \(P_{i + 1}\) 到 \(P_{o}\) ，一个一个的走满 \(d_i - K\) 步，也没有问题。
之后就爽了，因为操作是可逆的，每个 \(P'\) 中 \(=K\) 的元素向右移动不同位置后所组成的排列也是不同的。
所以答案就是 \(\prod (n - i + 1) ^ {[d_i = K]}\) 。