码风丑陋，大佬勿喷
正文
C题
题目大意
给定一个只包含 o 和 - 的，长度为 的字符串 ，从中找到一个最长的子串，满足第一个或最后一个字符为 -，其他字符都为 o。
求最长子串的长度。
如果不存在这种字串，输出-1
思路分析
首先先判断字符串 中 o 和 - 两种字符是否都有。
然后我们可以发现，因为这种字串的特点是头或尾为 - ，中间是 o，所以求最长子串就是求连续 o 的长度的最大值。
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,k=0,mx=-1;
string s;
int main(){
scanf("%d",&n);cin>>s;
if(s.find("o")==-1||s.find("-")==-1){
printf("-1");
return 0;
}
for(int i=0;i<n;i++){
if(s[i]=='o')k++,mx=max(mx,k);
else k=0;
}
printf("%d",mx);
}
D题
这是一道交互题。
题目大意
给定一个 ，有一个长度为 的字符串 ，只包含 0 和 1，其中第一个位置是 0，最后一个位置是 1。 你有最多20次机会询问这个字符串某个位置的字符是什么。
最后输出 ,使得 满足 。
询问格式：？
输出格式：！
思路分析
很明显能够看出用二分做。
每次先将 设为，然后询问 位置的数，
- 如果是0，可利用 的第一个位置是 0 的特性将 设为
- 如果是1，可利用 的第一个位置是 1 的特性将 设为
最后输出 即可。
每次询问后要用 刷新缓冲区
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,x;
int f[200005];
void pd(int o){
printf("? %d",o),cout<<endl;
scanf("%d",&x);
}
int main(){
scanf("%d",&n);
int l=1,r=n,k=-1;
while(l<r){
int o=(l+r)/2;
if(f[o])break;
f[o]=1,pd(o);
if(x==0)l=o;
else r=o;
}
printf("! %d",l);
}
E题
题目大意
给定一个简单连通的无向图，有 个点， 条边,要给每个点染上黑白两色。
其中有 个点，第 个点是 ,离 最近的黑点和 的距离是 。
如果能用上述方法染色，输出 ,并输出每个点的颜色； 否则输出 。
思路分析
可以先用 算出任意两个点的距离。
因为离 最近的黑点和 的距离是 ，所以说明和 的距离小于 的点不能为黑。
最后判断一下能否用上述方法染色即可。
代码部分
#include <bits/stdc++.h>
using namespace std;
int n,m,t,x,y;
vector<int>v[2005];
int p[2005],d[2005],f[2005];
int g[2005][2005];
queue<int>q;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
scanf("%d",&t);
for(int i=1;i<=t;i++)scanf("%d%d",&p[i],&d[i]);
for(int i=1;i<=n;i++){
q.push(i);
memset(f,0,sizeof(f));
f[i]=1;
while(!q.empty()){
int t=q.front();q.pop();
for(int j=0;j<v[t].size();j++){
int w=v[t][j];
if(f[w]==0){
f[w]=1;
g[i][w]=g[i][t]+1;
q.push(w);
}
}
}
}
for(int i=1;i<=n;i++)f[i]=1;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
if(g[p[i]][j]<d[i])f[j]=0;
}
}
for(int i=1;i<=t;i++){
int ff=0;
for(int j=1;j<=n;j++){
if(f[j]==1&&g[p[i]][j]==d[i]){
ff=1;
break;
}
}
if(ff==0){
printf("No\n");
return 0;
}
}
printf("Yes\n");
for(int i=1;i<=n;i++)printf("%d",f[i]);
}
共 1 条回复
不错不错