CF 1365 题解
A Matrix Game
注意到每次操作都相当于会损失一行和一列, 那么最多进行可用行列较少的那一个的轮数. 判断奇偶性即可,
B Trouble Sort
手玩发现, 不管一个属性的元素集合内部多么无序, 都可以借助一个其它属性的元素达到有序.
归纳证明特别简单.
因此, 一个序列可以被排序当且仅当它已经有序或者包含多种元素.
C Rotation Matching
由于两个序列都是排列, 只需要枚举值, 每一个值都有唯一的偏移量使得它对答案有贡献.
开个桶记录每个偏移量能获得多少答案, 找最大值即可.
D Solve The Maze
考虑贪心.
发现把每个坏人当场用墙围住一定比延后封闭更优.
因此把坏人周围建墙后判断好人到终点的可达性即可.
E Maximum Subsequence Value
首先, \(n\leq3\) 的情况特别平凡.
其次, 考虑选择大小不超过 \(3\) 的集合, 那么贡献是这三个元素按位或, 可得所选集合一定不小于 \(3\).
考虑选择大小不小于 \(3\) 的集合.
结论: 若选择一个集合 \(S\) , 且 \(|S|\geq 3\) , 那么总存在一个三元集 \(A\subseteq S\) , 使得 \(A\) 比 \(S\) 不劣.
证明:
记集合 \(Q\) 对答案贡献为 \(w(Q)\).
首先考虑任意选择一个元素 \(x\in S\), 那么对于每一个 \(w(S)\) 中有而 \(w(A)\) 没有的二进制位, 都满足它在 \(S\) 中只有 \(x\) 和另一个位置 \(y\) 处不存在. 这时再选择一个异于 \(x\) 的位置 \(k\) , 这时对于每一个 \(w(S)\) 中有而 \(w(A)\) 没有的二进制位, 都满足它在 \(S\) 中只有 \(x\) 和 \(k\) 处不存在.
这时再选择一个异于 \(x\) 和 \(k\) 的位置, 就有 \(w(A)\geq w(S)\).
因此这道题只要 \(O(n^3)\) 枚举三元集就可以了.
F Swaps Again
考虑两个关于中心点对称的元素, 发现交换后关于中心依然对称.
因此判断这个条件加上中心点不变就可以了.
G Secure Password
考虑把每个元素重标号为一个 \(13\) 位的二进制数, 并且其中恰有 \(6\) 个 \(1\).
考虑查询每个第 \(i\) 位是 \(1\) 的集合中的元素, 然后第 \(k\) 个元素的答案就是它的标号所有 \(0\) 的位对应答案的按位或.
原因在于我们约束每个元素标号所含 \(1\) 的个数一致, 因此标号不存在子集关系, 对于每一个 \(i\) 和 \(j\not=i\), 都存在一个二进制位 \(x\) 使得 \(i\) 中为 \(0\) , \(j\) 中为 \(1\).
标签:标号,一个,题解,元素,CF,二进制位,1365,集合 From: https://www.cnblogs.com/snowycat1234/p/18534664