[ACM] POJ 1218 THE DRUNK JAILER (关灯问题)
版权声明:本文为博主原创文章,未经博主同意不得转载。 https://blog.csdn.net/sr19930829/article/details/37727417
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 23246 | Accepted: 14641 |
Description
One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the
hall locking every other cell (cells 2, 4, 6, ?
). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He
repeats this for n rounds, takes a final drink, and passes out.
Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.
Given the number of cells, determine how many prisoners escape jail.
Input
Output
Sample Input
2
5
100
Sample Output
2
10
Source
解题思路:
题意为n个监狱,编号1到n,初始均关闭,进行n局游戏,第一局,把全部的监狱都打开,第i(i>=2)局,把编号为 i 的倍数的监狱的状态改变(打开变为关闭或关闭变为打开)。问n局游戏以后,有多少个监狱为打开状态。 用d[]数组来保存监狱的状态。模拟n局游戏就能够了。
代码:
#include <iostream>
#include <string.h>
#include <stack>
#include <iomanip>
#include <cmath>
using namespace std;
bool d[110];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int cnt=0;
memset(d,0,sizeof(d));
for(int i=2;i<=n;i++)
{
for(int j=i;j<=n;j+=i)
d[j]=1-d[j];//状态改变
}
for(int i=1;i<=n;i++)
if(d[i]==0)
cnt++;
cout<<cnt<<endl;
}
return 0;
}
最新文章
- AutoMapper指定列名进行映射
- es2自动发现插件
- iOS开发--应用设置及用户默认设置——转载
- contentprovider的学习实例总结
- Oracle数据库中的违规策略规则的修正
- 微软分布式缓存 appfabric
- SQL Server 基础 02 确保数据完整性
- ajax异步请求实例
- Study notes for Latent Dirichlet Allocation
- Linux经常使用的命令(必看)
- oss滤网图片音视频过滤(1)内容检测
- tomcat部署项目
- LeetCode练习3 找出一个字符串中最大不重复子字符串的长度
- nginx 开启高效文件传输模式
- linux下(Window当然也可以)解决idea创建maven项目导入过慢问题
- JavaScript——执行环境、变量对象、作用域链
- C# 调用 C++ 的 DLL 返回值为 bool 时,值混乱
- Swift:宏定义
- SSH框架整合过程总结
- Redis数据类型之SDS简单动态字符串
热门文章
- linux中的常用信号
- python第一个问题
- [fw]谈EXPORT_SYMBOL使用
- java并发编程之美-阅读记录6
- SQL数据库—<;7>;事务、异常和游标
- mybatis的缓存机制及用例介绍
- web前端架构师学习流程
- windows服务器装macos虚拟机(vmware)系统
- Rectangle类详解
- [BOOKS]BIG DATA and DATA ANALYTICS: The Beginner&#39;s Guide to Understanding the Analytical World