这么早的CF已经很少见了。
CF1138A
是的这题调了我半个小时。
别说了，丢人。
具体来说就是我写代码的时候默认nw总是较小的那个，但事实上有时候a[i]也有可能是较小的那个。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a[1000005],b[1000005];
int n;
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
}
a[1]=1;
int nw=0,ans=0;
for(int i=2;i<=n;++i){
if(b[i]!=b[i-1]){
nw=a[i-1];
a[i]=1;
ans=max(ans,min(nw,a[i]));
}else{
a[i]=a[i-1]+1;
ans=max(ans,min(nw,a[i]));
}
}
printf("%d\n",ans*2);
}
int main(){
init();
return 0;
}
CF1138B
这题我是松过去的。
一开始没看数据范围还有O(n)的幻想，看了以后就开始YY平方级的做法，但是编了半天没编出来。
最后决定破釜沉舟，写一个复杂度三方不满的暴力，居然一发入魂过了。Amazing！
一开始觉得复杂度是十亿左右，现在仔细算一算应该是一亿出头，加上常数小卡过去其实确实是有可能的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n;
char a[5005],b[5005];
int val[5005];
int mp[5005][5005];
bool vis[5005];
inline void prnt(int i,int j,int k,int l){
int i1=0,j1=0,k1=0,l1=0;
for(int t=1;t<=n;++t){
if(val[t]==0&&i1<i){
++i1;
printf("%d ",t);
}
if(val[t]==1&&k1<k){
++k1;
printf("%d ",t);
}
if(val[t]==2&&j1<j){
++j1;
printf("%d ",t);
}
if(val[t]==3&&l1<l){
++l1;
printf("%d ",t);
}
}
}
void init(){
scanf("%d",&n);
cin>>a+1>>b+1;
int q=0,w=0,e=0,r=0;
for(int i=1;i<=n;++i){
if(a[i]=='0'&&b[i]=='0'){
++q;
val[i]=0;
}
if(a[i]=='1'&&b[i]=='0'){
++w;
val[i]=1;
}
if(a[i]=='0'&&b[i]=='1'){
++e;
val[i]=2;
}
if(a[i]=='1'&&b[i]=='1'){
++r;
val[i]=3;
}
}
// fst->w,scn->e
for(int i=0;i<=min(n/2,q);++i){
for(int j=0;j<=min(n/2-i,e);++j){
for(int k=0;k<=min(n/2-i-j,w);++k){
int l=n/2-i-j-k;
if(l>r){
continue;
}
if(i+k==e-j+q-i&&j+l==w-k+r-l){
prnt(q-i,e-j,w-k,r-l);
return;
}
}
}
}
puts("-1");
return;
}
int main(){
init();
return 0;
}
CF1138C
看到这题首先就可以想到离散化。
具体来说就是我们对于每一行和每一列都各自离散化，然后计算出每个格子在这一行/列的相对大小。
由于大小关系不能改变，所以这个相对大小必须取较大值，这样才能留下足够的空间。
同样的，比每个格子大的数量也要取较大值，也是为了留下足够的空间。
然后就可以了。
不过我离散化写丑了，丢人。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,m;
int a[1005][1005],a1[1005][1005],a2[1005][1005];
int b[1005];
int mx1[1005],mx2[1005];
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
}
}
int nw;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
b[j]=a[i][j];
}
sort(b+1,b+1+m);
mx1[i]=unique(b+1,b+m+1)-b-1;
for(int j=1;j<=m;++j){
a1[i][j]=lower_bound(b+1,b+mx1[i]+1,a[i][j])-b;
}
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
b[j]=a[j][i];
}
sort(b+1,b+1+n);
mx2[i]=unique(b+1,b+n+1)-b-1;
for(int j=1;j<=n;++j){
a2[j][i]=lower_bound(b+1,b+mx2[i]+1,a[j][i])-b;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
printf("%d ",max(a1[i][j],a2[i][j])+max(mx1[i]-a1[i][j],mx2[j]-a2[i][j]));
}
puts("");
}
}
int main(){
init();
return 0;
}
CF1138D
第一个想法是暴力循环，但是那样子好像会WA9。
仔细考虑一下发现需要处理出最大非本身Border，然后分两段乱搞。
当然是要上一个KMP了。
但是我乱搞还是写丑了，WA在几十个点。现在想来应该是输出剩余的东西的时候写得丑了。最后参考了小粉兔的才通过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char a[500005],b[500005];
int x,y,n,m;
int nxt[500005];
void init(){
cin>>a+1;
cin>>b+1;
n=strlen(a+1);
m=strlen(b+1);
for(int i=1;i<=n;++i){
if(a[i]=='1'){
++x;
}else{
++y;
}
}
int l1;
int j=0;
for(int i=2;i<=m;i++){
while(j&&(b[i]!=b[j+1])){
j=nxt[j];
}
if(b[j+1]==b[i]){
j++;
}
nxt[i]=j;
}
l1=nxt[m];
j=0;
for(int i=1;i<=n;++i){
if(b[j+1]=='1'&&x){
putchar('1');
--x;++j;
if(j==m){
j=l1;
}
}else if(b[j+1]=='0'&&y){
putchar('0');
--y;++j;
if(j==m){
j=l1;
}
}else{
putchar(b[j+1]=='0'?'1':'0');
}
}
}
int main(){
init();
return 0;
}