首页 > 代码库 > Codeforces 558(C、D、E)总结
Codeforces 558(C、D、E)总结
558C
题意:给你n个数,可对每一个数进行操作(乘2或者除以2)。求最少的操作使得全部的数都相等。
思路 : dp[ t ] 表示全部的数转化到 t 所需的最少操作, vis[ t ] 表示有多少数能够转化成 t 。
对于一个数 num , 把它所能到达的数用上述的数组记录下即可了(详细看代码)。
注意 :
输入:
3
5 4 4
输出 : 2 (5/2*2=4)
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=100010; int n,vis[maxn],num[maxn]; void initial() { memset(num,0,sizeof(num)); memset(vis,0,sizeof(vis)); } void deal(int op) { int tp=op,ct=0; while(tp) { vis[tp]++; num[tp]+=ct; if(tp%2==1 && tp!=1) { int yp=tp/2*2,cnt=ct+2; while(yp<maxn) { vis[yp]++; num[yp]+=cnt; yp*=2; cnt++; } } tp/=2; ct++; } tp=op*2,ct=1; while(tp<maxn) { vis[tp]++; num[tp]+=ct; tp*=2; ct++; } } void input() { int u; for(int i=0;i<n;i++) { scanf("%d",&u); deal(u); } } void solve() { int Min=1<<30; for(int i=0;i<maxn;i++) if(vis[i]==n) Min=min(Min,num[i]); cout<<Min<<endl; } int main() { while(scanf("%d",&n)!=EOF) { initial(); input(); solve(); } return 0; }
558D
题意:给出n条信息。要你推断信息是否矛盾。或是否有多个出口,或是否有唯一出口。
信息有两种类型,一个是出口的若干区间,一个不是出口若干区间。
思路: 先通过出口的若干区间找出出口所在的树中根节点的区间。
然后在通过不是出
口的若干区间来推断。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define ll long long using namespace std; struct node { ll l,r; node(){} node(ll _l,ll _r):l(_l),r(_r){} }; vector <node> G; int n,m; ll st,ed; bool cmp(node p,node q) { if(p.l==q.l) return p.r<q.r; return p.l<q.l; } void initial() { G.clear(); st=(ll)1<<(n-1); ed=((ll)1<<n)-1; } void input() { int tp,t; ll u,v; for(int i=0;i<m;i++) { scanf("%d %I64d %I64d %d",&tp,&u,&v,&t); u=u<<(n-tp); for(int j=0;j<n-tp;j++) v=v<<1|1; if(t) { st=max(st,u); ed=min(ed,v); } else G.push_back(node(u,v)); } G.push_back(node(ed+1,ed+1)); } void solve() { ll ans=-1; sort(G.begin(),G.end(),cmp); for(int i=0;i<G.size();i++) { if(st>ed) break; if(st<G[i].l) { if(ans!=-1 || st+1<G[i].l) { cout<<"Data not sufficient!"<<endl; return ; } ans=st; } st=max(st,G[i].r+1); } if(ans==-1) cout<<"Game cheated!"<<endl; else cout<<ans<<endl; } int main() { while(scanf("%d %d",&n,&m)!=EOF) { initial(); input(); solve(); } return 0; }
558E
题意:给你一个长度为n的字符串(下标从1開始),然后给你m个操作。每一个操作有三个值 l,r,t。
假设t=1。表示将字符串中[ l ,r ]的部分依照升序排列。
假设t=0。表示将字符串中[ l ,r ]的部分依照降序排列。
最后要你输出原字符串经过m次操作后所形成的新的字符串。
思路:对于26个小写字母(a-z),分别建立线段树,即建26个线段树。
即每次改动 [ l , r ] 区间,则先通过26课线段树分别求出这个区间内的a–z的个数。然后将26课线
段树内的这一区间和置为0。
最后再依据顺序又一次给26课线段树的这一区间赋值即可了。
<span style="font-size:18px;">#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; const int N=100010; const int M=26; struct node { int l,r,sum,cover; } a[M][N*4]; string str; int n,m; void build(int cnt,int l,int r,int k) { a[cnt][k].l=l; a[cnt][k].r=r; a[cnt][k].sum=0; a[cnt][k].cover=-1; if(l==r) return ; int mid=(l+r)>>1; build(cnt,l,mid,2*k); build(cnt,mid+1,r,2*k+1); } void push_down(int cnt,int k) { if(a[cnt][k].cover!=-1) { a[cnt][k*2].cover=a[cnt][k*2+1].cover=a[cnt][k].cover; a[cnt][k*2].sum=(a[cnt][k*2].r+1-a[cnt][k*2].l)*a[cnt][k*2].cover; a[cnt][k*2+1].sum=(a[cnt][k*2+1].r+1-a[cnt][k*2+1].l)*a[cnt][k*2+1].cover; a[cnt][k].cover=-1; } } void update(int cnt,int l,int r,int k,int num) { if(l==a[cnt][k].l && r==a[cnt][k].r) { a[cnt][k].cover=num; a[cnt][k].sum=(a[cnt][k].r+1-a[cnt][k].l)*num; return ; } push_down(cnt,k); int mid=(a[cnt][k].l+a[cnt][k].r)>>1; if(r<=mid) update(cnt,l,r,2*k,num); else if(l>mid) update(cnt,l,r,2*k+1,num); else { update(cnt,l,mid,2*k,num); update(cnt,mid+1,r,2*k+1,num); } a[cnt][k].sum=a[cnt][k*2].sum+a[cnt][k*2+1].sum; } int query(int cnt,int l,int r,int k) { if(l==a[cnt][k].l && r==a[cnt][k].r) return a[cnt][k].sum; push_down(cnt,k); int mid=(a[cnt][k].l+a[cnt][k].r)>>1; if(r<=mid) return query(cnt,l,r,2*k); else if(l>mid) return query(cnt,l,r,2*k+1); else return query(cnt,l,mid,2*k)+query(cnt,mid+1,r,2*k+1); } void input() { for(int i=0; i<M; i++) build(i,1,n,1); getchar(); getline(cin,str); for(int i=1; i<=n; i++) update(str[i-1]-'a',i,i,1,1); } void solve() { int l,r,t; while(m--) { int num[M]; scanf("%d %d %d",&l,&r,&t); for(int i=0; i<M; i++) { num[i]=query(i,l,r,1); update(i,l,r,1,0); } int pos=l; if(t==1) { for(int i=0; i<M; i++) if(num[i]) { update(i,pos,pos+num[i]-1,1,1); pos=pos+num[i]; } } else { for(int i=M-1; i>=0; i--) if(num[i]) { update(i,pos,pos+num[i]-1,1,1); pos=pos+num[i]; } } } for(int i=1; i<=n; i++) for(int j=0; j<M; j++) if(query(j,i,i,1)) { printf("%c",j+'a'); break; } printf("\n"); } int main() { while(scanf("%d %d",&n,&m)!=EOF) { input(); solve(); } return 0; } </span>
Codeforces 558(C、D、E)总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。