|
|
題目鏈接：http://poj.org/problem?id=2886
  /**//*
 題意：
有一排編號(hào)為1到N的小孩順時(shí)針圍成圈，沒人手上有一張編號(hào)為A[i]的卡
片，游戲從第K個(gè)小孩開始，他告訴自己的卡片數(shù)字然后跳出圓圈，如果A[i]
大于0，那么左數(shù)第A[i]個(gè)小孩出圈否則右數(shù)第A[i]個(gè)出圈，游戲一直進(jìn)行直到
所有孩子都出去位置，第p個(gè)出圈的將會(huì)得到F(p)的糖果，F(xiàn)(p)表示p的因子數(shù)
，問誰拿到了最多的糖果。
解法：
樹狀數(shù)組 + 數(shù)論
思路：
直接模擬整個(gè)過程的復(fù)雜度是O(n^2)，但是n非常大，所以必須優(yōu)化，我們
發(fā)現(xiàn)模擬的時(shí)候瓶頸在于每次找到下一個(gè)小孩的時(shí)候需要遍歷全部，所以如果把
這一步簡化，問題就會(huì)簡單許多，利用樹狀數(shù)組的成段求和就可以做到每次找下
一個(gè)小孩的復(fù)雜度降為log(n)，我們將每個(gè)孩子對應(yīng)到樹狀數(shù)組的下標(biāo)，如果當(dāng)
前小孩存在那么就記為1，不存在記為0。這樣，統(tǒng)計(jì)第x到第y個(gè)孩子中間有多少
個(gè)孩子就可以直接采用樹狀數(shù)組的sum(y) - sum(x-1)來完成，那么問題就轉(zhuǎn)化成
了如何在第x到第y個(gè)孩子中間找到第k個(gè)尚存在的孩子，于是只要二分這個(gè)k，然
后利用成段求和來判可行。這樣總的復(fù)雜度就可以降到O(nlognlogn)了。
還有一個(gè)常數(shù)優(yōu)化，就是算每個(gè)孩子的因子數(shù)可以在篩選素?cái)?shù)的時(shí)候一起做掉
，然后用一個(gè)數(shù)組保存1到n的因子最大值的id，這樣就不用每次都重新算過了。而
且查找第k個(gè)孩子只要做到第id個(gè)就可以退出循環(huán)（原本是要做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(tǒng)中找到第k個(gè)存在的元素
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]);
}
}
|