CF1726

发布于 2022-09-07  300 次阅读


碎碎念

班会8点开始,开到10点半直接被保安赶出来可还行

有点麻,冲到寝室10点40,状态全无,开打div1+2的比赛

第5题又是数学题,已经连续好几道数学题做不出来了,麻中麻

做出4题也上分了,嘿嘿嘿unrated了,麻中麻中麻

A - Mainak and Array

给你一个数组,你有一次机会滚动一个区间任意次

最大化a[n]-a[1]

solution

三种情况,第一种是前一个-后一个

第二种是最小在1或最大在n,最大-最小

第三种是最大-a[1]或a[n]-最小

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int T,n,a[2010];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		int minn=inf,maxx=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			minn=min(a[i],minn);
			maxx=max(a[i],maxx);
		}
		int flag=1,ans=0;
		for(int i=1;i<n;i++)
		{
			if(a[i]==maxx&&a[i+1]==minn)
				flag=0;
			ans=max(ans,a[i]-a[i+1]);
		}
		if(a[1]==minn||a[n]==maxx)
			flag=0;
		if(flag)
			ans=max(ans,max(maxx-a[1],a[n]-minn));
		else ans=maxx-minn;
		printf("%d\n",ans);
	}
	return 0;
}

B - Mainak and Interesting Sequence

给你n和m,构造长度为n,和为m的数组,使得所有pi=0

pi的定义为数组中所有小于ai的数的xor和

solution

显然要求是除了最大数之外的每个数都要有偶数个

那么n为奇数时n-1个1,n为偶数时n-2个1就行了

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		if(n>m)puts("No");
		else if(n%2)
		{
			puts("Yes");
			for(int i=1;i<n;i++)
				putchar('1'),putchar(' ');
			printf("%d\n",m-n+1);
		}
		else
		{
			if(m%2)puts("No");
			else
			{
				puts("Yes");
				for(int i=3;i<=n;i++)
					putchar('1'),putchar(' ');
				printf("%d %d\n",(m-n+2)/2,(m-n+2)/2);
			}
		}
	}
	return 0;
}

C - Jatayu's Balanced Bracket Sequence

给你一个匹配的括号序列,以该序列建立一张无向图

点i,j有边的条件是区间[i,j]是匹配的括号序列

求连通块数量

solution

显然归属于同一块的最外层的括号是一个连通块

所以使用递归解决,预处理出每个括号的对应括号在哪

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200010];
char s[200010];
stack<int>q;
int solve(int sl,int sr)
{
	if(sl>=sr)return 0;
	if(sl+1==sr)return 1;
	int ret=1,u=sl;
	while(u<=sr)
	{
		ret+=solve(u+1,a[u]-1);
		u=a[u]+1;
	}
	return ret;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%s",&n,s);
		for(int i=0;i<(n<<1);i++)
		{
			if(s[i]=='(')
				q.push(i);
			else
			{
				int u=q.top();
				q.pop();
				a[u]=i,a[i]=u;
			}
		}
		printf("%d\n",solve(0,(n<<1)-1));
	}
	return 0;
}

D - Edge Split

给你一张无向连通图,至多有n+2条边

现在需要给边染成两种颜色

最小化只启用一种颜色的边的连通块数量之和

solution

只要想办法构造每条边都不构成环就行了

因为m不超过n+2,所以最小生成树之后至多有一个三元环

如果有三元环,将环中的一条边加入最小生成树并重新做一遍最小生成树

#include<bits/stdc++.h>
using namespace std;
int T,n,m,x[200010],y[200010],f[200010];
char ans[200010];
int cnt,c[10];
int find(int x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
void ins(int x)
{
	for(int i=1;i<=cnt;i++)
		if(c[i]==x)return;
	c[++cnt]=x;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			f[i]=i;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
			int fx=find(x[i]),fy=find(y[i]);
			ans[i]=(fx==fy?'1':'0');
			f[fy]=fx;
		}
		if(m==n+2)
		{
			cnt=0;memset(c,0,sizeof(c));
			int ret;
			for(int i=1;i<=m;i++)
				if(ans[i]=='1')
					ins(x[i]),ins(y[i]),ret=i;
			while(cnt==3)
			{
				for(int i=1;i<=n;i++)
					f[i]=i;
				ans[ret]='0';
				f[x[ret]]=y[ret];
				for(int i=1;i<=m;i++)if(i!=ret)
				{
					int fx=find(x[i]),fy=find(y[i]);
					ans[i]=(fx==fy?'1':'0');
					f[fy]=fx;
				}
				cnt=0,memset(c,0,sizeof(c));
				for(int i=1;i<=m;i++)
					if(ans[i]=='1')
						ins(x[i]),ins(y[i]),ret=i;
			}
		}
		for(int i=1;i<=m;i++)
			putchar(ans[i]);
		putchar('\n');
	}
	return 0;
}

E - Almost Perfect

完美排列满足abs(p[i]-a[i])<=1

其中p是排列数组,a[i]表示i在p中的位置

求出长度为n的完美排列的数量

solution

有个性质,如果将排列变为有向图,那么环的大小只能为1,2,4

大小为4的环一定是(i,i+1,j,j+1),证明有点烦,不想证了QAQ

那么可以枚举大小为4的环的数量

使n为排列长度,m为大小为4的环的数量,方案数即为C(n-2m,2m)*(2m!)/m!

大致意思是我们先取出2m对(i,i+1),再分别编号1~2m,令1与2,3与4,......,2m-1与2m配对,最后去重

然后我们只需要计算剩下n-4m个数分成大小为1或2的环的方案数即可

令f[i]表示i个数分成大小为1或2的环的方案数

更新时有i用与不用两种,不用直接继承f[i-1]

用的话先从前面选一个,有i-1种,剩下i-2个数的方案数即为f[i-2]

所以f[i]=f[i-1]+(i-1)*f[i-2]

#include<bits/stdc++.h>
#define N 300010
using namespace std;
const int MOD=998244353;
int pow(int a,int b){
	int res=1;
	while(b)
	{
		if(b&1)
			res=1ll*res*a%MOD;
		b/=2,a=1ll*a*a%MOD;
	}
	return res;
}
int T,n;
int inv[N],ji[N],ni[N];
int f[N];
int C(int x,int y){
	return 1ll*ji[x]*ni[y]%MOD*ni[x-y]%MOD;
}
int main()
{
	inv[1]=1;
	for(int i=2;i<N;i++)
		inv[i]=MOD-1ll*MOD/i*inv[MOD%i]%MOD;
	ji[0]=1,ni[0]=1;
	for(int i=1;i<N;i++)
		ji[i]=1ll*ji[i-1]*i%MOD,
		ni[i]=1ll*ni[i-1]*inv[i]%MOD;
	f[0]=1,f[1]=1;
	for(int i=2;i<N;i++)
		f[i]=(f[i-1]+1ll*f[i-2]*(i-1)%MOD)%MOD;
	scanf("%d",&T);
	while(T--)
	{
		int ans=0;
		scanf("%d",&n);
		for(int i=0;4*i<=n;i++)
			ans=(ans+1ll*C(n-2*i,2*i)*ji[2*i]%MOD*ni[i]%MOD*f[n-4*i]%MOD)%MOD;
		printf("%d\n",ans);
	}
	return 0;
}