首页 > 其他 > 详细

codeforces edu76 做题记录

时间:2019-11-22 00:57:05      阅读:108      评论:0      收藏:0      [点我收藏+]

A.

随便判一下,注意边界

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int T;
 5 int n,x,a,b;
 6 int main()
 7 {
 8     cin>>T;
 9     while(T--)
10     {
11         cin>>n>>x>>a>>b;
12         if(a>b)swap(a,b);
13         int ans=b-a;
14         ans+=min(a-1,x),x-=min(a-1,x);
15         ans+=min(n-b,x),x-=min(n-b,x);
16         cout<<ans<<endl; 
17     }
18 }
View Code

B.

考虑单组最多\(\log\)步,暴力跳就完事了

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int T;
 5 ll x,y;
 6 map<ll,bool> vis;
 7 int main()
 8 {
 9     scanf("%d",&T);
10     while(T--)
11     {
12         vis.clear();
13         scanf("%I64d%I64d",&x,&y);
14         while(!vis[x])
15         {
16             if(x>=y)break;
17             vis[x]=1;
18             if(x&1)x--;
19             x=x*3/2;
20         }
21         if(x>=y)puts("YES");
22         else puts("NO");
23     }
24 }
View Code

C.

最短的答案一定存在于两个相同的数字中间夹着一堆数的情况

显然中间如果有两个相同的数那一定更优

我们对每个数记录一下出现位置扫一遍就行了

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define maxn 200005
 3 using namespace std;
 4 int T,n;
 5 int a[maxn];
 6 vector<int> v[maxn];
 7 int main()
 8 {
 9     scanf("%d",&T);
10     while(T--)
11     {
12         scanf("%d",&n);
13         for(int i=1;i<=n;++i)v[i].clear();
14         for(int i=1;i<=n;++i)scanf("%d",&a[i]),v[a[i]].push_back(i);
15         int ans=n+1;
16         for(int i=1;i<=n;++i)
17         {
18             for(int j=1;j<v[i].size();++j)ans=min(ans,v[i][j]-v[i][j-1]+1);
19         }
20         if(ans==n+1)ans=-1;
21         printf("%d\n",ans);
22     }
23 }
View Code

D.

对每天能打的怪二分一下长度

然后check就变成了一个区间最值查询

ST表

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define maxn 200005
 3 using namespace std;
 4 int T,n,m;
 5 int st[maxn][20],maxhp[maxn];
 6 struct node
 7 {
 8     int atk,hp;
 9 }a[maxn];
10 int b[maxn]; 
11 bool operator < (node A,node B){return A.atk<B.atk;}
12 void init()
13 {
14     for(int j=1;j<=19;++j)
15         for(int i=1;i+(1<<j)-1<=n;++i)st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
16 }
17 int getmax(int l,int r)
18 {
19     int k=log2(r-l+1);
20     return max(st[l][k],st[r-(1<<k)+1][k]);
21 }
22 int main()
23 {
24     scanf("%d",&T);
25     while(T--)
26     {
27         scanf("%d",&n);
28         for(int i=1;i<=n;++i)scanf("%d",&st[i][0]);
29         init();
30         scanf("%d",&m);
31         for(int i=1;i<=m;++i)scanf("%d%d",&a[i].atk,&a[i].hp);
32         sort(a+1,a+m+1);
33         for(int i=1;i<=m;++i)b[i]=a[i].atk;
34         maxhp[m+1]=0; 
35         for(int i=m;i>=1;--i)maxhp[i]=max(maxhp[i+1],a[i].hp);
36         int pos=0,ans=0;
37         while(pos<n)
38         {
39             int l=pos+1,r=n,res=pos;
40             while(l<=r)
41             {
42                 int mid=(l+r)>>1;
43                 int maxv=getmax(pos+1,mid),len=mid-pos;
44                 int x=lower_bound(b+1,b+m+1,maxv)-b;
45                 if(maxhp[x]>=len)res=mid,l=mid+1;
46                 else r=mid-1;
47             }
48             if(res==pos){ans=-1;break;}
49             ans++;pos=res;
50         }
51         printf("%d\n",ans);
52     }
53 }
View Code

E.

\(dp[i][0/1/2]\)表示第\(i\)个位置在哪一段

直接转移一下就完事了

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define maxn 200005
 3 using namespace std;
 4 int k1,k2,k3,n;
 5 int dp[maxn][3],bel[maxn];
 6 int main()
 7 {
 8     scanf("%d%d%d",&k1,&k2,&k3);
 9     for(int x,i=1;i<=k1;++i)
10     {
11         scanf("%d",&x);
12         bel[x]=0; 
13     } 
14     for(int x,i=1;i<=k2;++i)
15     {
16         scanf("%d",&x);
17         bel[x]=1; 
18     } 
19     for(int x,i=1;i<=k3;++i)
20     {
21         scanf("%d",&x);
22         bel[x]=2; 
23     } 
24     n=k1+k2+k3;
25     memset(dp,127/2,sizeof(dp));
26     dp[0][0]=0;
27     for(int i=0;i<n;++i)
28     {
29         for(int j=0;j<3;++j)
30         {
31             for(int k=j;k<3;++k)
32             {
33                 dp[i+1][k]=min(dp[i+1][k],dp[i][j]+((bel[i+1]==k)?0:1));
34             }
35         }
36     }
37     cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<endl;
38 }
View Code

F.

考虑折半

把\(30\)位拆成\(15\)和\(15\)

枚举x的后\(15\)位,然后计算出一个表示\(1\)个数的vector塞进map里

然后枚举x的前\(15\)位,在map里统计一下

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define maxn 105
 3 using namespace std;
 4 int n;
 5 int a[maxn],b[maxn];
 6 map< vector<int>,int > mp;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;++i)
11     {
12         scanf("%d",&a[i]);
13         b[i]=a[i]&32767;
14         a[i]>>=15;
15     }
16     for(int S=0;S<32768;++S)
17     {
18         vector<int> A;
19         A.clear();
20         for(int i=1;i<=n;++i)A.push_back(__builtin_popcount(S^a[i]));
21         if(!mp.count(A))mp[A]=S;
22     }
23     for(int S=0;S<32768;++S)
24     {
25         vector<int> B;
26         B.clear();
27         for(int i=1;i<=n;++i)B.push_back(-(__builtin_popcount(S^b[i])));
28         for(int j=0;j<=30;++j)
29         {
30             for(int i=0;i<n;++i)B[i]++;
31             if(mp.count(B))
32             {
33                 int x=S|(mp[B]<<15);
34                 cout<<x<<endl;
35                 return 0;
36             }
37         }
38     }
39     puts("-1");
40 }
View Code

G.

如果不是多重集的话,那么\(n\)个数形成的集合里选最多的一些集合互不包含就是选\(\frac{n}{2}\)个

现在变成多重集,该结论仍然成立,还是选\(\frac{n}{2}\)个

但是多重集没法直接用组合数计算

那么我们考虑生成函数

对于每种东西来说,\(F(x)=(1+x+x^2+\cdots+x^m)\)

那么所有物品就是一堆这样的生成函数卷起来,然后取\([x^{\frac{n}{2}}] f(x)\)

分治FFT

技术分享图片
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int mod = 998244353;
  4 #define ll long long
  5 const double PI=acos(-1.0);
  6 const int maxn=800005;
  7 namespace fft
  8 {
  9     struct num{
 10         double x,y;
 11         num() {x=y=0;}
 12         num(double x,double y):x(x),y(y){}
 13     };
 14     inline num operator+(num a,num b) {return num(a.x+b.x,a.y+b.y);}
 15     inline num operator-(num a,num b) {return num(a.x-b.x,a.y-b.y);}
 16     inline num operator*(num a,num b) {return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
 17     inline num conj(num a) {return num(a.x,-a.y);}
 18     int base=1;
 19     vector<num> roots={{0,0},{1,0}};
 20     vector<int> rev={0,1};
 21     const double PI=acosl(-1.0);
 22     void ensure_base(int nbase){
 23         if(nbase<=base) return;
 24         rev.resize(1<<nbase);
 25         for(int i=0;i<(1<<nbase);i++)
 26             rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));
 27         roots.resize(1<<nbase);
 28         while(base<nbase){
 29             double angle=2*PI/(1<<(base+1));
 30             for(int i=1<<(base-1);i<(1<<base);i++){
 31                 roots[i<<1]=roots[i];
 32                 double angle_i=angle*(2*i+1-(1<<base));
 33                 roots[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
 34             }
 35             base++;
 36         }
 37     }
 38     void fft(vector<num> &a,int n=-1){
 39         if(n==-1) n=a.size();
 40         assert((n&(n-1))==0);
 41         int zeros=__builtin_ctz(n);
 42         ensure_base(zeros);
 43         int shift=base-zeros;
 44         for(int i=0;i<n;i++)
 45             if(i<(rev[i]>>shift))
 46                 swap(a[i],a[rev[i]>>shift]);
 47         for(int k=1;k<n;k<<=1){
 48             for(int i=0;i<n;i+=2*k){
 49                 for(int j=0;j<k;j++){
 50                     num z=a[i+j+k]*roots[j+k];
 51                     a[i+j+k]=a[i+j]-z;
 52                     a[i+j]=a[i+j]+z;
 53                 }
 54             }
 55         }
 56     }
 57     vector<num> fa,fb;
 58     vector<ll> multiply(vector<int> &a, vector<int> &b){
 59         int need=a.size()+b.size()-1;
 60         int nbase=0;
 61         while((1<<nbase)<need) nbase++;
 62         ensure_base(nbase);
 63         int sz=1<<nbase;
 64         if(sz>(int)fa.size()) fa.resize(sz);
 65         for(int i=0;i<sz;i++){
 66             int x=(i<(int)a.size()?a[i]:0);
 67             int y=(i<(int)b.size()?b[i]:0);
 68             fa[i]=num(x,y);
 69         }
 70         fft(fa,sz);
 71         num r(0,-0.25/sz);
 72         for(int i=0;i<=(sz>>1);i++){
 73             int j=(sz-i)&(sz-1);
 74             num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
 75             if(i!=j) fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
 76             fa[i]=z;
 77         }
 78         fft(fa,sz);
 79         vector<ll> res(need);
 80         for(int i=0;i<need;i++) res[i]=fa[i].x+0.5;
 81         return res;
 82     }
 83     vector<int> multiply_mod(vector<int> &a,vector<int> &b,int m,int eq=0){
 84         int need=a.size()+b.size()-1;
 85         int nbase=0;
 86         while((1<<nbase)<need) nbase++;
 87         ensure_base(nbase);
 88         int sz=1<<nbase;
 89         if(sz>(int)fa.size()) fa.resize(sz);
 90         for(int i=0;i<(int)a.size();i++){
 91             int x=(a[i]%m+m)%m;
 92             fa[i]=num(x&((1<<15)-1),x>>15);
 93         }
 94         fill(fa.begin()+a.size(),fa.begin()+sz,num{0,0});
 95         fft(fa,sz);
 96         if(sz>(int)fb.size()) fb.resize(sz);
 97         if(eq) copy(fa.begin(),fa.begin()+sz,fb.begin());
 98         else{
 99             for(int i=0;i<(int)b.size();i++){
100                 int x=(b[i]%m+m)%m;
101                 fb[i]=num(x&((1<<15)-1),x>>15);
102             }
103             fill(fb.begin()+b.size(),fb.begin()+sz,num{0,0});
104             fft(fb,sz);
105         }
106         double ratio=0.25/sz;
107         num r2(0,-1),r3(ratio,0),r4(0,-ratio),r5(0,1);
108         for(int i=0;i<=(sz>>1);i++){
109             int j=(sz-i)&(sz-1);
110             num a1=(fa[i]+conj(fa[j]));
111             num a2=(fa[i]-conj(fa[j]))*r2;
112             num b1=(fb[i]+conj(fb[j]))*r3;
113             num b2=(fb[i]-conj(fb[j]))*r4;
114             if(i!=j){
115                 num c1=(fa[j]+conj(fa[i]));
116                 num c2=(fa[j]-conj(fa[i]))*r2;
117                 num d1=(fb[j]+conj(fb[i]))*r3;
118                 num d2=(fb[j]-conj(fb[i]))*r4;
119                 fa[i]=c1*d1+c2*d2*r5;
120                 fb[i]=c1*d2+c2*d1;
121             }
122             fa[j]=a1*b1+a2*b2*r5;
123             fb[j]=a1*b2+a2*b1;
124         }
125         fft(fa,sz);fft(fb,sz);
126         vector<int> res(need);
127         for(int i=0;i<need;i++){
128             ll aa=fa[i].x+0.5;
129             ll bb=fb[i].x+0.5;
130             ll cc=fa[i].y+0.5;
131             res[i]=(aa+((bb%m)<<15)+((cc%m)<<30))%m;
132         }
133         return res;
134     }
135     vector<int> square_mod(vector<int> &a,int m){
136         return multiply_mod(a,a,m,1);
137     }
138 };
139 int n;
140 struct node
141 {
142     int sz;
143     vector<int> x;
144 };
145 vector<int> A[3000005];
146 bool operator < (node A,node B)
147 {
148     return A.sz>B.sz;
149 } 
150 void solve()
151 {
152     priority_queue<node> pq;
153     for(int i=2;i<=3000000;++i)if(A[i].size()>1)
154     {
155         node u;
156         u.sz=A[i].size();
157         u.x=A[i];
158         pq.push(u);
159     }
160     while(!pq.empty())
161     {
162         vector<int> x=pq.top().x;
163         pq.pop();
164         if(pq.empty())
165         {
166             printf("%d\n",x[n/2]);
167             break;
168         }
169         vector<int> y=pq.top().x;
170         pq.pop();
171         vector<int> z=fft::multiply_mod(x,y,mod);
172         node u;
173         u.sz=z.size(),u.x=z;
174         pq.push(u);
175     }
176 }
177 int main()
178 {
179     scanf("%d",&n);
180     for(int i=1;i<=3000000;++i)A[i].push_back(1);
181     for(int i=1;i<=n;++i)
182     {
183         int x;
184         scanf("%d",&x);
185         A[x].push_back(1);
186     }
187     solve();
188 }
View Code

 

codeforces edu76 做题记录

原文:https://www.cnblogs.com/uuzlove/p/11909382.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!