Codeforces Round #545 (Div. 2)

A. Sushi for Two

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int a[maxn];
 5 int main(){
 6     int one=0,two=0;
 7     int n;
 8     scanf("%d",&n);
 9     int ans=0;
10     int flag=0;
11     for(int i=0;i<n;i++)scanf("%d",&a[i]);
12     flag=a[0];
13     for(int i=0;i<n;i++){
14         if(flag==1){
15             if(a[i]==1)one++;
16             else {
17                 ans=max(ans,min(one,two));
18                 two=1;
19                 flag=2;
20             }
21         }
22         else if(flag==2){
23             if(a[i]==2)two++;
24             else {
25                 ans=max(ans,min(one,two));
26                 one=1;
27                 flag=1;
28             }
29         }    
30     }
31     ans=max(ans,min(two,one));
32     cout<<ans*2<<endl;
33 }

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)

有两个未知数暴力即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define FOR(i,f_start,f_end) for(int i=f_start ;i<f_end;i++)
 4 #define MT(x,i) memset(x,i,sizeof(x))
 5 #define ll long long 
 6 #define inf 0x3f3f3f3f
 7 vector<int >zero,two,three,one;
 8 char a[5000+5],b[5000+5];
 9 int main(){
10     int n;
11     int na=0,nb=0,nc=0,nd=0;
12     scanf("%d",&n);
13     scanf("%s",a);
14     scanf("%s",b);
15     for(int i=0;i<n;i++){
16         if(a[i]=='0'&&b[i]=='0')na++,zero.push_back(i+1);
17         else if(a[i]=='0'&&b[i]=='1')nb++,one.push_back(i+1);
18         else if(a[i]=='1'&&b[i]=='0')nc++,two.push_back(i+1);
19         else nd++,three.push_back(i+1);
20     }
21     FOR(a,0,na+1){
22         FOR(b,0,nb+1){
23             int c=n-2*(a+b)-nb-nd+b;
24             if(c>=0&&c<=nc){
25                 int d=n/2-c-a-b;
26                 if(d>=0&&d<=nd){
27                     FOR(i,0,a){
28                         printf("%d ",zero[i]);
29                     }
30                     FOR(i,0,b){
31                         printf("%d ",one[i]);
32                     }
33                     FOR(i,0,c)
34                         printf("%d ",two[i]);
35                     FOR(i,0,d)
36                         printf("%d ",three[i]);
37                 return 0;
38                 }
39             }
40         }
41     }
42     printf("-1");
43     return 0;
44 }

C. Skyscrapers

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
 4 #define MT(x,i) memset(x,i,sizeof(x))
 5 #define inf 0x3f3f3f3f
 6 #define mkp make_pair
 7 #define all(v) (v).begin(),(v).end()
 8 #define F first
 9 #define S second
10 #define pii pair<int,int>
11 #define pb push_back
12 const int maxn=1e3+5;
13 int a[maxn][maxn];
14 int rr[maxn][maxn],cc[maxn][maxn],r[maxn],l[maxn];
15 int main(){
16     int n,m ;
17     scanf("%d%d",&n,&m);
18     FOR(i,1,n)
19         FOR(j,1,m)scanf("%d",&a[i][j]);
20     FOR(i,1,n){
21         vector<pii>v;
22         FOR(j,1,m){
23             v.pb(mkp(a[i][j],j));
24         }
25         sort(all(v));
26         int last=-1,cnt=0;
27         for(pii tmp:v){
28             if(tmp.F!=last){
29                 cnt++;
30                 last=tmp.F;
31             }
32             rr[i][tmp.S]=cnt;
33         }
34         r[i]=cnt;
35     }
36     FOR(i,1,m){
37             vector<pii>v;
38         FOR(j,1,n){
39             v.pb(mkp(a[j][i],j));    
40         }
41         sort(all(v));
42         int last=-1,cnt=0;
43         for(pii tmp:v){
44             if(tmp.F!=last){
45                 last=tmp.F;
46                 cnt++;
47             }
48             cc[tmp.S][i]=cnt;
49         }
50         l[i]=cnt;
51     }
52     FOR(i,1,n){
53         FOR(j,1,m){
54             printf("%d ",max(rr[i][j],cc[i][j])+max(r[i]-rr[i][j],l[j]-cc[i][j]));
55         }
56         puts("");
57     }
58 
59     return 0;
60 }

D. Camp Schedule

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
 4 #define MT(x,i) memset(x,i,sizeof(x))
 5 #define inf 0x3f3f3f3f
 6 #define mkp make_pair
 7 #define all(v) (v).begin(),(v).end()
 8 #define F first
 9 #define S second
10 #define pii pair<int,int>
11 #define pb push_back
12 const int maxn=5e5+5;
13 char s[maxn],t[maxn];
14 int Next[maxn];
15 int get_next(const char *s, int *Next)
16 {
17     int i = 0, j = -1, len = strlen(s);
18     Next[0] = -1;
19     while (i<len)
20     {
21         if (j==-1 || s[i]==s[j])
22             Next[++i] = ++j;
23         else
24             j = Next[j];
25     }
26 
27     return len;
28 }
29 
30 int main(){
31     scanf("%s%s",s,t);
32     int a1,a2,b1,b2;
33     a1=a2=b1=b2=0;
34     int len1=strlen(s),len2=strlen(t);
35     if(len1<len2){
36         printf("%s",s);
37         return 0;
38     }
39     FOR(i,0,len1-1){
40         if(s[i]=='1')a1++;
41         else b1++;
42     }
43     FOR(i,0,len2-1){
44         if(t[i]=='1')a2++;
45         else b2++;
46     }
47     int suffix=0;
48     get_next(t, Next);
49     suffix = Next[len2];
50     if(a1>=a2&&b1>=b2){
51         a1-=a2,b1-=b2;
52         printf("%s",t);
53         int sa=0,sb=0;
54         FOR(i,suffix,len2-1){
55             if(t[i]=='1')sa++;
56             else sb++;
57         }
58         int tx;
59         if(sa&&sb){
60             tx=min(a1/sa,b1/sb);
61         }
62         else if(sa&&!sb){
63             tx=a1/sa;
64         }
65         else if(!sa&&sb){
66             tx=b1/sb;
67         }
68         a1-=tx*sa,b1-=tx*sb;
69         FOR(i,1,tx)printf("%s",t+suffix);
70         while(a1--)printf("1");
71         while(b1--)printf("0");
72     }
73     else {
74         printf("%s",s);
75     }
76 
77     return 0;
78 }