526互联

AtCoder Regular Contest 102

发布时间 2023-09-27 19:10:28作者: Zhou_JK

C - Triangular Relationship

枚举 \(a\bmod k\) 的值，\(b\bmod k,c\bmod k\) 的值也就确定了，算下贡献就好了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int main()
{
	scanf("%d%d",&n,&k);
	long long ans=0;
	for(int a=0;a<k;a++)
	{
		int b=(-a+k)%k;
		int c=(-a+k)%k;
		if((b+c)%k!=0) continue;
		int ca=n/k+(a<=n%k),cb=n/k+(b<=n%k),cc=n/k+(c<=n%k);
		if(a==0) ca--;
		if(b==0) cb--;
		if(c==0) cc--;
		ans+=1LL*ca*cb*cc;
	}
	printf("%lld",ans);
	return 0;
}

D - All Your Paths are Different Lengths

\(n\le 20\) 容易让人想到二进制拆分。发现可以构造出 \([0,2^{n-1})\) 的方案来，具体的说，我们在 \((i,i+1)\) 中连权值为 \(0,2^{i-1}\) 的两条边。然后考虑 \(L\) 怎么做，将 \(L\) 的每一位分离开来，如果 \(L\) 的第 \(i-1\) 位为 \(0\)，在 \((i,n)\)中连一条权值为将后 \(i\) 位置为 \(0\) 后的 \(L\) 的权值。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<tuple>
using namespace std;
int L;
int n,m;
vector<tuple<int,int,int>>edge;
int main()
{
	scanf("%d",&L);
	int n=log2(L)+1;
	for(int i=1;i<n;i++)
		edge.emplace_back(i,i+1,1<<(i-1)),edge.emplace_back(i,i+1,0);
	for(int i=1;i<n;i++)
		if(L&(1<<(i-1))) edge.emplace_back(i,n,(L>>i)<<i);
	int m=edge.size();
	printf("%d %d\n",n,m);
	for(auto [u,v,w]:edge)
		printf("%d %d %d\n",u,v,w);
	return 0;
}

E - Stop. Otherwise...

对于每次询问，我们可以将数分成两个部分，一部分是选了当前这个数不能选另一个数，另一部分是选了当前这个数对于其他数没有影响。令 \(f_{i,j}\) 表示考虑前一部分的 \(i\) 种颜色填满 \(j\) 个位置的方案数，\(g_{i,j}\) 表示后一部分的 \(i\) 种颜色（每种颜色如果存在可以换成另一种）填满 \(j\) 个位置的方案数。直接转移是 \(O(n^2m)\) 的，前缀和优化一波就是 \(O(nm)\) 的。每次询问暴力合并一下就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2005;
const int MOD=998244353;
int n,m;
int f[N][N],g[N][N];
int sumf[N][N],sumg[N][N];
int pw2[N];
int main()
{
	scanf("%d%d",&m,&n);
	sumf[0][0]=f[0][0]=1;
	for(int j=1;j<=n;j++)
		sumf[0][j]=(sumf[0][j-1]+f[0][j])%MOD;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
			f[i][j]=f[i-1][j];
		for(int j=1;j<=n;j++)
			f[i][j]=(f[i][j]+sumf[i-1][j-1])%MOD;
		sumf[i][0]=f[i][0];
		for(int j=1;j<=n;j++)
			sumf[i][j]=(sumf[i][j-1]+f[i][j])%MOD;
	}
	sumg[0][0]=g[0][0]=1;
	for(int j=1;j<=n;j++)
		sumg[0][j]=(sumg[0][j-1]+g[0][j])%MOD;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
			g[i][j]=g[i-1][j];
		for(int j=1;j<=n;j++)
			g[i][j]=(g[i][j]+2LL*sumg[i-1][j-1])%MOD;
		sumg[i][0]=g[i][0];
		for(int j=1;j<=n;j++)
			sumg[i][j]=(sumg[i][j-1]+g[i][j])%MOD;
	}
	for(int i=2;i<=2*m;i++)
		if(i%2==0)
		{
			int cnt1=i>m?i-m-1:m-i+1,cnt2=i>m?m-i/2:(i-1)/2;
			int ans=0;
			ans=(ans+f[cnt1][n])%MOD;
			for(int j=1;j<=n;j++)
				ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-j])%MOD;
			ans=(ans+1LL*f[cnt1][n-1])%MOD;
			for(int j=1;j<=n-1;j++)
				ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-1-j])%MOD;
			printf("%d\n",ans);
		}
		else
		{
			int cnt1=i>m?i-m-1:m-i+1,cnt2=i>m?m-i/2:i/2;
			int ans=0;
			ans=(ans+f[cnt1][n])%MOD;
			for(int j=1;j<=n;j++)
				ans=(ans+1LL*g[cnt2][j]%MOD*f[cnt1][n-j])%MOD;
			printf("%d\n",ans);
		}
	return 0;
}

Revenge of BBuBBBlesort!

一次操作相当于交换两个距离为 \(1\) 的数，所以如果奇数位置上有偶数，偶数位置上奇数显然是不合法的。

把奇数位和偶数位分成两个排列，一次操作会使得原排列中的逆序对减少 \(3\)，分割后的排列的逆序对减少 \(1\)。

所以可以发现一个必要条件即为原序列的逆序对个数为 \(3\) 的倍数，且为奇数位和偶数位的 \(3\) 倍。

可以证明这也是充分条件。

  1. 如果交换后原序列的逆序对数减少了 \(3\)，那么这一定是一个合法的操作。
  2. 考虑对分开后的两个排列冒泡排序，每次这两个排列中的某一个逆序对数会减少 \(3\)。

则可以发现每次操作都是满足第一个条件的，所以只要满足第二个条件就是合法的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
int n;
int p[N];
struct BIT
{
	int C[N];
	void clear()
	{
		memset(C,0,sizeof(C));
		return;
	}
	int lowbit(int x)
	{
		return x&-x;
	}
	void add(int x,int y)
	{
		for(int i=x;i<=n;i+=lowbit(i))
			C[i]+=y;
		return;
	}
	int getsum(int x)
	{
		int res=0;
		for(int i=x;i>0;i-=lowbit(i))
			res+=C[i];
		return res;
	}
	int query(int l,int r)
	{
		return getsum(r)-getsum(l-1);
	}
}T;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
		if(p[i]%2!=i%2)
		{
			printf("No");
			return 0;
		}
	long long cnt=0;
	for(int i=1;i<=n;i++)
		cnt+=T.query(p[i]+1,n),T.add(p[i],1);
	T.clear();
	long long cnt1=0;
	for(int i=1;i<=n;i+=2)
		cnt1+=T.query(p[i]+1,n),T.add(p[i],1);
	T.clear();
	long long cnt2=0;
	for(int i=2;i<=n;i+=2)
		cnt2+=T.query(p[i]+1,n),T.add(p[i],1);
	if(cnt%3==0&&3*(cnt1+cnt2)==cnt) printf("Yes");
	else printf("No");
	return 0;
}