码风丑陋，大佬勿喷
正文
C题
题目大意
给定 个互不相同的字符串，问是否能重新将这些字符串排序，使得任意两个相邻的字符串，都可通过修改一个字符串的一个字符，使其变成另一个字符串。
思路分析
考虑到数据很小，可以直接爆搜，全排列枚举顺序，每次结束时判断所有相邻字符串是否只有一个位置的字符不相同。是就直接输出 ，结束程序。否则最后输出 。
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,m;
string h[10];
int f[10],ff[10];
void dfs(int o){
if(o==m+1){
for(int i=1;i<m;i++){
int s=0,t=ff[i],t1=ff[i+1];
for(int j=0;j<n;j++){
if(h[t][j]!=h[t1][j])s++;
}
if(s!=1)return;
}
printf("Yes");
exit(0);
}
for(int i=1;i<=m;i++){
if(f[i]==0){
f[i]=1,ff[o]=i;
dfs(o+1);
f[i]=0;
}
}
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)cin>>h[i];
dfs(1);
printf("No");
}
D题
题目大意
给定两个数组 和 ，长度分别是 和 。现在要从两数组中各选一个数，使得两数之差不超过 。求两数之和的最大值。如果不存在这两个数，输出 。
思路分析
扫一遍 数组,在 数组中二分可能的最大的数。记录 数组当前值加上 数组可能的最大的数的最大值，输出。没有就输出 。
代码部分
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,d,mx=-1;
int a[200005],b[200005];
signed main(){
scanf("%lld%lld%lld",&n,&m,&d);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
sort(a+1,a+n+1);sort(b+1,b+m+1);
unique(a+1,a+n+1),unique(b+1,b+m+1);
for(int i=1;i<=n;i++){
int k=lower_bound(b+1,b+m+1,a[i]+d+1)-b-1;
if(abs(a[i]-b[k])>d){
k--;
if(abs(a[i]-b[k])>d)continue;
}
mx=max(mx,a[i]+b[k]);
}
printf("%lld",mx);
}
E题
题目大意
有一个 个点的无向图，一开始没有边。 给你 个查询，由两种形式给出：
- 1 将 和 两个点连边
- 2 删除和 相连的所有边
每个查询后输出没有被任何边连接的顶点数。
思路分析
使用 记录连接情况，数组记录每个点连接到的点数。 因为一开始无边，所以将答案设为n。
-
执行 1 操作时，若原来 点不与任何点相连，则答案减一； 点同理。因为现在 和 之间会连一条边。 然后连边，并将 和 连接到的点的个数各加1
-
执行 2 操作时，枚举 连接到的每一个点，将它们之间的边删掉，并把枚举到的这个点连接到的点数减一。如果这时这个点不与任何点相连，答案加一，表明不与任何点相连的点数多了一个。最后如果点 删掉所有边之前连接到的点数不为 0，答案就加一，因为点 连接到的点数现在为 0 了。
每次操作结束后，输出答案即可。
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,q,o,u,v,s=0;
set<int>st[300005];
int f[300005];
int main(){
scanf("%d%d",&n,&q);s=n;
while(q--){
scanf("%d",&o);
if(o==1){
scanf("%d%d",&u,&v);
if(f[v]==0)s--;
if(f[u]==0)s--;
st[u].insert(v);
st[v].insert(u);
f[v]++,f[u]++;
}
else{
scanf("%d",&v);
set<int>::iterator it=st[v].begin();
for(;it!=st[v].end();it++){
int t=*it;
st[t].erase(v);
f[t]--;
if(f[t]==0)s++;
}
st[v].clear();
if(f[v]>0)f[v]=0,s++;
}
printf("%d\n",s);
}
}