链接：https://codeforces.com/contest/1137
A - Skyscrapers
题解：对于每一段 $1$ 和每一段 $2$，统计他们的长度。因此对于相邻的两段长度求较小值，就有可能成为答案，维护所有的可能是答案的最大值即可。
AC代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n,t[maxn]; int l1,l2; int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&t[i]); l1=l2=0; vector<int> v; for(int i=1;i<=n;i++) { if(t[i]==1) l1++, l2=0; if(t[i]==2) l2++, l1=0; if(i==n || t[i]!=t[i+1]) { if(l1>0) v.push_back(l1); if(l2>0) v.push_back(l2); } } int ans=1; for(int i=0;i<v.size()-1;i++) { if(min(v[i],v[i+1])>ans) ans=min(v[i],v[i+1]); } cout<<2*ans<<endl; }
B - Circus - [暴力]
题解：
统计四种人的数目，$A=cnt(0,0), B=cnt(1,0), C=cnt(0,1), D=cnt(1,1)$，第一个代表是否会演小丑，第二个代表是否会演杂技。
设第一组中的三种人的数目 $cnt(1,0) = x, cnt(0,1) = C - y, cnt(1,1) = z$，因此会有等式 $x + z = y + (D-z)$，因此只需要枚举 $x,z$ 就能计算出 $y$。
然后只需要判断一下 $y ge 0, C-y ge 0$，以及 $n - [x+(C-y)+z] - [(B-x)+y+(D-z)] = A$ 就行了。
AC代码：
#include<bits/stdc++.h> using namespace std; const int maxn=5e3+10; int n; char c[maxn],a[maxn]; int A,B,C,D; vector<int> t[2][2]; int x,y,z; bool check() { for(x=0;x<=B;x++) { for(z=0;z<=D;z++) { y=x+z-D+z; if(y<0 || C-y<0) continue; if(x+(C-y)+z>n/2 || (B-x)+y+(D-z)>n/2) continue; if(n/2-(x+(C-y)+z) + n/2-((B-x)+y+(D-z)) == A) { return 1; } } } return 0; } int main() { cin>>n; scanf("%s",c+1); scanf("%s",a+1); A=B=C=D=0; t[0][0].clear(), t[1][0].clear(), t[0][1].clear(), t[1][1].clear(); for(int i=1;i<=n;i++) { if(c[i]=='0' && a[i]=='0') A++, t[0][0].push_back(i); if(c[i]=='1' && a[i]=='0') B++, t[1][0].push_back(i); if(c[i]=='0' && a[i]=='1') C++, t[0][1].push_back(i); if(c[i]=='1' && a[i]=='1') D++, t[1][1].push_back(i); } if(check()==0) cout<<"-1 "; else { // cout<<(n/2-(x+(C-y)+z))<<endl; // cout<<x<<endl; // cout<<C-y<<endl; // cout<<z<<endl; for(int i=0;i<n/2-(x+(C-y)+z);i++) printf("%d ",t[0][0][i]); for(int i=0;i<x;i++) printf("%d ",t[1][0][i]); for(int i=0;i<C-y;i++) printf("%d ",t[0][1][i]); for(int i=0;i<z;i++) printf("%d ",t[1][1][i]); } }
C - Skyscrapers - [离散化]
题意：
有个 $n$ 条横向街道，$m$ 条纵向街道，它们产生 $nm$ 个交点，每个交点上有一栋大楼高度 $h[i][j]$。
然后你对每个交点，你要把 $[1,x]$ 的整数重新赋值给这个十字上的所有大楼。使得，一条道路上任意两栋大楼之间的高度关系都与原来一致。
题解：
离散化裸题。
AC代码：
#include<bits/stdc++.h> using namespace std; int n,m; int h[1005][1005]; vector<int> r[1005],c[1005]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>h[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) r[i].push_back(h[i][j]); sort(r[i].begin(),r[i].end()); r[i].erase(unique(r[i].begin(),r[i].end()),r[i].end()); } for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) c[j].push_back(h[i][j]); sort(c[j].begin(),c[j].end()); c[j].erase(unique(c[j].begin(),c[j].end()),c[j].end()); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int tp1=lower_bound(r[i].begin(),r[i].end(),h[i][j])-r[i].begin(); int tp2=lower_bound(c[j].begin(),c[j].end(),h[i][j])-c[j].begin(); int tp3=r[i].end()-lower_bound(r[i].begin(),r[i].end(),h[i][j]); int tp4=c[j].end()-lower_bound(c[j].begin(),c[j].end(),h[i][j]); printf("%d ",max(tp1,tp2)+max(tp3,tp4)); } printf(" "); } }