P3988-[SHOI2013]发牌
题目:
题目描述:
在一些扑克游戏里，如德州扑克，发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前，先要销牌（burn card）。所谓销牌，就是把当前在牌库顶的那一张牌移动到牌库底，它用来防止玩家猜牌而影响游戏。
假设一开始，荷官拿出了一副新牌，这副牌有 $N$ 张不同的牌，编号依次为 $1$ 到 $N$。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为 $1,2,\cdots,N$，$N$ 号牌在牌库底。为了发完所有的牌，荷官会进行 $N$ 次发牌操作，在第 $i$ 次发牌之前，他会连续进行 $R_i$ 次销牌操作，$R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？
举个例子，假设 $N=4$，则一开始的时候，牌库中牌的构成顺序为 $1,2,3,4$。
- 假设 $R_1=2$，则荷官应该连销两次牌，将 $1$ 和 $2$ 放入牌库底，再将 $3$ 发给玩家。目前牌库中的牌顺序为 $4,1,2$。
- 假设 $R_2=0$，荷官不需要销牌，直接将 $4$ 发给玩家，目前牌库中的牌顺序为 $1,2$。
- 假设 $R_3=3$，则荷官依次销去了 $1,2,1$，再将 $2$ 发给了玩家。目前牌库仅剩下一张牌 $1$。
- 假设 $R_4=2$，荷官在重复销去两次 $1$ 之后，还是将 $1$ 发给了玩家，这是因为 $1$ 是牌库中唯一的一张牌。
输入格式:
第一行，一个整数 $N$，表示牌的数量。
第二行到第 $N+1$ 行，在第 $i+1$ 行，有一个整数 $R_i$。
输出格式:
共 $N$ 行，第 $i$ 行有一个整数，表示玩家收到的第 $i$ 张牌的编号。
样例:
样例输入1:
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| // Problem: P3988 [SHOI2013]发牌
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3988
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/BIT.h"
#include "ybwhead/ios.h"
CPTH::BIT<int> x;
int add(const int &x, const int &y)
{
return x + y;
}
const int maxn = 7e5 + 10;
int pre[maxn], nxt[maxn];
int n;
inline int search(int l, int r, int sum)
{
int ret = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (x.query(mid) >= sum)
ret = mid, r = mid - 1;
else
l = mid + 1;
}
return ret;
}
int main()
{
yin >> n;
for (int i = 1; i <= n; ++i)
pre[i] = i - 1, nxt[i] = i + 1;
x.init(n, add, 0);
pre[1] = n,
nxt[n] = 1;
for (int i = 1; i <= n; i++)
x.add(i, 1);
int p = 1;
for (int i = n; i >= 1; i--)
{
int xx;
yin >> xx;
xx %= i;
++xx;
int sum = x.query(n) - x.query(p - 1);
if (xx > sum)
yout << (p = search(1, p - 1, xx - sum)) << endl;
else
yout << (p = search(p, n, xx + x.query(p - 1))) << endl;
pre[nxt[p]] = pre[p];
nxt[pre[p]] = nxt[p];
x.add(p, -1);
p = nxt[p];
}
return 0;
}
|