有一串数,长度为K(K≤100000),从开头开始数,数到1,则这个数标为1,然后删除这个数,继续往后重新数2个,这个数标为2,然后删除这个数。如果后面没有数了就又回到开头继续。像这样:
1 · 2 · · 3 · · · 4 · · · · 5 · · · · · 6 · ·
继续:
1 · 2 · · 3 ·7· 4 · · · · 5 · · 8· · 6 · ·
(解释不清楚。。。有点像tldds,但是每次数的个数+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)