POJ 2886.Who Gets the Most Candies? -线段树(单点更新、类约瑟夫问题)
线段树可真有意思呢续集2。。。区间成段的替换和增减，以及区间求和等，其中夹杂着一些神奇的操作，数据离散化，简单hash，区间异或，还需要带着脑子来写题。
有的题目对数据的操作并不是直接按照题面意思进行操作，而是换一个角度，通过对其他数据的操作得到结果，感觉真的是。。。啊啊啊啊啊啊，我的脑子离家出走了，他在哪啊(ಥ_ಥ)ru
写到后面的题目就感觉满满的都是套路，只要想到怎样处理数据以及如果通过线段树维护数据就可以，但是就是这个是关键(废话。。。)，嘤嘤嘤，一拳一个嘤嘤怪，好好写题解。。。
POJ2886.Who Gets the Most Candies?
这个题可以偷懒一下，先找出n个数中第几个数的小孩能得到最多的糖果，for循环跑一遍找出来最大的h，很多人是用反素数写的因数个数，然而，并没有懂，直接跑一遍for就可以的吧。。。
然后只需要对线段树进行h次操作就可以了。因为每次操作的pos不确定，所以需要实时更新pos，取模的mod也是实时变化的，但是tree中存了这个值，所以直接每次操作完重新给mod赋值tree就可以。因为分向左还是向右，所以操作要注意。我就是这里出了问题。关于约瑟夫问题，具体的不介绍，自行百度吧。
这个题和插队的问题差不多，都需要带着脑子写，这些应该都是经典的线段树的题目吧。
好菜啊，为什么我这么菜。。。
代码:
1 //F
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<cmath>
6 #include<algorithm>
7 #include<cstdlib>
8 #include<queue>
9 #include<stack>
10 using namespace std;
11 typedef long long ll;
12 const int inf=0x3f3f3f3f;
13 const double eps=1e-5;
14 const int maxn=5*1e5+10;
15 #define lson l,m,rt<<1
16 #define rson m+1,r,rt<<1|1
17 struct node{
18 char na;
19 int num;
20 }a;
21 int tree,ans;
22 int n,time;
23 void init()
24 {
25 memset(ans,0,sizeof(ans));
26 int cnt=(int)sqrt(n*1.0);
27 for(int i=1;i<=cnt;i++)
28 {
29 for(int j=i+1;j*i<=n;j++)
30 ans+=2;
31 ans++;
32 }
33 int maxx=ans;
34 time=1;
35 for(int i=2;i<=n;i++)
36 {
37 if(ans>maxx)
38 {
39 maxx=ans;
40 time=i;
41 }
42 }
43 }
44 void build(int l,int r,int rt)
45 {
46 tree=r-l+1;
47 if(l==r){
48 return ;
49 }
50
51 int m=(l+r)>>1;
52 build(lson);
53 build(rson);
54 }
55 int update(int pos,int l,int r,int rt)
56 {
57 tree--;
58 if(l==r){
59 return l;
60 }
61
62 int m=(l+r)>>1;
63 if(pos<=tree) return update(pos,lson);
64 else return update(pos-tree,rson);
65 }
66 int main()
67 {
68 int k,mod;
69 while(~scanf("%d%d",&n,&k))
70 {
71 init();
72 for(int i=1;i<=n;i++)
73 scanf("%s%d",&a.na,&a.num);
74 build(1,n,1);
75 int pos=0;a.num=0;
76 mod=tree;
77 int h=time;
78 while(h--)
79 {
80 if(a.num>0)
81 k=((k-1+a.num-1)%mod+mod)%mod+1;
82 else
83 k=((k-1+a.num)%mod+mod)%mod+1;
84 pos =update(k,1,n,1);
85 mod=tree;
86 }
87 printf("%s %d\n",a.na,ans);
88 }
89 return 0;
90 }
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3167913
页:
[1]