博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Power Crisis
阅读量:4979 次
发布时间:2019-06-12

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

这道题被严重恶意评分了,实际应该是绿题。

因为其实我们只需要模拟即可。这里我们引入一种新的东西:约瑟夫环。

它能直接告诉你约瑟夫问题中最后一个存活下来的人是谁。(不过下标是从0开始的,实际使用的时候需要+1)

如果有n个人,每次报到m的时候出列,那么令f[i]表示有i个人的时候最后存活的人的下标,那么有f[i+1] = (f[i] + m) % i,其中f[0] = 0;

怎么推的呢?对于一个序列,在长度相同的时候,获胜的人应该是固定的,我们假设现在报到m的人出列了,下一个人(m+1)成为了队首,其实相当于所有人往前移动了m位.那么倒着退回去,我们也就能知道其实获胜的人相对应向后移了m位,不过因为人数在增加,所以我们要每次%i。

对于这道题,因为1已经出去了,所以我们要求的就是n-1的约瑟夫环的最小m,使得f[n-1] = 11,这样我们模拟即可。

看一下代码。

#include
#include
#include
#include
#include
#include
#include
#define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')using namespace std;typedef long long ll;const int M = 10005;const int INF = 1000000009;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}int n;int main(){ while(1) { n = read(); if(!n) break; rep(i,1,n-1) { int k = 0; rep(j,1,n-1) k = (k + i) % j; if(k == 11) { printf("%d\n",i); break; } } } return 0;}

 

转载于:https://www.cnblogs.com/captain1/p/9886302.html

你可能感兴趣的文章
POJ 1308 Is It A Tree?(并查集)
查看>>
N进制到M进制的转换问题
查看>>
springIOC第一个课堂案例的实现
查看>>
求输入成绩的平均分
查看>>
php PDO (转载)
查看>>
wordpress自动截取文章摘要代码
查看>>
[置顶] 一名优秀的程序设计师是如何管理知识的?
查看>>
highcharts 图表实例
查看>>
highcharts曲线图
查看>>
extjs动态改变样式
查看>>
宏定义
查看>>
笔记:git基本操作
查看>>
生成php所需要的APNS Service pem证书的步骤
查看>>
JavaWeb之JSON
查看>>
HOT SUMMER 每天都是不一样,积极的去感受生活 C#关闭IE相应的窗口 .
查看>>
optionMenu-普通菜单使用
查看>>
【MemSQL Start[c]UP 3.0 - Round 1 C】 Pie Rules
查看>>
Ognl中“%”、“#”、“$”详解
查看>>
我对应用软件——美团的看法
查看>>
struts2.x + Tiles2.x读取多个xml 配置文件
查看>>