[ACM-ICPC][Asia - Seoul][殺人遊戲][模擬解] 4727 - Jump
Integers
1, 2, 3,..., n are placed on a circle in the increasing order
as in the following figure. We want to construct a sequence from these
numbers on a circle. Starting with the number 1, we continually go round
by picking out each k-th number and send to a sequence queue until all
numbers on the circle are exhausted. This linearly arranged numbers in
the queue are called Jump(n, k) sequence where 1
n, k.
Let us compute Jump(10, 2) sequence. The first 5 picked numbers are 2, 4, 6, 8, 10 as shown in the following figure. And 3, 7, 1, 9 and 5 will follow. So we get Jump(10, 2) = [2,4,6,8,10,3,7,1,9,5]. In a similar way, we can get easily Jump(13, 3) = [3,6,9,12,2,7,11,4,10,5,1,8,13], Jump(13, 10) = [10,7,5,4,6,9,13,8,3,12,1,11,2] and Jump(10, 19) = [9,10,3,8,1,6,4,5,7,2].
You write a program to print out the last three numbers of Jump(n, k) for n, k given. For example suppose that n = 10, k = 2, then you should print 1, 9 and 5 on the output file. Note that Jump(1, k) = [1].
Input
Your program is to read the input from standard input. The input consists
of T test cases. The number of test cases T is given in the first line
of the input. Each test case starts with a line containing two integers
n and k, where
5n500, 000 and
2k500, 000.
Output
Your program is to write to standard output. Print the last three numbers of Jump(n, k) in the order of the last third, second and the last first. The following shows sample input and output for three test cases.
Sample Input
3 10 2 13 10 30000 54321
Sample Output
1 9 5 1 11 2 10775 17638 23432
為了加快模擬速度, 採用 zkw式ST, 單一測資是 O(nlogn)
#include <stdio.h>
int st[1<<20];
int main() {
int n, k, i, j;
int t;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
int M;
for(M = 1; M < n+1; M <<= 1);
for(i = 2*M-1; i > 0; i--) {
if(i >= M)
st[i] = 1;
else
st[i] = st[i<<1]+st[i<<1|1];
}
int m, last, prev = 0, s;
for(i = 1; i <= n; i++) {
m = (k+prev)%(n-i+1);
if(m == 0)
m = n-i+1;
prev = m-1;
for(s = 1; s < M;) {
if(st[s<<1] < m)
m -= st[s<<1], s = s<<1|1;
else
s = s<<1;
}
last = s-M+1;
if(i > n-3) {
if(i > n-2) putchar(' ');
printf("%d", last);
}
while(s) {
st[s] --;
s >>= 1;
}
}
puts("");
}
return 0;
}
上一篇：[ACM-ICPC][Asia - Seoul][Farthest Pair] 4728 - Squares
下一篇：[ACM-ICPC][Asia - Seoul][Greedy+dp] 4731 - Cellular Network