题意 给你一个n和一个k,表示有n个人,从k先开始,被叫到的人出圈,之后出圈的那个人,手里有一个数字a[i],如果是正数就表示的是顺时针走a[i]步是下一个出圈的人,如果是负数就逆时针走a[i]步是下一个出圈的人,每个人出圈都会得到一定的糖果,糖果的数量是假如你是第k次出圈的,那么你将会得到k的因子个数的糖果,现在问你谁得到了最多的糖果。 思路 我们可以轻易的求出第几次出来会得到最多的糖果,那么我们就直接模拟第几次出来就好了,关于如何模,由于他每次走的步数都在 108 10 8 ,所以我们on的去模拟肯定是会超时的,那么具体我们怎么作呢?我们可以用线段树把他降到log,我们线段树的节点维护的是你所管辖的区间中现在还有几个数,每次update的时候就让所管辖的区间–,首先我们可以求出来每一轮需要走的步数,之后每次查询的时候就看当前节点的左子树所管辖的区间,够不够我现在所要求的步数,如果够了话就说明我要求的数字肯定在当前节点的左子树,如果不够的话那么我们就可以让我们所求的数减去左子树的区间,之后去右子树上查。 代码
#include <iostream> #include <string.h> #include <stdio.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int maxn = 500000+10; char ch[maxn][20]; int a[maxn]; int D[maxn]; void init() { for(int i = 1 ; i <= maxn ;i ++) { ++D[i]; for(int j = 2 * i ; j <= maxn ; j += i) { ++D[j]; } } } struct Segtree { int seg[maxn<<2]; void build(int l, int r,int rt) { seg[rt] = r - l + 1; if(l == r) return ; int m = (l+r)>>1; build(lson); build(rson); } int query(int k , int l,int r,int rt) { --seg[rt]; if(l == r) return l; int m = (l+r)>>1; if(seg[rt<<1] >= k) { return query(k,lson); } else { return query(k-seg[rt<<1],rson); } } }tree; int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { tree.build(1,n,1); init(); int MAX = -1; int pos; for(int i = 1 ; i <= n ; i++) { scanf("%s %d",&ch[i],&a[i]); if(D[i] > MAX) { pos = i; MAX = D[i]; } } int T = pos; int mod = tree.seg[1]; pos = 0; a[0] = 0; while(T--) { //求出我们需要走的步数 if (a[pos] > 0) k = ((k - 1 + a[pos] - 1) % mod + mod) % mod + 1; else k = ((k + a[pos] - 1) % mod + mod) % mod + 1;//card[i] cout<<k<<" "<<pos<<endl; pos = tree.query(k,1,n,1); mod--; } printf("%s %d\n",ch[pos],MAX); } } /* 7 2 a -7 b 12 c -2 d 6 e 0 f 1 g 7 */