-problem: 一个(2n+1)*(2n+1)的网格, n<=20, 里面是'+'或'-'. 每次可以同时翻转2n+1个格子, 使'+'变成'-'或者反之, 要求这2n+1个格子的行, 列都不相同. 现在要你输出翻转步骤, 使得最后'+'的数量不超过2n. solution: 贪心. 关键是如何用两次操作翻转一个矩形的4个角. ----link: http://acm.timus.ru/problem.aspx?space=1&num=1092 ----code: https://docs.google.com/document/pub?id=1sEOzqZiI9kz-qBkkSjblq9_PafP8xCg2rrhw17CKGD0
看的题解: http://www.nocow.cn/index.php/URAL/1092
关键是如何用两次操作翻转一个矩形的4个角, 上述网址里的方法只能针对矩形左上角正好是网格左上角的情况.
比较好的方法是用一个数组标记不可用的列.
另外上述网址里的”折脚”剩余一个’+'跟’+'的数量是奇数的关系我也没看懂.
我用的另外的方法.
仍然基于翻转矩形4个角的方法.
可以从上到下一行一行来, 每一行要么消除干净, 要么剩下一个’+', 那么就把剩下的这一个移到最右边.
最后一行不处理, 则此时网格可能像这样:
----+ ----+ ----- ----+ ++--+
这样将最右边和最下边除了右下角的’+'两两配对, 以网格右下角为矩形右下角做翻转. 结果就是这样:
+---- -+--- ----- ----+ ----+
这样只要在两两配对之前剩下的’+'是偶数就可以保证最多剩下2n个’+’.
原因是之前针对行的操作并不改变’+'数量的奇偶性.
而后来的配对操作每次消除1个’+'(右下角’-'变’+'), 或者3个’+'(右下角’+'变’-'). 仍然不改变奇偶性.
而最右边或最下边除了右下角, 总有一边上的’+'被清空了, 又最后’+'总数是偶数个, 所以最多剩下2n个.
Post a Comment