链接：https://codeforces.com/contest/1137
A - Skyscrapers
题解：对于每一段 $1$ 和每一段 $2$，统计他们的长度。因此对于相邻的两段长度求较小值，就有可能成为答案，维护所有的可能是答案的最大值即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
int n,t[maxn];
int l1,l2;
int main()
{
cin>>n;
for(int i=;i<=n;i++) scanf("%d",&t[i]); l1=l2=;
vector<int> v;
for(int i=;i<=n;i++)
{
if(t[i]==) l1++, l2=;
if(t[i]==) l2++, l1=; if(i==n || t[i]!=t[i+])
{
if(l1>) v.push_back(l1);
if(l2>) v.push_back(l2);
}
} int ans=;
for(int i=;i<v.size()-;i++)
{
if(min(v[i],v[i+])>ans) ans=min(v[i],v[i+]);
}
cout<<*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+;
int n;
char c[maxn],a[maxn];
int A,B,C,D;
vector<int> t[][];
int x,y,z;
bool check()
{
for(x=;x<=B;x++)
{
for(z=;z<=D;z++)
{
y=x+z-D+z;
if(y< || C-y<) continue;
if(x+(C-y)+z>n/ || (B-x)+y+(D-z)>n/) continue;
if(n/-(x+(C-y)+z) + n/-((B-x)+y+(D-z)) == A)
{
return ;
}
}
}
return ;
}
int main()
{
cin>>n;
scanf("%s",c+);
scanf("%s",a+); A=B=C=D=;
t[][].clear(), t[][].clear(), t[][].clear(), t[][].clear();
for(int i=;i<=n;i++)
{
if(c[i]=='' && a[i]=='') A++, t[][].push_back(i);
if(c[i]=='' && a[i]=='') B++, t[][].push_back(i);
if(c[i]=='' && a[i]=='') C++, t[][].push_back(i);
if(c[i]=='' && a[i]=='') D++, t[][].push_back(i);
} if(check()==) cout<<"-1\n";
else
{
// cout<<(n/2-(x+(C-y)+z))<<endl;
// cout<<x<<endl;
// cout<<C-y<<endl;
// cout<<z<<endl; for(int i=;i<n/-(x+(C-y)+z);i++) printf("%d ",t[][][i]);
for(int i=;i<x;i++) printf("%d ",t[][][i]);
for(int i=;i<C-y;i++) printf("%d ",t[][][i]);
for(int i=;i<z;i++) printf("%d ",t[][][i]);
}
}
C - Skyscrapers - [离散化]
题意：
有个 $n$ 条横向街道，$m$ 条纵向街道，它们产生 $nm$ 个交点，每个交点上有一栋大楼高度 $h[i][j]$。
然后你对每个交点，你要把 $[1,x]$ 的整数重新赋值给这个十字上的所有大楼。使得，一条道路上任意两栋大楼之间的高度关系都与原来一致。
题解：
离散化裸题。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int h[][];
vector<int> r[],c[];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>h[i][j]; for(int i=;i<=n;i++)
{
for(int j=;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=;j<=m;j++)
{
for(int i=;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=;i<=n;i++)
{
for(int j=;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("\n");
}
}