Codeforces Round #545 (Div. 2)

A. Sushi for Two

题意：给出 只有1 和2 组成的数组  求最大形如xxxyyy的长度 

思路：直接扫一边 1 和2 分界的时候记一下分界之前的那个 1或2的连续长度即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int main(){
    int one=0,two=0;
    int n;
    scanf("%d",&n);
    int ans=0;
    int flag=0;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    flag=a[0];
    for(int i=0;i<n;i++){
        if(flag==1){
            if(a[i]==1)one++;
            else {
                ans=max(ans,min(one,two));
                two=1;
                flag=2;
            }
        }
        else if(flag==2){
            if(a[i]==2)two++;
            else {
                ans=max(ans,min(one,two));
                one=1;
                flag=1;
            }
        }    
    }
    ans=max(ans,min(two,one));
    cout<<ans*2<<endl;
}

B. Circus

题意：每个人可能有两种属性  1表示有0表示没有   则一个人有四种情况 11 10 01 00 让分成两组  （为了叙述方便 前面的数字表示前面的属性，后面的数字表示后面的属性，例如10 前面的属性有，后面的属性无）分组后 要使其中一组的前面一个属性多少个人有等于 后面一组的后面一个属性有多少个人有

思路：

设第一组选了 四种人的数量分别为a(0,0) b(0,1) c(1,0) d(1 1) 总数分别为na nb nc nd

而根据两组的等式关系有  c+d=(nb-b)+(nd-d)

有两个未知数 暴力即可

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define ll long long 
#define inf 0x3f3f3f3f
vector<int >zero,two,three,one;
char a[5000+5],b[5000+5];
int main(){
    int n;
    int na=0,nb=0,nc=0,nd=0;
    scanf("%d",&n);
    scanf("%s",a);
    scanf("%s",b);
    for(int i=0;i<n;i++){
        if(a[i]=='0'&&b[i]=='0')na++,zero.push_back(i+1);
        else if(a[i]=='0'&&b[i]=='1')nb++,one.push_back(i+1);
        else if(a[i]=='1'&&b[i]=='0')nc++,two.push_back(i+1);
        else nd++,three.push_back(i+1);
    }
    FOR(a,0,na+1){
        FOR(b,0,nb+1){
            int c=n-2*(a+b)-nb-nd+b;
            if(c>=0&&c<=nc){
                int d=n/2-c-a-b;
                if(d>=0&&d<=nd){
                    FOR(i,0,a){
                        printf("%d ",zero[i]);
                    }
                    FOR(i,0,b){
                        printf("%d ",one[i]);
                    }
                    FOR(i,0,c)
                        printf("%d ",two[i]);
                    FOR(i,0,d)
                        printf("%d ",three[i]);
                return 0;
                }
            }
        }
    }
    printf("-1");
    return 0;
}

C. Skyscrapers

题意  有n*m个房子分布在网格图中  问分别对每一行和每一列的房子进行一下映射 使得每一行的房子高度大小关系不变 并且映射的范围是（1-x）要使x尽可能小  （这里的映射只是针对选定的一个行和列而言 到另外一行重新映射 是互不影响的）

思路：预处理每一行（和每一列）的位置大小 其中相等的可以进行类似合并的操作 最后针对每一个点  他的最小x 为 max(行的大小位置，列的大小位置)+max(行总数-行的大小位置 ，列总数-列的大小位置) 画个图很容易理解

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define inf 0x3f3f3f3f
#define mkp make_pair
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
const int maxn=1e3+5;
int a[maxn][maxn];
int rr[maxn][maxn],cc[maxn][maxn],r[maxn],l[maxn];
int main(){
    int n,m ;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)
        FOR(j,1,m)scanf("%d",&a[i][j]);
    FOR(i,1,n){
        vector<pii>v;
        FOR(j,1,m){
            v.pb(mkp(a[i][j],j));
        }
        sort(all(v));
        int last=-1,cnt=0;
        for(pii tmp:v){
            if(tmp.F!=last){
                cnt++;
                last=tmp.F;
            }
            rr[i][tmp.S]=cnt;
        }
        r[i]=cnt;
    }
    FOR(i,1,m){
            vector<pii>v;
        FOR(j,1,n){
            v.pb(mkp(a[j][i],j));    
        }
        sort(all(v));
        int last=-1,cnt=0;
        for(pii tmp:v){
            if(tmp.F!=last){
                last=tmp.F;
                cnt++;
            }
            cc[tmp.S][i]=cnt;
        }
        l[i]=cnt;
    }
    FOR(i,1,n){
        FOR(j,1,m){
            printf("%d ",max(rr[i][j],cc[i][j])+max(r[i]-rr[i][j],l[j]-cc[i][j]));
        }
        puts("");
    }

    return 0;
}

D. Camp Schedule

题意 给出一个串 s 和一个串t（都是01串）  现对s串进行重新排序  使得串t在排序后的串后尽可能多的 出现（可以重叠）

思路：先由 0 1 的数量关系 和串的长度 判断t可不可能在s中出现 然后找出t的最长相等的前缀和后缀（kmp的get_next 不然会超时）之后就由 不在公共前缀和后缀里面的01的数量关系构造即可

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define inf 0x3f3f3f3f
#define mkp make_pair
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
const int maxn=5e5+5;
char s[maxn],t[maxn];
int Next[maxn];
int get_next(const char *s, int *Next)
{
    int i = 0, j = -1, len = strlen(s);
    Next[0] = -1;
    while (i<len)
    {
        if (j==-1 || s[i]==s[j])
            Next[++i] = ++j;
        else
            j = Next[j];
    }

    return len;
}

int main(){
    scanf("%s%s",s,t);
    int a1,a2,b1,b2;
    a1=a2=b1=b2=0;
    int len1=strlen(s),len2=strlen(t);
    if(len1<len2){
        printf("%s",s);
        return 0;
    }
    FOR(i,0,len1-1){
        if(s[i]=='1')a1++;
        else b1++;
    }
    FOR(i,0,len2-1){
        if(t[i]=='1')a2++;
        else b2++;
    }
    int suffix=0;
    get_next(t, Next);
    suffix = Next[len2];
    if(a1>=a2&&b1>=b2){
        a1-=a2,b1-=b2;
        printf("%s",t);
        int sa=0,sb=0;
        FOR(i,suffix,len2-1){
            if(t[i]=='1')sa++;
            else sb++;
        }
        int tx;
        if(sa&&sb){
            tx=min(a1/sa,b1/sb);
        }
        else if(sa&&!sb){
            tx=a1/sa;
        }
        else if(!sa&&sb){
            tx=b1/sb;
        }
        a1-=tx*sa,b1-=tx*sb;
        FOR(i,1,tx)printf("%s",t+suffix);
        while(a1--)printf("1");
        while(b1--)printf("0");
    }
    else {
        printf("%s",s);
    }

    return 0;
}