who gets the most candies[pku 2886].cpp

PKU 上的几个题目 Tunnel Warfare Unique Solution Washing Clothes Weather Forecast Who Gets the Most Ca

// PKU 2886
// use segmental tree, delete and find position in O(LogN) time
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;

#define foreach(it,c) for (it=(c).begin(); it!=(c).end(); it++)

const int NMAX = 500000 +100;
const int PMAX = 100;
int n, k;
struct NODE
{
	char name[12];
	int card;
};
NODE child[NMAX];

bitset <PMAX> bp;
VI np;
struct FPNUM
{
	int num;
	int fp;
	int pos;
	vector <int> fac;
	vector <int> seq;

	FPNUM(int _n = 0, int _f = 0, int _p = 0)
		: num(_n), fp(_f), pos(_p) {}
	bool operator < (const FPNUM & ft) const
	{
		if (num == ft.num)
			return fp > ft.fp;
		return num > ft.num;
	}
};
int fpnum[100], fp[100], fptotal;

void pre_cal()
{
	int i, j;

	int rt = sqrt(1.0*PMAX);
	np.push_back(2);
	for (i=3; i<rt; i+=2)
		if (! bp[i])
		{
			np.push_back(i);
			for (j=i*i; j<PMAX; j+=i)
				bp[j] = 1;
		}
	for (; i<PMAX; i++)
		if (! bp[i])
			np.push_back(i);
	
	fpnum[0] = 1;
	fp[0] = 1;
	fptotal = 1;

	FPNUM s(2,2,0);
	s.fac.push_back(2);
	s.seq.push_back(1);
	
	priority_queue <FPNUM> pq;
	pq.push(s);

	while (! pq.empty())
	{
		s = pq.top();
		pq.pop();

		if (s.fp <= fp[fptotal-1])
			continue;

		fpnum[fptotal] = s.num;
		fp[fptotal] = s.fp;
		fptotal ++;

		if (s.num >= NMAX)
			break;

		for (i=0; i<=s.pos+1; i++)
		{
			FPNUM next = s;
			next.num = s.num * np[i];
			if (i <= s.pos)
			{
				next.seq[i] ++;
				next.fp = next.fp / next.seq[i] * (next.seq[i]+1);
			}
			else
			{
				next.fp *= 2;
				next.fac.push_back(np[i]);
				next.seq.push_back(1);
				next.pos = i;
			}
			pq.push(next);
		}
	}

}

int tree[1<<20];

void update(int root, int l, int r, int pos, int flag)
{
	tree[root] += flag;
	if (l == r)
		return;

	int mid = (l+r) >> 1;
	if (pos <= mid)
		update(root<<1, l, mid, pos, flag);
	else
		update((root<<1)+1, mid+1, r, pos, flag);
}

int find(int root, int l, int r, int flag)
{
	if (l == r)
	{
		if (flag == 1)
			return l;
		return -1;
	}

	int mid = (l+r) >> 1;
	int lpos = root << 1;
	int lres = (mid-l+1) - tree[lpos];

	if (lres >= flag)
		return find(lpos, l, mid, flag);
	else
		return find(lpos+1, mid+1, r, flag-lres);
}

int sum(int root, int l, int r, int ql, int qr)
{
	if (ql<=l && r<=qr)
		return r-l+1-tree[root];

	int ret = 0;
	int mid = (l+r) >> 1;
	if (ql <= mid)
		ret += sum(root<<1, l, mid, ql, qr);
	if (mid < qr)
		ret += sum((root<<1)+1, mid+1, r, ql, qr);
	return ret;
}

void solve()
{
	int i, j, res;

	int maxfppos = lower_bound(fpnum, fpnum+fptotal, n) - fpnum;
	if (fpnum[maxfppos] != n)
		maxfppos --;

	int minp = fpnum[maxfppos];
	int maxfp = fp[maxfppos];
	int who;

	memset(tree, 0, sizeof(tree));
	k --;
	who = k;
	k = child[who].card;
	child[who].card = 0;
	update(1, 0, n-1, who, 1);

	for (i=1,res=n-1; i<minp; i++,res--)
	{
		int who2 = sum(1, 0, n-1, 0, who);
		if (k > 0)
			who2 --;
		k = ((who2+k)%res + res) % res;

		who = find(1, 0, n-1, k+1);
		update(1, 0, n-1, who, 1);

		k = child[who].card;
		child[who].card = 0;
	}

	printf("%s %d\n", child[who].name, maxfp);
}

int main()
{
	int i, j;
	
	pre_cal();

	while ( scanf("%d %d", &n, &k) == 2)
	{
		for (i=0; i<n; i++)
			scanf("%s %d", child[i].name, &child[i].card);
		solve();
	}
}