luogu P1146 硬币翻转
2024-08-25 00:47:14
题目描述
在桌面上有一排硬币,共N枚,每一枚硬币均为正面朝上。现在要把所有的硬币翻转成反面朝上,规则是每次可翻转任意N-1枚硬币(正面向上的被翻转为反面向上,反之亦然)。求一个最短的操作序列(将每次翻转N-1枚硬币成为一次操作)。
输入输出格式
输入格式:
输入只有一行,包含一个自然数N(N为不大于100的偶数)。
输出格式:
输出文件的第一行包含一个整数S,表示最少需要的操作次数。接下来的S行每行分别表示每次操作后桌上硬币的状态(一行包含N个整数(0或1),表示每个硬币的状态:0――正面向上,和1――反面向上,不允许出现多余空格)。
对于有多种操作方案的情况,则只需字典序最小输出一种。
输入输出样例
输入样例#1:
4
输出样例#1:
4
0111
1100
0001
1111
设翻了x次,总共翻了y轮(指翻过的硬币数除以这排的硬币数)
由题意得:x*(n-1)=y*n
因为n为偶数,n-1为奇数
所以x为偶数
又n与n-1互质
当x,y最小时
x=n y=n-1 所以,只要翻n次
剩下的靠样例理解
当然处理时可以用位运算
以上摘自luogu题解
#include<cstdio> int n,a[]; int main()
{
scanf("%d",&n);
printf("%d\n",n);
for(int i=,k=;i<=n;i++,k++)
{
for(int j=;j<n;j++)
a[(j+k-)%n+]^=;
for(int j=;j<=n;j++)
printf("%d",a[j]);
printf("\n");
}
return ;
}
最新文章
- ContentProvider中央档案馆,以及获取联系人电话的示例
- 【WP8】WebBrowser相关
- [IOS基础]关于IOS的UIScreeen,UIView,UIViewController,UIWindow理解
- Xcode UUID查询
- java 反取字符串
- BW标准数据源初始化设置
- 小菜鸟学 MQ(三)
- Android实现简单短信发送器
- [HBuilder] 简介
- Python中下划线---完全解读
- 翻译 异步I/O不会创建新的线程
- 适合使用并行的一种bfs
- Spring 学习笔记(二)
- 解决XP系统任务管理器显示不全
- [UE4]游戏中服务器切换地图,控制台命令Execute console Command
- DNS主从复制及子域(三)
- JAVA-JSP之taglib指令
- CentOS 7上搭建Docker环境
- C#单元测试:NUnit详细使用方法
- Spring框架中用到的设计模式(转)
热门文章
- 每天一个Linux命令(11):cat命令
- cookie换肤功能
- ACM基础算法入门及题目列表
- 基于linux操作系统安装、使用memcached详解
- JS XMLHttpRequest.upload.addEventListener 传参,回调
- VMware 密匙
- Nginx与Tomcat集成
- 【bzoj1875】[SDOI2009]HH去散步 矩阵乘法
- 【bzoj1195】[HNOI2006]最短母串 AC自动机+状态压缩+BFS最短路
- 笔记:CS231n+assignment2(作业二)(三)