第十二周 11.15-11.21

news/2024/7/6 21:31:00

11.15

补个BC。

HDU 5565 Clarke and baton

没太懂题解怎么搞。反正挺暴力过了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef long long LL;
 8 const int maxn=1e7+10;
 9 
10 bool cmp(int a,int b)
11 {
12     return a>b;
13 }
14 
15 LL seed;
16 int a[maxn];
17 int rand(int l, int r) {
18     static long long mo=1e9+7, g=78125;
19     return l+((seed*=g)%=mo)%(r-l+1);
20 }
21 
22 int main(void)
23 {
24     int T;scanf("%d",&T);
25     while(T--)
26     {
27         int n,q;
28         scanf("%d%d%I64d",&n,&q,&seed);
29         int sum=rand(q, 10000000);
30         for(int i=1; i<=n; i++) {
31             a[i]=rand(0, sum/(n-i+1));
32             sum-=a[i];
33         }
34         a[rand(1, n)]+=sum;
35         map< int,vector<int> > M;
36         for(int i=1;i<=n;i++) M[a[i]].push_back(i);
37         map< int,vector<int> >::iterator it=M.end();
38         while(1)
39         {
40             it--;
41             vector<int> & t=(*it).second;
42             sort(t.begin(),t.end(),cmp);
43             for(int i=t.size()-1;i>=0;i--)
44             {
45                 if(q==0) break; q--;
46                 int x=(*it).first,y=t[i];
47                 M[x-1].push_back(y);
48                 M[x].pop_back();
49             }
50             if(q==0||it==M.begin()) break;
51         }
52         int ans=0;
53         for(it=M.begin();it!=M.end();it++)
54         {
55             vector<int> & t=(*it).second;
56             for(int i=t.size()-1;i>=0;i--) ans^=(*it).first+t[i];
57         }
58         printf("%d\n",ans);
59     }
60     return 0;
61 }