Codeforces Round #402 (Div. 2)-白红宇

Codeforces Round #402 (Div. 2)

阅读量：5917 次

发布时间：2019-06-19

本文共 3276 字，大约阅读时间需要 10 分钟。

日常沙比提

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;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[10],b[10],ans;int main(){    //freopen("in","r",stdin);    n=read();    for(int i=1;i<=n;i++) a[read()]++;    for(int i=1;i<=n;i++) b[read()]++;    for(int i=1;i<=5;i++){        int c=a[i]+b[i];        if(c&1) {puts("-1");return 0;}        else ans+=abs(c/2-a[i]);    }    printf("%d",ans/2);}

View Code

日常沙比提2

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;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;}char s[20];int n,k;int main(){    //freopen("in","r",stdin);    scanf("%s",s+1);k=read();    n=strlen(s+1);    int c=0;    for(int i=1;i<=n;i++) if(s[i]=='0') c++;    if(c
           
            =1;i--){ if(s[i]=='0') zero++; else now++; if(zero==k) break; } printf("%d",now); }}

View Code

我去怎么这次三道沙比提

样例3良心！注意第一次买可以比$k$个多

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2e5+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,ans;struct Item{    int a,b,c;    bool operator <(const Item &r)const{        return c>r.c;    }}a[N];int main(){    //freopen("in","r",stdin);    n=read();k=read();    for(int i=1;i<=n;i++) a[i].a=read();    for(int i=1;i<=n;i++) a[i].b=read();    for(int i=1;i<=n;i++) a[i].c=a[i].b-a[i].a;    sort(a+1,a+1+n);    int i;    for(i=1;i<=k;i++) ans+=a[i].a;    while(i<=n&&a[i].c>=0) ans+=a[i].a,i++;    for(;i<=n;i++) ans+=a[i].b;    printf("%d",ans);}

View Code

题意：给两个字符串以及一个删除第一个字符串字符的操作序列，问多少次操作之后是最后的可以从第一个中找出第二个字符串的时刻

乱想一通，突然发现二分答案不就好了....

倒着处理变成加字符，二分加的字符的最晚时间最早，然后判定

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2e5+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,t[N],m;char a[N],b[N];bool check(int g){    int now=1;    for(int i=1;i<=n;i++) if(t[i]<=g){        if(a[i]==b[now]) now++;        if(now>m) return true;    }    return false;}void solve(){    int l=1,r=n,ans=0;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid)) ans=mid,r=mid-1;        else l=mid+1;    }    printf("%d",n-ans);}int main(){    //freopen("in","r",stdin);    scanf("%s%s",a+1,b+1);    n=strlen(a+1);    m=strlen(b+1);    for(int i=1;i<=n;i++) t[read()]=n-i+1;    solve();}