题目链接:poj 2886 Who Gets the Most Candies?
题目大意:N个人围成一圈玩约瑟夫环游戏,不同的是,步长不固定,由前一个出局的人决定,给定K表示起始的人。第i个淘汰的人将获得g(i)个糖果,问说谁获得的糖果最多。g(x)为x的因子个数。
解题思路:起始g(x)是成阶段的,所以打表处理处g(x)递增值,对于每个N,一开始找到小于等于N的最大x,那么第x个淘汰的人即为获得糖果数最多的家伙。剩下的就用线段树模拟游戏过程。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
struct Node {
int l, r, s;
void set (int l, int r, int s) {
this->l = l;
this->r = r;
this->s = s;
}
}nd[maxn * 4];
const int antipri[36] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500001};
const int fact[36] = {1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200};
int N, B, v[maxn];
char name[maxn][20];
void build (int u, int l, int r) {
nd[u].set(l, r, r - l + 1);
if (l == r)
return ;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
}
int query(int u, int x) {
nd[u].s--;
if (nd[u].l == nd[u].r)
return nd[u].l;
if (nd[lson(u)].s >= x)
return query(lson(u), x);
else
return query(rson(u), x - nd[lson(u)].s);
}
int bsearch (int x) {
int l = 0, r = 35;
for (int i = 0; i < 20; i++) {
int mid = (l + r) / 2;
if (antipri[mid] > x)
r = mid;
else
l = mid;
}
return l;
}
int main () {
while (scanf("%d%d", &N, &B) == 2) {
for (int i = 1; i <= N; i++)
scanf("%s%d", name[i], &v[i]);
build(1, 1, N);
v[0] = 0;
int E = bsearch(N), k = 0;
for (int i = N; i; i--) {
B = ((B + v[k] - (v[k] > 0 ? 2 : 1)) % i + i) % i + 1;
k = query(1, B);
if (N - i + 1 == antipri[E]) {
printf("%s %d\n", name[k], fact[E]);
break;
}
}
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
北大POJ2388-Who's in the Middle 解题报告+AC代码
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
线段树、树状数组算法入门 加 poj解题报告 pdf文档
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
poj 1611 The Suspects 代码 并查集的应用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类