2022杭电多校第九场题解

2022杭电多校第九场

Matryoshka Doll（DP）

题意
有$n$个套娃，第$i$个套娃的大小为$a_i$。求将这$n$个套娃分成$k$组，且每组排序后相邻两个套娃大小之差不小于$r$的方案数。

分析
看数据范围可以猜到是$n^2$的DP，用$f[i][j]$表示前$i$个数分为$j$组的方案数。下面考虑状态转移，假设当前状态为$f[i][j]$，有两种情况：(1)$a[i]$单独作为一组，从$f[i-1][j-1]$转移；(2)$a[i]$和前面某个数一组，两个数之差大于等于$r$，从$f[i-1][j]$转移。对于第二种情况，需要预处理能和$a[i]$放在一组的元素的数量。

AC代码

typedef long long ll;
const int mod=998244353;
const int N=5010;
int a[N],L[N],f[N][N]; //L[i]:a[i]左边有多少个数不能和a[i]一组

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,k,r;
		cin>>n>>k>>r;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			L[i]=0;
			for(int j=i-1;j>=1;j--)
			{
				if(abs(a[i]-a[j])<r) L[i]++;
			}
		}
		//初始化，在本题不是必须的
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				f[i][j]=0;
			}
		}
		f[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				f[i][j]=(ll)(f[i-1][j-1]+(ll)f[i-1][j]*(j-L[i])%mod)%mod;
			}
		}
		cout<<f[n][k]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

Shortest Path in GCD Graph（容斥原理）

题意
给定含有$n$个点的完全图，边权为两个点的$gcd$。有$q$次询问，对于每次询问，求两点之间的最短路的长度以及最短路的条数。

分析
如果两个点$x$和$y$的$gcd$为1，从$x$直接到$y$路径最短，最短路的长度为1，条数为1。如果$gcd$不为1，可以先让$x$走到与$x$和$y$都互质的点，再走到$y$，最短路长度不超过2，直接从$x$到$y$的路径长度大于等于2，因此最短路径长度为2。对于$x$和$y$不互质的情况，有两种走法，$x$走到和两个数互质的点，再走到$y$，或者$x$直接走到$y$，此时有$gcd(x,y)=2$。对于第二种情况特判计科，对于第一种情况，可以用容斥原理，因为两个数含有的不同质因数最多只有12个。时间复杂度$O(q\ast 2^k)$($k$是两个数含有的不同质因数的个数)。

AC代码

typedef long long ll;
const int N=1e7+10;
int vis[N],prime[N];
int a[105];
int n,q,ans,cnt,k;

void dfs(int x,int sum,int c)
{
	if(x==cnt+1)
	{
		if(c&1) ans-=n/sum;
		else ans+=n/sum;
		return ;
	}
	dfs(x+1,sum,c);
	if((ll)sum*a[x]<=n) dfs(x+1,sum*a[x],c+1);
}

void get_primes(int n)
{
	for(int i=2;i<=n;i++) {
		if(vis[i]==0) { vis[i]=i; prime[++k]=i; }
		for(int j=1;j<=k;j++) {
			if(prime[j]>vis[i]||prime[j]>n/i) break;
			vis[i*prime[j]]=prime[j];
		}
	}
}

int main()
{
	cin>>n>>q;
	get_primes(10000000);
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(__gcd(x,y)==1)
		{
			cout<<1<<" "<<1<<endl;
		}
		else
		{
			bool flag=false;
			if(__gcd(x,y)==2) flag=true;
			set<int> s;
			while(x>1)
			{
				s.insert(vis[x]);
				int z=vis[x];
				while(x%z==0) x/=z;
			}
			while(y>1)
			{
				s.insert(vis[y]);
				int z=vis[y];
				while(y%z==0) y/=z;
			}
			cnt=0;
			for(auto x:s) a[++cnt]=x;
			ans=0;
			dfs(1,1,0);
			if(flag) ans++;
			cout<<2<<" "<<ans<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

Sum Plus Product（思维）

题意
有$n$个数，每次随机取出两个数$a$和$b$，再放入$a\ast b+a+b$，直到只剩下一个数，求最终得到的数的期望。

分析
最终得到的数和选择顺序无关，直接模拟即可。时间复杂度$O(n)$。

AC代码

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		vector<ll> v(n);
		for(int i=0;i<n;i++) cin>>v[i];
		while(v.size()>=2)
		{
			ll x=v.back();
			v.pop_back();
			ll y=v.back();
			v.pop_back();
			v.push_back((x+y+x*y%mod)%mod);
		}
		cout<<v[0]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22