首页 > 代码库 > Codeforces Round #390 (Div. 2)

Codeforces Round #390 (Div. 2)

Codeforces Round #390 (Div. 2)

22:35~0:35  1.6.2017

 


 

A.Lesha and array splitting

题意:自己看

题解:

构造什么的最弱了

想了想,貌似除了0每个数单独一组就可以,只要有一个非0数则一定可以有解

0的话不停往前找到第一个非0然后合为一组

第一个数是0怎么办?先让第一个数往后找一个非0呗

比赛的时候智商骤减,写的代码好难看还写了好长时间,并且还WA一次...应该可以很简洁的吧

 

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=105;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,a[N],f[N],l[N],r[N],k,sum,vis[N];void solve(){    k++;    l[k]=1;r[k]=1;    if(f[1]!=0){        for(int i=2;i<=n;i++){            if(f[i]==0){                int p=i-1;                while(f[p]==0) p--;                if(p<=r[k]) r[k]=i;                else {k++;l[k]=p;r[k]=i;}            }        }        puts("YES");        int now=1,cnt=k;        for(int i=1;i<=n;i++){            if(l[now]<=i&&i<=r[now]) {if(i==r[now])now++;}            else cnt++;        }        printf("%d\n",cnt);        now=1;        for(int i=1;i<=n;i++){            if(l[now]<=i&&i<=r[now]){                if(!vis[now]) printf("%d %d\n",l[now],r[now]),vis[now]=1;                if(i==r[now]) now++;            }else printf("%d %d\n",i,i);        }    }else{        int p=1;        while(f[p]==0) p++;//,printf("hi %d %d\n",p,f[p]);        if(p>n) {puts("NO");return;}        r[k]=p;        for(int i=p+1;i<=n;i++){            if(f[i]==0){                int p=i-1;                while(f[p]==0) p--;                if(p<=r[k]) r[k]=i;                else {k++;l[k]=p;r[k]=i;}            }        }        puts("YES");        int now=1,cnt=k;        for(int i=1;i<=n;i++){            if(l[now]<=i&&i<=r[now]) {if(i==r[now])now++;}            else cnt++;        }        printf("%d\n",cnt);        now=1;        for(int i=1;i<=n;i++){            if(l[now]<=i&&i<=r[now]){                if(!vis[now]) printf("%d %d\n",l[now],r[now]),vis[now]=1;                if(i==r[now]) now++;            }else printf("%d %d\n",i,i);        }    }        }int main(){    n=read();    for(int i=1;i<=n;i++) a[i]=read(),f[i]=a[i]==0?0:1;    solve();}
点我可以展开哦

 


 

B.Ilya and tic-tac-toe game

题意:4*4的井字棋判一步能不能获胜

题解:

直接无脑暴力枚举下在那里行了不管了

结果又WA一次因为忘判断刚下的位置是中间构成3个

 

技术分享
////  main.cpp//  b////  Created by Candy on 2017/1/6.//  Copyright © 2017年 Candy. All rights reserved.//#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=10;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n=4;char s[N][N];inline bool can(int x){return 1<=x&&x<=4;}bool check(int i,int j){    if(i>2){        if(s[i-1][j]==x&&s[i-2][j]==x) return true;        if(j>2&&s[i-1][j-1]==x&&s[i-2][j-2]==x) return true;        if(j<=2&&s[i-1][j+1]==x&&s[i-2][j+2]==x) return true;    }    if(i<=2){        if(s[i+1][j]==x&&s[i+2][j]==x) return true;        if(j>2&&s[i+1][j-1]==x&&s[i+2][j-2]==x) return true;        if(j<=2&&s[i+1][j+1]==x&&s[i+2][j+2]==x) return true;    }    if(j>2&&s[i][j-1]==x&&s[i][j-2]==x) return true;    if(j<=2&&s[i][j+1]==x&&s[i][j+2]==x) return true;        if(can(i-1)&&can(i+1)&&s[i-1][j]==x&&s[i+1][j]==x) return true;    if(can(j-1)&&can(j+1)&&s[i][j-1]==x&&s[i][j+1]==x) return true;    if(can(i-1)&&can(j-1)&&can(i+1)&&can(j+1)&&s[i-1][j-1]==x&&s[i+1][j+1]==x) return true;    if(can(i-1)&&can(j-1)&&can(i+1)&&can(j+1)&&s[i-1][j+1]==x&&s[i+1][j-1]==x) return true;    return false;}void solve(){    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(s[i][j]==.&&check(i,j)){puts("YES");return;}    puts("NO");}int main(int argc, const char * argv[]) {    for(int i=1;i<=4;i++) scanf("%s",s[i]+1);    solve();    return 0;}
点我可以展开哦

 

 


  

C.Vladik and chat

题意:...

题解:

还剩一个小时,貌似就是把人名分配给消息啊,字符串处理一下每条消息可以用那几个人名,然后搞个二分图跑最大流就行了

还要输出解?貌似找满流的边就可以了

字符串处理的太恶心了,当时好晚了好困了已经不知道自己哪里会写错了

然而到最后一刻还是WA,哎

 

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=205,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,m;char name[N][N];int ln[N],able[N];struct message{    char s[N];    bool has[N];}a[N];bool can(char c){    if(c>=a&&c<=z) return false;    if(c>=A&&c<=Z) return false;    if(c>=0&&c<=9) return false;    return true;}bool check(char *s,int pos,char *a,int len,int fin){    for(int i=1;i<=len;i++)        if(s[pos+i-1]!=a[i]) return false;;    if(pos+len==fin+1||can(s[pos+len])) return true;    return false;}int s,t,u,v;struct edge{    int v,ne,c,f;}e[N*N<<1];int cnt,h[N];inline void ins(int u,int v,int c){//printf("ins %d %d %d\n",u,v,c);    cnt++;    e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;}int vis[N],d[N],q[N],head=1,tail=1;bool bfs(){    memset(vis,0,sizeof(vis));    memset(d,0,sizeof(d));    head=tail=1;    q[tail++]=s;d[s]=0;vis[s]=1;    while(head!=tail){        int u=q[head++];//printf("u %d\n",u);        for(int i=h[u];i;i=e[i].ne){            int v=e[i].v;            if(!vis[v]&&e[i].c>e[i].f){                vis[v]=1;d[v]=d[u]+1;                q[tail++]=v;                if(v==t) return true;            }        }    }    return false;}int cur[N];int dfs(int u,int a){    if(u==t||a==0) return a;    int flow=0,f;    for(int &i=cur[u];i;i=e[i].ne){        int v=e[i].v;        if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){            flow+=f;            e[i].f+=f;            e[((i-1)^1)+1].f-=f;            a-=f;            if(a==0) break;        }    }    return flow;}int dinic(){    int flow=0;    while(bfs()){        for(int i=s;i<=t;i++) cur[i]=h[i];        flow+=dfs(s,INF);    }    return flow;}void getGraph(){    cnt=0;    memset(h,0,sizeof(h));    s=0;t=m+n+1;    for(int i=1;i<=m;i++) if(a[i].s[1]==?) ins(s,i,1);    for(int i=1;i<=n;i++) if(able[i]) ins(m+i,t,1);    for(int i=1;i<=m;i++) if(a[i].s[1]==?)        for(int j=1;j<=n;j++) if(able[j]&&!a[i].has[j]) ins(i,m+j,1);}void solve(){    int tot=0;    for(int k=1;k<=m;k++) if(a[k].s[1]==?){tot++;        int len=strlen(a[k].s+1);        for(int i=1;i<=len;i++) if(i==1||can(a[k].s[i-1]))            for(int j=1;j<=n;j++)                if(check(a[k].s,i,name[j],ln[j],len)) {a[k].has[j]=1;break;}    }    getGraph();    int ans=dinic(); //printf("anstot %d %d\n",ans,tot);    if(ans!=tot) puts("Impossible");    else{        for(int i=1;i<=m;i++){            if(a[i].s[1]!=?) puts(a[i].s+1);            else{                for(int k=h[i];k;k=e[k].ne) if(e[k].f==1){//printf("get %d %d %d\n",k,e[k].f,e[k].v);                    printf("%s",name[e[k].v-m]+1);                    puts(a[i].s+2);                    break;                }            }        }    }}int main(int argc, const char * argv[]) {    int T=read();    while(T--){        n=read();        for(int i=1;i<=n;i++) scanf("%s",name[i]+1),ln[i]=strlen(name[i]+1),able[i]=1;        m=read();        for(int i=1;i<=m;i++){            gets(a[i].s+1);memset(a[i].has,0,sizeof(a[i].has));            if(a[i].s[1]!=?){                int flag=1;                for(int j=1;j<=n;j++){                    for(int k=1;k<=ln[j];k++) if(a[i].s[k]!=name[j][k]) {flag=0;break;}                    if(flag) {able[j]=0;break;}                    flag=1;                }            }        }        //        puts("test!!!");//        for(int i=1;i<=n;i++) printf("%d\n",ln[i]);//        for(int i=1;i<=m;i++) printf("look %s\n",a[i].s+1);        solve();    }    return 0;}
不要看我啦!

 

看了一下别人提交的,怎么都用了map,代码比我短多了,还AC


 

D.Fedor and coupons

题意:n个区间选k个使交集最大

题解:

今天晚自习第三节之前开始做的,用了不到1h,早知道就做这道题了,世事无常

区间按照先l后r小到大排序,可以发现答案区间一定是一个区间的l和一个区间的r

枚举是那个区间的l,然后对于这个l选k个区间后的可行的最大的r就是在l之前枚举过的区间中的k大值

可以用平衡树维护,复杂度O(nlogn)

然后发现还要输出解,在重复一遍一遇到当前答案=最大值就输出呗,平衡树节点上多一个id就行了

然后发现多个区间的r可能相同,于是把id改成了一个链表,直接用了邻接链表那一套

 

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define lc t[x].l#define rc t[x].rconst int N=3e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,k;struct rec{    int l,r,id;    bool operator <(const rec &rhs)const{return l<rhs.l;}}a[N];struct edge{    int id,ne;}e[N];int h[N],cnt;inline void inse(int u,int v){    cnt++;    e[cnt].id=v;e[cnt].ne=h[u];h[u]=cnt;}struct node{    int l,r,v,w,size,rnd;}t[N];int sz,root;inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}inline void rturn(int &x){    int c=lc;lc=t[c].r;t[c].r=x;    t[c].size=t[x].size;update(x);x=c;}inline void lturn(int &x){    int c=rc;rc=t[c].l;t[c].l=x;    t[c].size=t[x].size;update(x);x=c;}void ins(int &x,int v,int id){    if(x==0){        sz++;x=sz;        t[sz].l=t[sz].r=0;t[sz].size=t[sz].w=1;        t[sz].v=v;t[sz].rnd=rand();                inse(x,id);        return;    }    t[x].size++;    if(t[x].v==v) {t[x].w++;inse(x,id);return;}    if(v<t[x].v){        ins(lc,v,id);        if(t[lc].rnd<t[x].rnd) rturn(x);    }else{        ins(rc,v,id);        if(t[rc].rnd<t[x].rnd) lturn(x);    }}int kth(int x,int k){    if(x==0) return 0;    if(k<=t[lc].size) return kth(lc,k);    else if(k>t[lc].size+t[x].w) return kth(rc,k-t[lc].size-t[x].w);    else return x;}int ans;void solve(){    srand(222);    int r=0;    sort(a+1,a+1+n);    for(int i=1;i<=n;i++){        ins(root,a[i].r,a[i].id);        if(i>=k){            r=t[kth(root,i-k+1)].v;            ans=max(ans,r-a[i].l+1);        }    }    printf("%d\n",ans);    if(ans==0){        for(int i=1;i<=k;i++) printf("%d ",i);        return;    }    memset(t,0,sizeof(t));    sz=root=0;    cnt=0;memset(h,0,sizeof(h));    for(int i=1;i<=n;i++){        ins(root,a[i].r,a[i].id);        if(i>=k){            r=t[kth(root,i-k+1)].v;//printf("hello %d\n",i);            if(r-a[i].l+1==ans){                for(int j=i-k+1;j<=i;j++){                    int u=kth(root,j);                    for(int k=h[u];k;k=e[k].ne) printf("%d ",e[k].id),j++;                    j--;                }                break;            }                    }    }}int main(){    //freopen("in.txt","r",stdin);    n=read();k=read();    for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(),a[i].id=i;    solve();}
点我啊

  

和mywaythere神犇讨论她说可以用优先队列,等会研究一下

 

 


 

E.

人太弱不会


 

总结:

1.比赛前在群里讨论某个弱智问题,没有平静下来

2.时间比较晚,之前没有好好休息

3.比赛时心情太急躁,着急去写代码没有认真思考

4.做题顺序问题,不要感觉时间很急还是英文题就不把每道题读一遍,难度不一定是升序

 

Codeforces Round #390 (Div. 2)