[Editorial] Codeforces Contest 1726

A. Mainak and Array

显然如果 /([l,r]/) 不包括两端那么就不会对答案有影响，那么直接枚举包括两端的情况即可。

/*
author : Gemini
date : September 6th, 2022
url : https://codeforces.com/contests/1726/A 
*/
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
	T sgn=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	x*=sgn;
}
int n,a[2005],ans;
void MAIN(){
	read(n);
	ans=-1e9;
	for(int i=0;i<n;i++){
		read(a[i]);
	}
	for(int i=0;i<n;i++){
		ans=max(ans,a[(i+n-1)%n]-a[i]);
	}
	for(int i=1;i<n;i++){
		ans=max(ans,a[i]-a[0]);
	}
	for(int i=0;i<n-1;i++){
		ans=max(ans,a[n-1]-a[i]);
	}
	printf("%d/n",ans);
}
int main(){
	int T;read(T);while(T--)MAIN();
	return 0;
}

B. Mainak and Interesting Sequence

注意这道题是所有小于 /(a_i/) 的值的异或和。

如果 /(m<n/) 显然没有答案，否则如果 /(n/) 是奇数，那么可以放 /(n-1/) 个 /(1/) 然后放一个 /(m-n+1/)，此时 /(p_n=0/)。

如果 /(n/) 是偶且 /(m/) 也是偶数，那么可以放 /(n-2/) 个 /(1/) 然后放两个 /(/frac{m-n}{2}+1/)。

如果 /(m/) 此时是奇数，那么仔细思考发现无解。

/*
author : Gemini
date : September 6th, 2022
url : https://codeforces.com/contests/1726/B 
*/
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
	T sgn=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	x*=sgn;
}
int n,m;
void MAIN(){
	read(n);read(m);
	if(m<n)puts("No");
	else{
		if((n&1)){
			puts("Yes");
			for(int i=1;i<n;i++)printf("1 ");
			printf("%d/n",m-n+1);
		}else if(!(m&1)){
			puts("Yes");
			for(int i=1;i<=n-2;i++)printf("1 ");
			m-=(n-2);
			printf("%d %d/n",m/2,m/2);
		}else{
			puts("No");
		}
	}
}
int main(){
	int T;read(T);while(T--)MAIN();
	return 0;
}

C. Jatayu’s Balanced Bracket Sequence

直接模拟，显然对于每一层都是一个连通块，而不同层之间是互不影响的。

/*
author : Gemini
date : September 6th, 2022
url : https://codeforces.com/contests/1726/C 
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
template<typename T>
void read(T &x){
	T sgn=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	x*=sgn;
}
int n,stk[maxn],top,R[maxn];
char s[maxn];
int solve(int l,int r){
	if(l>r)return 0;
	int ret=0;
	for(int i=l;i<=r;i=R[i]+1){
		ret+=solve(i+1,R[i]-1);
	}
	return ret+1;
}
void MAIN(){
	read(n);
	scanf("%s",s+1);
	for(int i=1;i<=n*2;i++){
		if(s[i]=='(')stk[++top]=i;
		else R[stk[top]]=i,top--;
	}
	printf("%d/n",solve(1,n*2));
}
int main(){
	int T;read(T);while(T--)MAIN();
	return 0;
}

D. Edge Split

注意，此题和构造无关，是一个纯暴力题。

注意到最后只与无用边（连同同一个连通块地边）有关。

考虑贪心地去填每一条边，如果两端不在同一连通块里就染上红色然后合并。否则染蓝色。如果蓝色存在一条边连通同一连同块，就强行再做一次，让这一条边强行染红。容易发现答案最多在这两者之间。这题就这么暴力，不需要去想每一个环的构造。

/*
author : Gemini
date : September 7th, 2022
url : https://codeforces.com/contest/1726/problem/D
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
template<typename T>
void read(T &x){
	T sgn=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	x*=sgn;
}
int n,m;
int ans[maxn],U[maxn],V[maxn],fa[maxn];
int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}
void reset(){
	for(int i=1;i<=n;i++)fa[i]=i;
}
int work(int x){
	for(int i=1;i<=m;i++)ans[i]=0;
	int ret=0;
	reset();
	for(int t=x;t<=m+x-1;t++){
		int i=t<=m?t:t-m;
		if(Find(U[i])!=Find(V[i])){
			ans[i]=1;
			fa[Find(U[i])]=Find(V[i]);
		}
	}
	reset();
	for(int t=x;t<=m+x-1;t++){
		int i=t<=m?t:t-m;
		if(ans[i])continue;
		if(Find(U[i])==Find(V[i])){
			ret=t;
			continue;
		}
		fa[Find(U[i])]=Find(V[i]);
	}
	return ret;
}
void MAIN(){
	read(n);read(m);
	for(int i=1;i<=m;i++){
		read(U[i]);read(V[i]);
	}
	int x=work(1);
	if(x)work(x);
	for(int i=1;i<=m;i++)printf("%d",ans[i]);
	puts("");
}
int main(){
	int T;
	read(T);
	while(T--)MAIN();
	return 0;
}

E. Almost Perfect

E 比 D 简单…

通过打表或者手玩可以发现只可能存在长度为 /(1,2,4/) 的环，且对于一个长度为 /(4/) 的环一定是两对连续的数。于是设 /(f_i/) 代表 /(i/) 个数只出现长度为 /(1,2/) 的环的方案数，可以dp预处理，/(f_{i}=f_{i-1}+(i-1)f_{i-2}/)。

然后枚举有多少个长度为 /(4/) 的环，然后从 /(n-1/) 个数里选出 /(2i/) 个不相邻的数，每个数代表选择 /(k/) 和 /(k+1/)。方案数是 /(/binom{n-2i}{2i}/)，然后这些数随意排列，按顺序相邻的两对组合。然后注意到这几对（4）环的位置其实是固定的，所以要除掉 /(i!/)。最后的值就是 /(/binom{n-2i}{2i}/frac{(2i)!}{i!}/)。

/*
author : Gemini
date : September 1st, 2022
url : www.nmsl.com
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5,mod=998244353;
int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int dec(int a,int b){return a<b?a-b+mod:a-b;}
int mul(int a,int b){return 1ll*a*b%mod;}
int ksm(int a,int b=mod-2){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
template<typename T>
void read(T &x){
	T sgn=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	x*=sgn;
}
int n,f[maxn],fac[maxn],ifac[maxn];
int C(int a,int b){
	if(a<0||b<0||a<b)return 0;
	return mul(fac[a],mul(ifac[b],ifac[a-b]));
}
int main(){
	int T;
	read(T);
	while(T--){
		read(n);
		f[0]=f[1]=1;
		for(int i=2;i<=n;i++)
			f[i]=add(f[i-1],mul(i-1,f[i-2]));
		int ans=0;
		fac[0]=ifac[0]=1;
		for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
		ifac[n]=ksm(fac[n]);
		for(int i=n-1;i;i--)ifac[i]=mul(ifac[i+1],i+1);
		for(int i=0;i*4<=n;i++){
			ans=add(ans,mul(f[n-i*4],mul(C(n-2*i,2*i),mul(fac[2*i],ifac[i]))));
		}
		printf("%d/n",ans);
	}
	return 0;
}

未完待续