【BestCoder Round #75 1005】King's Pilots

【BestCoder Round #75 1004】King's Game

Zarxdy34 posted @ 2016年3月13日 09:53 in BestCoder with tags 递推 , 226 阅读

  考时自然是交了个表上去。

  不过也是很显然的一个递推,记f[n][i]表示剩n个人,按照隔i,i+1,i+2,i+3,...i+n-2个人出队的顺序最终幸存者的编号。(为了方便先把人按0...n-1编号)

  那么递推式就是\(f[n][i]=(f[n-1][i+1]+i)\ mod\ i\),边界条件\(f[1][i]=0\)。n个人时幸存者即为\(f[n][1]+1\)。

 

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5010;

int f[2][maxn];
int ans[maxn];
int n,T;

int main()
{
	for (int i=1;i<=5000;i++)
	{
		int o=i&1,po=o^1;
		for (int j=1;j+i<=5005;j++) f[o][j]=(f[po][j+1]+j)%i;
		ans[i]=f[o][1]+1;
	}
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter