[USACO 1.5.4]checker(水题重做——位运算(lowbit的应用))
2024-08-24 22:24:57
描述
检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
0 1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式),这是作弊。如果你坚持作弊,那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了!
[编辑]格式
测试时间: 1s
程序名: checker
输入格式:
(checker.in)
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式:
(checker.out)
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
[编辑]SAMPLE INPUT
6
[编辑]SAMPLE OUTPUT
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
lowbit除了树状数组外还可以用于这类搜索的位运算优化里,翻JZP大神的博客发现的……
http://hi.baidu.com/oimaster/item/d359b712bb59fd0bd1d66d42
最新文章
- 自己动手写计算器v1.1
- 告别IT,出售多年自己研发的股票分析系统源码
- python面向对象进阶 反射 单例模式 以及python实现类似java接口功能
- Counterfeit Dollar -----判断12枚钱币中的一个假币
- 修復jquery的tablesorter对加了千分位的数字无法正确排序的bug
- POJ 1436 (线段树 区间染色) Horizontally Visible Segments
- Java 学习 第二篇;面向对象 定义类的简单语法:
- [置顶] 小伙伴们来自己实现LinkedList
- Hibernate学习笔记(1)Hibernate构造
- angularJS的一些用法
- PHP大文件分割上传(分片上传)
- 测试一下OpenLiveWriter
- 项目分层-----MVC
- js数组删除元素、json删除元素
- Windows 虚拟机 忘记密码的处理
- 转载:小结(1.7)《深入理解Nginx》(陶辉)
- Servlet (二)ServletContext
- Linux下清空或删除大文件内容的2种方法
- LeetCode--012--整数转罗马数字(java)
- Quartz.NET基础知识概述
热门文章
- myeclipe eclipse 常遇问题:Some projects cannot be imported 、java.lang.ClassNotFoundException: oracle.jdbc.driver.OracleDriver、The file connot be validate
- Eclipse中修改SVN用户名和密码方法(转)
- 【Android UI设计与开发】10:滑动菜单栏(二)SlidingMenu 动画效果的实现
- 怎么运用ZBrush中的Z球制作身体部分
- WPF窗口阴影和夜间模式的实现
- Oracle导入导出dmp文件
- 分层开发(MySchool总结)
- Android service ( 二) 远程服务
- Rdlc报表出现空白页解决方法(转)
- 解决centos7重启后出现ata bus error