|
|
题目链接：http://poj.org/problem?id=2886
  /**//*
 题意：
有一排编号为1到N的小孩顺时针围成圈，没人手上有一张编号为A[i]的卡
片，游戏从第K个小孩开始，他告诉自己的卡片数字然后跳出圆圈，如果A[i]
大于0，那么左数第A[i]个小孩出圈否则右数第A[i]个出圈，游戏一直进行直到
所有孩子都出去位置，第p个出圈的将会得到F(p)的糖果，F(p)表示p的因子数
，问谁拿到了最多的糖果。
解法：
树状数组 + 数论
思路：
直接模拟整个过程的复杂度是O(n^2)，但是n非常大，所以必须优化，我们
发现模拟的时候瓶颈在于每次找到下一个小孩的时候需要遍历全部，所以如果把
这一步简化，问题就会简单许多，利用树状数组的成段求和就可以做到每次找下
一个小孩的复杂度降为log(n)，我们将每个孩子对应到树状数组的下标，如果当
前小孩存在那么就记为1，不存在记为0。这样，统计第x到第y个孩子中间有多少
个孩子就可以直接采用树状数组的sum(y) - sum(x-1)来完成，那么问题就转化成
了如何在第x到第y个孩子中间找到第k个尚存在的孩子，于是只要二分这个k，然
后利用成段求和来判可行。这样总的复杂度就可以降到O(nlognlogn)了。
还有一个常数优化，就是算每个孩子的因子数可以在筛选素数的时候一起做掉
，然后用一个数组保存1到n的因子最大值的id，这样就不用每次都重新算过了。而
且查找第k个孩子只要做到第id个就可以退出循环（原本是要做n次的）。
 */
#include <iostream>
using namespace std;
#define maxn 500010
int lowbit(int x)  {
return x & (-x);
}
int n;
int c[maxn];
void add(int pos, int v) {
  while(pos <= n) {
c[pos] += v;
pos += lowbit(pos);
 }
}
int sum(int pos) {
int s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
bool f[maxn];
int prime[maxn], ans[maxn], size;
int MaxAns[maxn], id[maxn];
struct Point {
string name;
int val;
}pt[maxn];
// 从x到y中找到第k个存在的元素
int Binary(int l, int r, int k) {
int ans;
if(l <= r) {
int pre = sum(l-1);
while(l <= r) {
int m = (l + r) >> 1;
if(sum(m) - pre >= k) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
swap(l, r);
int pre = sum(r);
while(l <= r) {
int m = (l + r) >> 1;
if(pre - sum(m-1) >= k) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
int main() {
int i, j;
for(i = 2; i < maxn; i++) {
if(!f[i]) {
prime[size++] = i;
ans[i] = 2;
for(j = i+i; j < maxn; j += i) {
int v = j;
if(!ans[j]) ans[j] = 1;
int x = 1;
while(v % i == 0) {
v /= i;
x ++;
}
ans[j] *= x;
f[j] = 1;
}
}
}
MaxAns[1] = 1;
id[1] = 1;
for(i = 2; i < maxn; i++) {
MaxAns[i] = MaxAns[i-1];
id[i] = id[i-1];
if(ans[i] > MaxAns[i]) {
MaxAns[i] = ans[i];
id[i] = i;
}
}
int k;
while(scanf("%d %d", &n, &k) != EOF) {
int pos = id[n];
for(i = 1; i <= n; i++) {
char str[20];
int v;
scanf("%s %d", str, &v);
pt[i].name = str;
pt[i].val = v;
}
if(MaxAns[pos] == 1) {
printf("%s 1\n", pt[k].name.c_str());
continue;
}
for(i = 1; i <= n; i++) {
c[i] = 0;
}
for(i = 1; i <= n; i++) {
add(i, 1);
}
int nowChild = k;
int nCount = 1;
add(k, -1);
while(nCount < pos) {
int A = pt[ nowChild ].val;
if(A > 0) {
A %= (n - nCount);
if(A == 0)
A = n - nCount;
int big = sum(n) - sum(nowChild);
if(A <= big) {
nowChild = Binary(nowChild+1, n, A);
}else {
A -= big;
nowChild = Binary(1, nowChild-1, A);
}
}else {
A = -A;
A %= (n - nCount);
if(A == 0) {
A = n - nCount;
}
int les = sum(nowChild - 1);
if(A <= les) {
nowChild = Binary(nowChild-1, 1, A);
}else {
A -= les;
nowChild = Binary(n, nowChild+1, A);
}
}
add(nowChild, -1);
nCount ++;
}
printf("%s %d\n", pt[nowChild].name.c_str(), MaxAns[pos]);
}
}
|