博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【枚举】AtCoder Regular Contest 095 C - Symmetric Grid
阅读量:6678 次
发布时间:2019-06-25

本文共 724 字,大约阅读时间需要 2 分钟。

题意:给你一个H*W的字符矩阵,一次操作可以任意将两行或者两列交换。问你是否能通过任意多次操作,使得其变为对称矩阵。对称的含义是:对于任何格子A(i,j),其都等于A(H-i+1,W-j+1)。

显然,先换行还是列不影响结果,不妨假设先换行再换列。

行不必真换,只需找出哪些行成对即可,然后这些对的顺序无关,这样的方案数只有1*3*5*7*...*n,只有10000左右。

这个怎么枚举呢,假设行数是1,2,3,4,5,6,

那么就(1,2)-(3,4)-(5,6)

     -(3,5)-(4,6)

     -(3,6)-(4,5)

   (1,3)-(2,4)-(5,6)

     -(2,5)-(4,6)

     -(2,6)-(4,5)

   (1,4)-(2,3)-(5,6)

     -(2,5)-(3,6)

     -(2,6)-(3,5)

   (1,5)-(2,3)-(4,6)

     -(2,4)-(3,6)

     -(2,6)-(3,4)

   (1,6)-(2,3)-(4,5)

     -(2,4)-(3,5)

     -(2,5)-(3,4)

就每次枚举一对后,下一对(x,y)的x一定选上次空出来的第一个位子,y去枚举其他位子即可。

行数如果是奇数 类似,最后会剩下一个。

这样枚举完行,再去check列,假设列数为偶数,则每次对于一列,找是否有与其的逆序相等的列,如果有 则配对成功。最后看看是否都能配对成功。

如果列数是奇数,还必须有一列单独的回文列放在(W+1)/2列的位子。

转载于:https://www.cnblogs.com/autsky-jadek/p/8837951.html

你可能感兴趣的文章
epoll的LT和ET模式
查看>>
Android IOS WebRTC 音视频开发总结(六四)-- webrtc能走多远我不知道,但这个市场真实存在...
查看>>
使用yum高速部署Oracle安装环境(11g)
查看>>
Js~(function(){})匿名自执行方法的作用
查看>>
String.format格式化
查看>>
android的快速开发框架集合
查看>>
yaffs2物理存储
查看>>
Spring入门导读——IoC和AOP
查看>>
iSCSI存储系统知识
查看>>
一步一步学ROP之linux_x64篇
查看>>
Kali linux 2016.2(Rolling)里的应用更新和配置额外安全工具
查看>>
js 实现图片实时预览
查看>>
Java 8 Optional类深度解析
查看>>
联想还是那个联想吗?
查看>>
com.panie 项目开发随笔_前后端框架考虑(2016.12.8)
查看>>
BZOJ 3529: [Sdoi2014]数表 [莫比乌斯反演 树状数组]
查看>>
ubuntu12.04中shell脚本无法使用source的原因及解决方法
查看>>
备忘录模式
查看>>
git 如何更改某个提交内容/如何把当前改动追加到某次commit上? git rebase
查看>>
eclipse里将java工程改web工程
查看>>