模拟赛没有判 \(n=1\),喜提 \(0\) 分。感谢每个 subtask 都放 \(n=1\) 的善良出题人。
看到题感觉 A 的操作好像比较弱小,唯一的用处似乎只能用来排除 B 在哪些位置,那这样就有一个暴力了,直接记录当前还有哪些点上可能有 B,然后直接跑 bfs,就可以通过第一档分了。
看到第二档分似乎比较简单,然后拿暴力跑了一下,发现一种合法方案是 \(\{2,3,4...n-1,n-1,n-2,n-3...2\}\) ,相当于正反遍历了两次,直接写了就能拿到第二档分了。
考虑这样为什么是对的。由于 B 可以反复横跳,所以考虑把图黑白染色,那么模拟一下过程不难发现一次遍历可以把同一种颜色全部排除掉,然后走两次就是正确的。类似的可以推广到树上,把直径找出来沿着直径走,盘一下中间有没有挂长度大于 \(2\) 的支链,就构造完了,感觉操作次数很少,认为这是操作次数下界了。
感觉会写暴力的话规律还是比较好找的。
#include <bits/stdc++.h>
#define sz(x) (int)((x).size())
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 1010;
int n, m, tag[N];
vector<int> G[N], e[N];
int fa[N], d[N];
void dfs(int u, int f) {
d[u] = d[fa[u] = f] + 1;
for(int v : G[u])
if(v ^ f) dfs(v, u);
}
int main() {
read(n), read(m);
if(n == 1) {
puts("YES\n1\n1\n");
return 0;
} if(n == 2) {
puts("YES\n2\n1 1\n");
return 0;
} if(m >= n) {
puts("NO");
return 0;
}
for(int i = 1, u, v; i <= m; ++i)
read(u), read(v),
G[u].emplace_back(v), G[v].emplace_back(u);
dfs(1, 0);
int x = 1;
for(int i = 1; i <= n; ++i)
if(d[i] > d[x]) x = i;
dfs(x, 0);
int y = 1;
for(int i = 1; i <= n; ++i)
if(d[i] > d[y]) y = i;
for(int i = 1; i <= n; ++i)
if(sz(G[i]) > 1) {
for(int j : G[i])
e[j].emplace_back(i);
}
int t = y;
while(t != x) tag[t] = 1, t = fa[t];
vector<int> ans;
t = y;
while(t != x) {
while(sz(G[t]) == 1) t = fa[t];
ans.emplace_back(t);
for(int v : e[t]) {
if(tag[v]) continue;
if(sz(e[v]) > 1) {
puts("NO");
return 0;
}
ans.emplace_back(v);
ans.emplace_back(t);
}
t = fa[t];
}
printf("YES\n%d\n",sz(ans) * 2);
for(int x : ans)
printf("%d ",x);
reverse(ans.begin(), ans.end());
for(int x : ans)
printf("%d ",x);
return 0;
}
标签:ch,return,fa,int,Newspapers,back,CEOI2021,ans
From: https://www.cnblogs.com/DCH233/p/17364061.html