HDU 5565 - Clarke and baton (思维)
题意
克拉克是一名人格分裂患者。某一天，克拉克fork出了nn个自己，序号从11到nn。 他们准备玩一个减肥游戏，每一个克拉克都有一个体重a[i]a[i]。他们有一个接力棒，这个接力棒任何时刻总是在最重的克拉克（如果重量相同则在序号最小的）的手中，得到这个接力棒的克拉克需要减肥，使得体重变成a[i]-1a[i]−1，随后接力棒便传递到下一个人（可以是自己）的手中。 现在克拉克们知道接力棒一共被传递过qq次，他们想知道最终每一个克拉克的体重分别是多少。
思路
官方题解讲得挺详细了。引用一下。
我们首先计数排序，即开个可变长数组a来将所有值为i的下标按顺序存入a[i]中。然后再开个可变长数组b，用b[i]来存储由a[i+1]降到i的数。然后考虑从大到小枚举值i，首先从b[i]和a[i]中找一个下标最小的数j，弹出，更新了这个j的值后，插入到b[i-1]中。依次类推即可。时间复杂度$O(Tq)$。
也就是说，我们来回倒腾两个数组就行了。
一开始直接用STL queue，爆空间了。于是就写了一个简易版queue。
代码
#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
#include <climits>
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 1e7+10;
const int MOD = 1e9 + 7;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//const int seed = 131;
int cases = 0;
typedef std::pair<int, int> pii;
struct Queue
{
vector<int> G;
int pos;
Queue() : pos(0) {}
int front()
{
return G[pos];
}
void pop()
{
++pos;
}
bool empty()
{
return pos == SZ(G);
}
void push(int &n)
{
G.push_back(n);
}
}initial[MAXN], revised[MAXN];
int a[MAXN], n, q;
long long seed;
int rand(int l, int r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}
void init()
{
int sum=rand(q, 10000000);
for(int i=1; i<=n; i++) {
a[i]=rand(0, sum/(n-i+1));
sum-=a[i];
}
a[rand(1, n)]+=sum;
for (int i = 1; i < MAXN; i++)
{
initial[i].G.clear();
initial[i].pos = 0;
revised[i].G.clear();
revised[i].pos = 0;
}
initial[0].G.clear();
revised[0].G.clear();
}
int ans[MAXN];
inline void update(Queue &cur, int pos)
{
int u = cur.front(); cur.pop();
revised[pos-1].push(u);
ans[u] = pos - 1;
}
int main()
{
//ROP;
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%I64d", &n, &q, &seed);
init();
for (int i = 1; i <= n; i++)
{
initial[a[i]].push(i);
ans[i] = a[i];
}
int pos = MAXN - 1;
while (q--)
{
while (pos >= 1 && initial[pos].empty() && revised[pos].empty()) --pos;
if (pos == 0) break;
if (!initial[pos].empty() && !revised[pos].empty())
{
int u = initial[pos].front(), v = revised[pos].front();
if (u < v) update(initial[pos], pos);
else update(revised[pos], pos);
}
else if (initial[pos].empty()) update(revised[pos], pos);
else if (revised[pos].empty()) update(initial[pos], pos);
}
int ret = 0;
for (int i = 1; i <= n; i++) ret = ret ^ (ans[i] + i);
printf("%d\n", ret);
}
return 0;
}