A
题意： 问你最长的 111222这样格式的子串有多长
题解：1112222211212 连续的数字转化为数量 352111 求一下相邻两个数字中小的那一个 最大是多少
#include <bits/stdc++.h>
#define maxn 100000+5
using namespace std;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
vector<int>v;
int flag=a[0],tmp=1;
for(int i=1;i<n;i++){
if(a[i]==flag){
tmp++;
}else {
v.push_back(tmp);
if(flag==1)flag=2;
else flag=1;
tmp=1;
}
if(i==n-1)v.push_back(tmp);
}
int ans=0;
for(int i=0;i<v.size()-1;i++){
ans=max(min(v[i],v[i+1]),ans);
}
cout<<ans*2<<endl;
//while(1)getchar();
} B
题意 第一排表示每个人能不能当小丑 第二排表示能不能演杂技
要求 将这些人分成两半 第一场表演当小丑的人数等于第二场演杂技的人数
输出哪些人 在第一场表演
题解：不太好想 定义c00 c10 c11 c01 为每个状态的人数
然后a00 a10 a01 a11为第一场 b00 b10 b01 b11为第二场表演的各个状态的人数
枚举 a10 a11 然后就能求出其他所有的状态 判断一下其他所有的状态是否合法
#include <bits/stdc++.h>
#define maxn 200000+5
using namespace std;
int main(){
int c11=0,c10=0,c01=0,c00=0;
string a,b;int n;
cin>>n;
cin>>a>>b;
for(int i=0;i<n;i++){
if(a[i]=='1'&&b[i]=='1')c11++;
if(a[i]=='0'&&b[i]=='1')c01++;
if(a[i]=='1'&&b[i]=='0')c10++;
if(a[i]=='0'&&b[i]=='0')c00++;
}
int a00,a01,a10,a11,b00,b01,b10,b11;
for(a10=0;a10<=c10;a10++){
for(a11=0;a11<=c11;a11++){
b10=c10-a10;
b11=c11-a11;
if(b11<0||b10<0)continue;
b01=a10+a11-b11;
if(b01<0||b01>c01)continue;
a01=c01-b01;
a00=n/2-a01-a10-a11;
b00=c00-a00;
if(a01<0||a01>c01||a00<0||a00>c00||b00+b10+b11+b01!=n/2||b00<0||b00>c00)continue;
for(int i=0;i<n;i++)
{
if(a00&&a[i]=='0'&&b[i]=='0')printf("%d ",i+1),a00--;
if(a01&&a[i]=='0'&&b[i]=='1')printf("%d ",i+1),a01--;
if(a10&&a[i]=='1'&&b[i]=='0')printf("%d ",i+1),a10--;
if(a11&&a[i]=='1'&&b[i]=='1')printf("%d ",i+1),a11--;
}
//while(1)getchar();
return 0;
}
}
printf("-1");
//while(1)getchar();
return 0;
} C
题意 这个题的题意真的是。。。 对于每个路口的交点来说 ，竖排可以按照高低安排1-x 横排也是 （高低顺序不能变）
然后问你每个交点 对应的十字 最高的x是多大
输出矩阵
题解:将每个横排排序去重，竖排排序去重
然后找一下每个交点的高度 在横排里最高排大 竖排里最高排多大
和就是答案
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000+5
int a[maxn][maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
}
vector<int>r[maxn],c[maxn];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
r[i].push_back(a[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=0;j<m;j++){
for(int i=0;i<n;i++){
c[j].push_back(a[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=0;i<n;i++){
for(int j=0;j<m;j++){
int flag1=lower_bound(r[i].begin(),r[i].end(),a[i][j])-r[i].begin();
int flag2=lower_bound(c[j].begin(),c[j].end(),a[i][j])-c[j].begin();
int flag3=r[i].end()-lower_bound(r[i].begin(),r[i].end(),a[i][j]);
int flag4=c[j].end()-lower_bound(c[j].begin(),c[j].end(),a[i][j]);
printf("%d ",max(flag1,flag2)+max(flag3,flag4));
}
printf("\n");
}
//while(1)getchar();
return 0;
} D
题意 将第一个串重新排序 使得第二个串 在新生成的序列中出现次数最多
题解：注意是出现次数最多 所以出现的每一个子串是可以重叠的
不重叠直接输出就行了 一看到重叠我就想起了kmp
然后这个题就是kmp 求出next数组 找到最后一个字符输出完后应该跳到哪个字符继续输出
不难写，调试时间花费比较多
#include <bits/stdc++.h>
#define maxn 5000000+5
using namespace std;
int Next[maxn];
char t[maxn],s[maxn];
void getNext(char * p, int * Next)
{
Next[0] = -1;
int i = 0, j = -1;
int ns=strlen(p);
while (i < ns)
{
if (j == -1 || p[i] == p[j])
{
++i;
++j;
Next[i] = j;
}
else
j = Next[j];
}
}
int main(){
scanf("%s%s",t,s);
getNext(s,Next);
int n=strlen(t),t0=0,t1=0;
for(int i=0;i<n;i++){
if(t[i]=='0')t0++;
else t1++;
}
int ns=strlen(s);
/*for(int i=0;i<=ns;i++)
cout<<Next[i];*/
int flag=0;
//cout<<endl;
while(t0>0&&t1>0){
if(flag==ns)flag=Next[flag];
if(s[flag]=='1'){
printf("1");
t1--;
}else {
printf("0");
t0--;
}
flag++;
}
while(t0>0)printf("0"),t0--;
while(t1>0)printf("1"),t1--;
//while(1)getchar();
return 0;
}
京公网安备 11010502036488号