首页 > 代码库 > Educational Codeforces Round 23 补题小结
Educational Codeforces Round 23 补题小结
昨晚听说有教做人场，去补了下玩。
大概我的水平能做个5/6的样子？
（不会二进制Trie啊，我真菜）
A.
傻逼题。大概可以看成向量加法，判断下就好了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int x1,x2,yy1,y2,x,y; int main(){ scanf("%d%d%d%d%d%d",&x1,&yy1,&x2,&y2,&x,&y); int dx=abs(x1-x2),dy=abs(yy1-y2); if((abs(dx/x-dy/y)%2==0)&&(dx%x==0)&&(dy%y==0))puts("YES"); else puts("NO"); }
B.
找符合要求的最小三元组乘积出现次数。
sort一下随便搞搞就行了。
#include<bits/stdc++.h> #define N 100010 typedef long long ll; using namespace std; ll a[N];int n;ll minv; inline ll read(){ ll f=1,x=0;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1);ll cnt=0; for(int i=1;i<=n;i++)if(a[i]==a[3])cnt++; if(a[1]==a[3])cout<<(cnt-2)*(cnt-1)*cnt/6<<endl; else if(a[2]==a[3])cout<<(cnt-1)*cnt/2<<endl; else cout<<cnt<<endl; }
C.
第一反应数位dp，反正也可做。
数位记忆化搜索大概也行的样子。
但是可以显然地证明一个性质：x?+?1?-?sumd(x?+?1)?≥?x?-?sumd(x)
这就满足了一个单调性，按照出题人的想法是可以二分答案。
但是可以直接枚举最大的范围嘛！干嘛非要写个二分答案
而且这么写跑得飞快。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,s; inline bool check(ll x){ ll res=x; while(res){x-=res%10;res/=10;} return x>=s; } int main(){ cin>>n>>s;ll maxv=min(n,s+180),sum=0; for(ll i=s;i<=maxv;i++)if(check(i))++sum; cout<<n-maxv+sum<<endl; }
D.
用单调栈维护一个"一个数向左向右最大可以做max与min能管的距离"
好久不上语文课了表达能力=0
实在不行看官方题解吧。
#include<bits/stdc++.h> #define N 1000005 #define inf 1000000007 typedef long long ll; using namespace std; int n,a[N]; ll ans1,ans2,ans; stack<int>s1,s2; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int main(){ n=read(); s1.push(0);s2.push(0); for(int i=1;i<=n;i++){ a[i]=read();a[0]=0; while(s1.top()&&a[i]<a[s1.top()]){ int top=s1.top();s1.pop(); ans1-=1LL*a[top]*(top-s1.top()); } ans1+=1LL*a[i]*(i-s1.top());s1.push(i); a[0]=inf; while(s2.top()&&a[i]>a[s2.top()]){ int top=s2.top();s2.pop(); ans2-=1LL*a[top]*(top-s2.top()); } ans2+=1LL*a[i]*(i-s2.top());s2.push(i); ans+=ans2-ans1; } cout<<ans<<endl; }
E.
我太菜了，以前居然没见过这种在二进制字典树上的贪心……
建一个二进制的字典树，然后贪心一下看能不能搞成1就行了。
具体的我日后可能得写个blog介绍下Trie的贪心。
#include<bits/stdc++.h> #define N 3000005 using namespace std; int size[N],ch[N][2],n,cnt,a,b,type; inline void ins(int x,int add){ int now=1; for(int i=26;i>=0;i--){ bool v=((x>>i)&1); if(!ch[now][v])ch[now][v]=++cnt; now=ch[now][v]; size[now]+=add; } } inline void query(int x,int y){ int ans=0,now=1,val=0; for(int i=26;i>=0&&now;i--){ bool xbit=((x>>i)&1),ybit=((y>>i)&1); val+=val; if(ybit){ ans+=size[ch[now][xbit]];now=ch[now][!xbit]; val+=!xbit; } else{now=ch[now][xbit];val+=xbit;} } printf("%d\n",ans); } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int main(){ cnt=1;n=read(); while(n--){ int opt=read(),x=read(); if(opt==1)ins(x,1); if(opt==2)ins(x,-1); if(opt==3){ int y=read(); query(x,y); } } }
F.
看到mex突然激动，感觉可能是个DS题。
果然是。
第一反应主席树求一下就好，后来想下，主席树也是没有必要的。
直接线段树维护就行。
类似于取反，求最左节点的操作。
值域过大可以选择动态开点或者离散化。
我就写了个离散化……
类似的分解的操作的题bzoj都有，如果一下子看不懂这篇
可以QQ找我问几个原题。
#include<bits/stdc++.h> #define N 300005 #define lson (o<<1) #define rson (o<<1|1) using namespace std; typedef long long ll; ll a[N]; struct Query{ll l,r,opt;}Q[N]; int n,len; struct Segment_Tree{ int sumv[N<<4],addv[N<<4],rev[N<<4]; inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];} inline void puttag(int o,int l,int r,int add,int re){ if(re){ if(addv[o]==-1)rev[o]^=1,sumv[o]=r-l+1-sumv[o]; else addv[o]^=1,sumv[o]=r-l+1-sumv[o]; } else if(add!=-1){ rev[o]=0;addv[o]=add;sumv[o]=(r-l+1)*add; } } inline void pushdown(int o,int l,int r){ int mid=(l+r)>>1; puttag(lson,l,mid,addv[o],rev[o]); puttag(rson,mid+1,r,addv[o],rev[o]); addv[o]=-1;rev[o]=0; } void build(int o,int l,int r){ if(l==r){addv[o]=-1;return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); addv[o]=-1; } int querymex(int o,int l,int r){ if(l==r)return l; int mid=(l+r)>>1;pushdown(o,l,r); if(sumv[lson]<mid-l+1)return querymex(lson,l,mid); else return querymex(rson,mid+1,r); } void change(int o,int l,int r,int ql,int qr,int add,int re){; if(ql<=l&&r<=qr){puttag(o,l,r,add,re);return;} int mid=(l+r)>>1;pushdown(o,l,r); if(ql<=mid)change(lson,l,mid,ql,qr,add,re); if(qr>mid)change(rson,mid+1,r,ql,qr,add,re); pushup(o); } }T; inline ll read(){ ll f=1,x=0;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int main(){ n=read(); for(int i=1;i<=n;i++){ Q[i].opt=read();Q[i].l=read();Q[i].r=read(); } a[1]=1; for(int i=1;i<=n;i++)a[3*i-1]=Q[i].l,a[3*i]=Q[i].r,a[3*i+1]=Q[i].r+1; sort(a+1,a+n*3+2); len=1; for(int i=2;i<=3*n+1;++i)if(a[i]!=a[i-1]) a[++len]=a[i]; T.build(1,1,len); for(int i=1;i<=n;i++){ int x=lower_bound(a+1,a+len+1,Q[i].l)-a,y=lower_bound(a+1,a+len+1,Q[i].r)-a; if(Q[i].opt==1)T.change(1,1,len,x,y,1,0); if(Q[i].opt==2)T.change(1,1,len,x,y,0,0); if(Q[i].opt==3)T.change(1,1,len,x,y,-1,1); printf("%lld\n",a[T.querymex(1,1,len)]); } }
啊最后总结下吧。
姿势水平还不够，还得学习一个。
数据结构要学会活学活用，用现有的水平解决一些不是很常规的问题。
dp什么的思维还是不够，要学习一个。
不过这场的外国人居然出了两个DS？
但是可能外国的DS水平不如我国？这个Trie题讲道理可能在国内只有T2的难度吧。
最后一个Segment-Tree可以算奇奇怪怪的常规应用的组合。
所以还是要熟练呀~
Educational Codeforces Round 23 补题小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。