【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 递推 , 385 阅读

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

  不过也是很显然的一个递推,记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;
}
Avatar_small
AP 1st Inter Botany 说:
2022年9月08日 19:46

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Model Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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