神仙的 ARC。
A.Non-Adjacent Flip
题目分析：
就是一个分类讨论，主要就是讨论一下只有 \(2\) 个 \(1\) 的情况。
自己手模一下应该很好理解。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
vector<int> v;
char s[N];
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
scanf("%s",s+1);
for(int i=1; i<=n; i++) if(s[i] == '1') v.push_back(i);
int m = v.size();
if(m & 1) printf("-1\n");
else if(m == 2 && v[0] + 1 == v[1]){
if(n <= 3) printf("-1\n");
else if(n >= 5) printf("2\n");
else{
if(s[1] == '1' || s[4] == '1') printf("2\n");
else printf("3\n");
}
}
else printf("%d\n",m/2);
v.clear();
}
return 0;
}
B.Mex on Blackboard
题目分析：
我们其实可以考虑从小到大依次决定每一个数选择多少，也就是考虑完了前 \(i\) 个数选的情况再考虑 \(i+1\) 这个数，这样显然是没影响的。
这个其实就启发我们直接枚举选择的最大的数是多少，假设为 \(i\) 且为了使得序列存在 \([1,i]\) 还剩余 \(k\) 次操作，那么答案其实就是：
但是会出现一个问题，假设我们现在选择的数为 \(x\) 但是序列中原本就存在 \(x+1\)，这样就会算重最大为 \(x\) 的情况。但是这个也不用容斥，出现这种情况直接跳过 \(x\) 就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX = 1e6+5;
const int MOD = 998244353;
int cnt[MX*2],a[MX],fac[MX*2+5],inv[MX*2+5];
int mod(int x){
return x % MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
int binom(int n,int m){
return mod(fac[n] * mod(inv[n - m] * inv[m]));
}
signed main(){
int n,k;scanf("%lld%lld",&n,&k);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),cnt[a[i]]++;
fac[0] = 1;
for(int i=1; i<=MX*2; i++) fac[i] = mod(fac[i-1] * i);
inv[MX*2] = power(fac[MX*2],MOD-2);
for(int i=MX*2-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i+1));
int ans = 0;
for(int i=0; i<=MX; i++){
if(!cnt[i]) k--;
if(k <= 0){
ans++;
break;
}
while(cnt[i+1]) i++;
ans = mod(ans + binom(k+i,i));
}
printf("%lld\n",ans);
return 0;
}
C.Tree and LCS
题目分析：
又是一道我不会的神仙题呢。
考虑对于任意一个排列其最小的权值都至少为 \(1\)，因为我们可以选择路径 \((i,P_k)\) 其中满足 \(P_k = i\)。
我们就是考虑每次选择两个一度点 \(x,y\) 然后令 \(P_x = y,P_y = x\)，并将 \(x,y\) 从图上删去，最后如果有剩下的点就直接令剩下的点 \(P_i = i\)。
可以证明的是这样的操作对于路径 \((x,y)\) 一定是不劣的，而对于包含 \(x,y\) 的路径，想使得 \(x,y\) 产生大于 \(1\) 的贡献也是不可能的，而 \(x,y\) 只有可能是相互配对才可能产生大于 \(1\) 的贡献，而相互配对也不行，所以只要包含 \(x,y\) 那么 \(x,y\) 就一定不会产生大于 \(1\) 的贡献。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
struct edge{
int nxt,to;
edge(){}
edge(int _nxt,int _to){
nxt = _nxt,to = _to;
}
}e[2 * N];
int head[N],deg[N],cnt,ans[N];
void add_edge(int from,int to){
e[++cnt] = edge(head[from],to);
head[from] = cnt;
}
int main(){
int n;scanf("%d",&n);
for(int i=1; i<n; i++){
int from,to;scanf("%d%d",&from,&to);
add_edge(from,to);add_edge(to,from);
deg[from]++;deg[to]++;
}
queue<int> q;
for(int i=1; i<=n; i++){
if(deg[i] == 1) q.push(i);
}
while(q.size() > 1){
int x = q.front();q.pop();
int y = q.front();q.pop();
ans[x] = y;ans[y] = x;
for(int i = head[x]; i; i = e[i].nxt){
int to = e[i].to;
deg[to]--;
if(deg[to] == 1) q.push(to);
}
for(int i = head[y]; i; i = e[i].nxt){
int to = e[i].to;
deg[to]--;
if(deg[to] == 1) q.push(to);
}
}
for(int i=1; i<=n; i++) if(!ans[i]) ans[i] = i;
for(int i=1; i<=n; i++) printf("%d ",ans[i]);
return 0;
}