AGC006

AtCoder Grand Contest 006

C - Rabbit Exercise

推式子发现该操作就是把坐标差分的期望序列中相邻两项互换, 于是做完. ## D - Median Pyramid Hard 看到排列, 并且与排序相关, 显然二分答案变成01序列做. ## E - Rotate 3x3 首先发现每一列都一定是\(\{3k,3k+1,3k+2\}\),并且奇偶列之间不会交换. 于是变成了分奇数与偶数列的冒泡排序问题, 同时需要考虑每一列的方向变化. ### 法一 直接模拟冒泡排序, 计算每一列拍完序的方向. 时间\(O(n\log n)\), 实现繁琐. ### 法二 题解的神仙做法. 如果分别计数不考虑方向合法性的合法序列个数与实际合法的序列数(暴搜), 发现正好是4倍关系, 这隐含着两组对称性. 考虑以偶数列为中心的操作, 每次既改变了奇数列排列的奇偶性, 也改变偶数列反方向列个数的奇偶性. 于是计算排列的奇偶性和反向列的个数对比即可判定合法性. ## F - Blackout 神仙题! 首先手玩几个数据, 将发现可以连的边与\((d(x,z)\mod 3)\)有关. 如果把图3-染色, 发现每个点只能与下一个颜色的点连边. 对于一个弱连通块, 存在如下结论: 1. 如果不存在\((x,y), (y,z)\), 显然不能连边. 2. 如果可以3-染色, 则两种相邻颜色的所有点之间都可以连边. (可以不断进行迭代, 最后每一组边都一定可以被两个相邻的边表示出来) 3. 如果不能3-染色, 则任意点之间都可以连边. (考虑一定存在环长不为3的倍数的环, 不断分割就可以得到自环, 由于弱联通, 可以从自环出发, 得到它与所以点组成的二元环, 最终得到所有的自环, 就可以构造任意边了)

于是把图划分连通块染色即可.