POJ 2886 Who Gets the Most Candies? 题解 《挑战程序设计竞赛》

POJ 2886 Who Gets the Most Candies?

抢糖：N个熊孩子围成一个圈，从第K个开始淘汰，每淘汰一个，出示手中的数字，决定下一个淘汰者，正数表示左手第n个，负数反之。每个人可以拿到的存活回数的因数个数的糖果，求拿到最多糖果数的孩子的名字以及糖果数。

3.3活用各种数据结构

Binary Indexed Tree

这群熊孩子简直逆天了，你数学这么好，你麻麻知道吗？

第一步需要做一份因式分解表，table[i]=x表示i有x个因数。怎么求一个数有多少个约数呢？先将x分解为质因数之积，比如270 = 3 * 3 * 3 * 2 * 5，那么分别从所有{质因数的n次方}中分别挑一个出来累乘就可以得出一个唯一的因数。

比如{1, 3, 9, 27} * {1, 2} * {1, 5}，这三个集合中每个集合挑一个数出来做乘法，一共有4 * 2 * 2 = 16种，于是因数有16个。

然后需要在剔除人之后还能快速将一个人的当前的次序与最初的次序联系起来，朴素的做法每淘汰一个人就更新前面的每个人的次序是非常耗时的，这种区域修改可以活用BIT高效完成。

BIT用来维护初始下标，BIT将一个人当前的次序与最初的次序关联起来，具体来说：

用BIT的sum(x)的值表示目前剩下的第几人（x表示初始下标，当然随着逐渐淘汰，有些x代入sum(x)没有实际的意义），每淘汰一个人（初始id=x），就add(x, -1)。如何快速知道第sum的家伙以前的下标是多少呢？可以用二分，因为前缀和必定是单调递增的。

举个例子说明问题，假设有6人参加，BIT的前缀和初始为

123456

后来淘汰了下标为2的人，BIT的前缀和变为

112345

对应人的编号为

13456

这时我们想知道剩下的人中第3个人的初始下标（13456的第3个数是4），我们从前缀和里面找，发现sum(4)=3，那么第3个人的初始下标就是4。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_N 500000
int factor_table[MAX_N + 16];
char name[MAX_N + 16][16];
int  integer[MAX_N + 16];

void init_factor_table(int n)
{
	fill(factor_table, factor_table + n + 1, 1);
	for (int i = 2; i <= n; ++i)
	{
		if (factor_table[i] == 1)
		{
			for (int j = i; j <= n; j += i)
			{
				int k = 0;
				for (int m = j; m % i == 0; m /= i, ++k);
				factor_table[j] *= k + 1;
			}
		}
	}
}

template <class T>
class BinaryIndexedTree
{
public:
	T bit[MAX_N];
	int size;

	BinaryIndexedTree(){}

	void init(int size)
	{
		this->size = size;
		memset(bit, 0, sizeof(bit));
	}

	T sum(int i)
	{
		int s = 0;
		while (i > 0)
		{
			s += bit[i];
			i -= (i & -i);
		}
		return s;
	}

	void add(int i, T v)
	{
		++i;	// 防止如果i是0的话，下面的循环永远不会终止
		while (i <= MAX_N)
		{
			bit[i] += v;
			i += (i & -i);
		}
	}

	// 二分搜索真实下标
	T binary_search(int id)
	{
		int lb = 0, ub = size;
		while (ub - lb > 1)
		{
			int mid = (ub + lb) >> 1;
			if (sum(mid) <= id)
			{
				lb = mid;
			}
			else
			{
				ub = mid;
			}
		}
		return lb;
	}
};

BinaryIndexedTree<int> bit;	// bit.binary_seach(x)表示当前排序为x的人的初始下标

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, K;

	init_factor_table(MAX_N + 16);
	while (cin >> N >> K)
	{
		--K;
		bit.init(N);

		for (int i = 0; i < N; ++i)
		{
			scanf("%s %d", name[i], &integer[i]);
			bit.add(i, 1);
		}

		int candies = -1, index;
		for (int i = 0; i < N; ++i)
		{
			if (candies < factor_table[i + 1])
			{
				candies = factor_table[i + 1];
				index = K;
			}
			bit.add(K, -1);
			if (i < N - 1)
			{
				int mod = N - i - 1;	// 当前人数
				int id = bit.sum(K) + integer[K] + (integer[K] > 0 ? -1 : 0);	// 下标从0开始
				id = (id % mod + mod) % mod;
				K = bit.binary_search(id);	// K表示下一个站出来的孩子的初始index
			}
		}

		printf("%s %d\n", name[index], candies);
	}

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

Reference：http://even-eko.hatenablog.com/entry/2013/10/08/163126

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2886 Who Gets the Most Candies? 题解 《挑战程序设计竞赛》