【codejam

题目大意：

有一串数，长度为K(K≤100000)，从开头开始数，数到1，则这个数标为1，然后删除这个数，继续往后重新数2个，这个数标为2，然后删除这个数。如果后面没有数了就又回到开头继续。像这样： 1 · 2 · · 3 · · · 4 · · · · 5 · · · · · 6 · · 继续： 1 · 2 · · 3 ·7· 4 · · · · 5 · · 8· · 6 · · （解释不清楚。。。有点像约瑟夫环，但是每次数的个数+1） 有n(n≤100)次询问，询问最后标号的数列的 di 位置是什么数。

分析：

原题解地址：https://code.google.com/codejam/contest/32017/dashboard#s=a&a=2

模拟：

直接暴力模拟：

O(K2) TIME LIMIT EXCEED

K−−√ 分块：

将序列分为 K−−√ 块，模拟，当一块全部被删去时，就可以直接跳过，时间复杂度 O(K1.5)

线段树模拟：

O(logK) 的删除操作，时间复杂度 O(KlogK)

神奇方法：

考虑我们只计算要询问的值。 当我们要删除一个数时，可以将后面整个序列往前移一位，即把后面的询问全部-1。这样，每次向后面数个数时，就可以直接用加法处理：pos=(pos+(i-1))%(K-(i-1))(pos表示当前要删的数的前一个，必须是前一个，如果pos表示当前那个数，因为这个数被删掉了，下次往下计算时就会多走一个）如果走到位置刚好是询问，则保存到答案数组里去。 时间复杂度 O(Kn)

最优方法代码：

#include<cstdio> #define MAXK 1000005 #define MAXN 105 int Q[MAXN],ans[MAXN]; int main() { int T,K,n; scanf("%d",&T); for(int Case=1;Case<=T;Case++) { scanf("%d%d",&K,&n); for(int i=1;i<=n;i++) { scanf("%d",Q+i); ans[i]=0; } for(int i=1,pos=0;i<=K;i++) { pos=(pos+i-1)%(K-(i-1)); for(int j=1;j<=n;j++) if(!ans[j]) { if(Q[j]==pos+1) ans[j]=i; else if(Q[j]>pos+1) Q[j]--; } } printf("Case #%d:",Case); for(int i=1;i<=n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; }