LA 3882

时间:2023-11-13 13:38:08

动态规划;

白书上的题,看了好久看不懂刘汝佳的解法;

在网上无意中看到了大神的思路,比较好理解,膜拜!

他的思路是这样的:

设d[i]是n个数按顺时针方向分别从0开始编号,第一次删除0,以后每k个数删除一个,最后剩下的数。

实际上d[i]就是顺时针偏移了多少位。

状态转移方程:

d[i] = (k - 1 + d[i-1]) % (n-1) + 1;

(删了0后,剩下1,2,...,n,全部减1后得到0,1,2,...,n-1,所以原来该删k——>>k-1,顺时针偏移d[i-1]位,取模,加1后变回原来的编号)

代码:

 #include<cstdio>
#define maxn 10009
using namespace std;
int d[maxn]; int main()
{
int n,m,k;
d[]=;
while(scanf("%d%d%d",&n,&k,&m)&&(m+n+k))
{
for(int i=;i<=n;i++)d[i]=(d[i-]+k-)%(i-)+;
int ans=(m-+d[n])%n+;
printf("%d\n",ans);
}
return ;
}