首页 > 代码库 > POJ 2886 Who Gets the Most Candies?
POJ 2886 Who Gets the Most Candies?
题目大意是:n个人围成一圈 ,每个人有一个非零数num,为正表示在他出去以后他左边第num 个人出去,否则右边第-num个人出去,给定最开始出去的人,求第m个出去的人,其中,1<=m<=n, m的约数个数在1..n中是最多的 输出这个人的名字和m的约数个数
分两步:
(1)首先求m,可以预处理求出1到maxn的所有数的约数个数,并求出数组f[p],当n==p时,f[p]表示约数个数最多的那个数;这样对每一个n,O(1)得到m;
(2)求出m以后,就是模拟了,模拟前m次出队过程,问题的关键就是如何确定下一个要出去的人。线段树是显然符合要求的,保存当前区间内实际存在的人数,然后就是简单的单点更新了,更新和查询都是logn级别的
被坑出翔的地方:题目给的数据是顺时针给的,也就是从右到左,而线段树是从左到右的,所以题目给定的方向也必须反过来,下面是代码:
1 /********************************************** 2 *** Problem: 3 *** Author: JKL 4 *** University: CSUST 5 *** Team: __Dream 6 *** Email: 1451108308@QQ.COM 7 *** My Blog: http://www.cnblogs.com/jklongint/ 8 ***********************************************/ 9 //=================================================== 10 #include <iostream> 11 #include <fstream> 12 #include <sstream> 13 #include <iomanip> 14 #include <cstdio> 15 #include <cstdlib> 16 #include <cmath> 17 #include <cassert> 18 #include <numeric> 19 #include <ctime> 20 #include <algorithm> 21 #include <cstring> 22 #include <string> 23 #include <vector> 24 #include <queue> 25 #include <map> 26 #include <stack> 27 #include <list> 28 #include <set> 29 #include <bitset> 30 #include <deque> 31 using namespace std; 32 //--------------------------------------------------- 33 #define mem(a,b) memset(a,b,sizeof(a)) 34 #define GO cout<<"HelloWorld!"<<endl 35 #define Case(x) cout<<"Case "<<x<<":" 36 #define foru(i,n) for(int i=1; i <= n; i++) 37 #define ford(i,n) for(int i = n; i >= 1; i--) 38 #define fin freopen("input.txt","r",stdin); 39 #define fout freopen("output.txt","w",stdout) 40 #define lson l, m, rt << 1 41 #define rson m + 1, r, rt << 1 | 1 42 43 #define sqr(a) ((a)*(a)) 44 #define abs(a) ((a>0)?(a):-(a)) 45 #define pii pair<int,int> 46 47 #define fmax(a,b) max(a,b) 48 #define fmin(a,b) min(a,b) 49 #define fmax3(a,b,c) (fmax(a,fmax(a,b))) 50 #define fmin3(a,b,c) (fmin(a,fmin(a,b))) 51 52 #define sfi(x) scanf("%d",&x) 53 #define sfL(x) scanf("%I64d",&x) 54 #define sfc(x) scanf("%c",&x) 55 #define sfd(x) scanf("%lf",&x) 56 #define sfs(x) scanf("%s",x) 57 #define sfii(a,b) scanf("%d%d",&a,&b) 58 #define sfLL(a,b) scanf("%I64d%I64d",&a,&b) 59 #define sfcc(a,b) scanf("%c%c",&a,&b) 60 #define sfdd(a,b) scanf("%lf%lf",&a,&b) 61 #define sfss(a,b) scanf("%s%s",a,b) 62 63 #define pfi(x) printf("%d",x) 64 #define pfL(x) printf("%I64d",x) 65 #define pfs(x) printf("%s",x) 66 #define pfd(x) printf("%lf",x) 67 #define pfc(x) print("%c",x) 68 #define newLine pfs("\n") 69 #define space pfs(" ") 70 71 //-------------------------------------------------------- 72 typedef long long LL; 73 typedef unsigned long long ULL; 74 typedef __int64 __LL; 75 typedef unsigned __int64 __ULL; 76 77 typedef vector<int> vi; 78 typedef vector<LL> vL; 79 typedef vector<string> vs; 80 typedef set<int> si; 81 typedef map<int,int> mii; 82 typedef map<LL,LL> mLL; 83 typedef map<string,int> msi; 84 typedef map<char,int> mci; 85 //-------------------------------------------------------- 86 const int dx[4]={1,-1,0,0}; 87 const int dy[4]={0,0,1,-1}; 88 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 89 const int N6=1000006; 90 const int N5=100006; 91 const int N4=10006; 92 const int N3=1006; 93 const int N2=106; 94 const int N=510009; 95 const int MOD=1000000007; 96 const LL LMAX=0x7fffffffffffffff; 97 const LL IMAX=0x3fffffff; 98 const double PI=3.14159265359; 99 //--------------------------------------------------------100 template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }101 template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }102 103 //------------------------------------------------------------104 struct TreeNode{105 int cnt;106 };107 //=================================================================108 TreeNode tree[N << 2];109 int n, k, a[N],cnt[N + 2], ans, max0[N + 2], cc[N + 2];110 char s[N][15];111 void init()112 {113 for(int i = 1; i <= N; i++){114 for(int j = 1; j * i <= N ; j++)115 cnt[j * i]++;116 }117 foru(i, N){118 if(max0[i-1] < cnt[i]){119 max0[i] = cnt[i];120 cc[i] = i;121 }122 else{123 max0[i] = max0[i - 1];124 cc[i] = cc[i - 1];125 }126 }127 }128 void PushUP(int rt)129 {130 tree[rt].cnt = tree[rt << 1].cnt + tree[rt << 1 | 1].cnt;131 }132 void build(int l, int r, int rt)133 {134 if(l == r){135 tree[rt].cnt = 1;136 return;137 }138 int m = (l + r) >> 1;139 build(lson);140 build(rson);141 PushUP(rt);142 }143 int query(int p, int l, int r, int rt)144 {145 if(l == r){146 tree[rt].cnt = 0;147 return l;148 }149 int m = (l + r) >> 1, cnt = tree[rt << 1].cnt, tmp;150 if(p <= cnt) tmp = query(p, lson);151 else tmp = query(p - cnt, rson);152 PushUP(rt);153 return tmp;154 }155 int getNext(int pos, int cnt)156 {157 int total = tree[1].cnt, mark;158 if(total == 0) return 0;159 mark = cnt > 0 ? 1 : -1;160 if(cnt > 0)cnt %= total;else cnt = -((-cnt) % total);161 if(mark > 0)return (pos - cnt + total -1) % total + 1;162 else return (pos -cnt -2) % total + 1;163 }164 int main()165 {166 //fin;fout;167 init();168 while( ~ sfii(n, k)){169 build(1, n, 1);170 foru(i, n)sfs(s[i]), sfi(a[i]);171 int pos = k, c = cc[n], out;172 foru(i, c){173 out = query(pos, 1, n, 1);174 pos = getNext(pos, -a[out]);175 }176 pfs(s[out]);space;pfi(cnt[c]);newLine;177 }178 return 0;179 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。