|
题目链接:http://poj.org/problem?id=2886
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
有一排编号为1到N的小孩顺时针围成圈,没人手上有一张编号为A[i]的卡
片,游戏从第K个小孩开始,他告诉自己的卡片数字然后跳出圆圈,如果A[i]
大于0,那么左数第A[i]个小孩出圈否则右数第A[i]个出圈,游戏一直进行直到
所有孩子都出去位置,第p个出圈的将会得到F(p)的糖果,F(p)表示p的因子数
,问谁拿到了最多的糖果。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
树状数组 + 数论
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
直接模拟整个过程的复杂度是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次的)。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 500010
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int x) {
return x & (-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
int c[maxn];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void add(int pos, int v) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos <= n) {
c[pos] += v;
pos += lowbit(pos);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int sum(int pos) {
int s = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool f[maxn];
int prime[maxn], ans[maxn], size;
int MaxAns[maxn], id[maxn];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct Point {
string name;
int val;
}pt[maxn];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 从x到y中找到第k个存在的元素
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Binary(int l, int r, int k) {
int ans;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l <= r) {
int pre = sum(l-1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l <= r) {
int m = (l + r) >> 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(sum(m) - pre >= k) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
swap(l, r);
int pre = sum(r);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l <= r) {
int m = (l + r) >> 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(pre - sum(m-1) >= k) {
l = m + 1;
ans = m;
}else
r = m - 1;
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 2; i < maxn; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(!f[i]) {
prime[size++] = i;
ans[i] = 2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(j = i+i; j < maxn; j += i) {
int v = j;
if(!ans[j]) ans[j] = 1;
int x = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(v % i == 0) {
v /= i;
x ++;
}
ans[j] *= x;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f[j] = 1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
MaxAns[1] = 1;
id[1] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 2; i < maxn; i++) {
MaxAns[i] = MaxAns[i-1];
id[i] = id[i-1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(ans[i] > MaxAns[i]) {
MaxAns[i] = ans[i];
id[i] = i;
}
}
int k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d %d", &n, &k) != EOF) {
int pos = id[n];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
char str[20];
int v;
scanf("%s %d", str, &v);
pt[i].name = str;
pt[i].val = v;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(MaxAns[pos] == 1) {
printf("%s 1\n", pt[k].name.c_str());
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
c[i] = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
add(i, 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int nowChild = k;
int nCount = 1;
add(k, -1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(nCount < pos) {
int A = pt[ nowChild ].val;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(A > 0) {
A %= (n - nCount);
if(A == 0)
A = n - nCount;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int big = sum(n) - sum(nowChild);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(A <= big) {
nowChild = Binary(nowChild+1, n, A);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
A -= big;
nowChild = Binary(1, nowChild-1, A);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
A = -A;
A %= (n - nCount);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(A == 0) {
A = n - nCount;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int les = sum(nowChild - 1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(A <= les) {
nowChild = Binary(nowChild-1, 1, A);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
A -= les;
nowChild = Binary(n, nowChild+1, A);
}
}
add(nowChild, -1);
nCount ++;
}
printf("%s %d\n", pt[nowChild].name.c_str(), MaxAns[pos]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|