这道题被严重恶意评分了,实际应该是绿题。
因为其实我们只需要模拟即可。这里我们引入一种新的东西:约瑟夫环。
它能直接告诉你约瑟夫问题中最后一个存活下来的人是谁。(不过下标是从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;}