题目大意:k个好人,k个坏人,确定n,利用Joseph方法删除所有坏人.
由于数据规模,可以利用暴力打表,以后能打表就尽量打表。
这题原本模拟数据时间完全够的,但是测试数据有很多重复的,导致很多人超时,暗坑!!!!
以后要注意点这种情况。
打表:
#includeint main(){ int n,a[14]={ 0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881}; while(scanf("%d",&n)&&n) printf("%d\n",a[n]); return 0;}
/*
题目总结: 注意学习,模拟约瑟夫循环的过程!三个方程:
kill=(ans+ans - 1)%sum //下一处要删除的位置
if(kill==0)kill=sum; //为零的特殊情况
sum--; //人数减一
*/
#include#include #include #include #include using namespace std;int res[16];int joseph(int n){ int ans, flag, sum; if(res[n]) return res[n]; else { for(ans = n + 1; ; ++ans) { flag = 0; sum = 2 * n; for(int j = ans; ; j += ans - 1) //人数减1 { if(j > sum) j = j % sum ? j % sum : sum; //人数减1 if(j <= n) break; else sum--; if(sum == n) { flag = 1; break; } } if(flag) { res[n] = ans; return res[n]; } } }}int main(){ int n; while(cin>>n,n) { cout< <