Acwing161周赛题解

A

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int gcd(int a, int b) {
   
	return b ? gcd(b, a % b) : a;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int a, b;
	cin >> a >> b;
	int res = gcd(a, b);
	if (res == 1) cout << "YES" << "\n";
	else cout << "NO" << "\n";

	return 0;
}

B

朴素做法时间复杂度$O(n^2\log n)$, 会超时

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N], f[N];

int gcd(int a, int b) {
   
	return b ? gcd(b, a % b) : a;
}

bool check(int a, int b) {
   
	return gcd(a, b) == 1;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];

	int res = 1;
	for (int i = 1; i <= n; ++i) {
   
		f[i] = 1;
		for (int j = 1; j < i; ++j) {
   
			if (!check(w[j], w[i])) f[i] = max(f[i], f[j] + 1);
		}
		res = max(res, f[i]);
	}

	cout << res << "\n";
	return 0;
}

需要优化, 如何找到$a_i$前面与$a_i$不互质的数的位置, $a_i$质因数的个数是$\log a_i$, 与$a_i$不互质的数的位置一定至少与$a_i$有一个公共的质因子

原来是暴力枚举所有非互质数, 现在可将整个集合进行划分, 划分成与$a_i$有相同的质因子是$p_1$的数, 是$p_2$的数…

$g[i]$代表所有包含质因子$i$的$f[j]$的最大值, 这样处理后状态转移方程转化为
$f[i]=\max (g[2],g[3],...,g[k])+1$, 求$f[i]$后更新$g$

时间的复杂度$O(n\sqrt{n})$, 时间瓶颈在试除法分解质因数, 或者使用筛法优化, 时间复杂度$O(n\log n)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N], f[N], primes[N], g[N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];
	
	// 筛法求每个数的最小质因子
	for (int i = 2; i < N; ++i) {
   
		for (int j = i; j < N; j += i) {
   
			if (!primes[j]) primes[j] = i;
		}
	}

	int res = 0;
	for (int i = 1; i <= n; ++i) {
   
		f[i] = 1;
		
		// 枚举每个数的质因子
		for (int j = w[i]; j > 1; j /= primes[j]) {
   
			f[i] = max(f[i], g[primes[j]] + 1);
		}   
		
		// 更新每个质因子对应的最大的f的值
		for (int j = w[i]; j > 1; j /= primes[j]) {
   
			g[primes[j]] = max(g[primes[j]], f[i]);
		}

		res = max(res, f[i]);
	}

	cout << res << "\n";

	return 0;
}

注意$j\ne 0$, 因为$0$没有最小质因子

C

将问题集合进行分类, 将集合按照第$1$个不能上车的奶牛进行划分, 如果所有奶牛都能上车进行特判

将集合继续进行划分, 前面有$j$头牛, 后面有$n-j-1$头牛, 在对重量进行划分
$f[i][j]$表示选择了$j$头牛并且总重量是$k$的方案数, 发生的概率就是$\frac{f[i][j]}{n!}$, 因为前后奶牛的顺序可以任意调整, 因此概率为

$$\frac{f[i][j]\times j!\times (n-j-1)!}{n!}$$

如何计算$f[j][k]$?
从$n$头牛中选择$j$头牛并且总量为$k$的方案数, 是二维费用的背包问题

因此总的期望就是
$$\sum _{i=1}^n\frac{f[j,k]\times j!\times (n-i-1)!}{n!}j$$

将式子进行变形
$$\sum _{i=1}^n\frac{j\times f[j][k]}{n}\frac{j!\times (n-j-1)!}{(n-1)!}$$

发现后面的式子是组合数倒数
$$\sum _{i=1}^n\frac{j\times f[j][k]}{n}\frac{1}{C_{n-1}^j}$$
时间复杂度$O(n^4)$

在枚举$k$时需要考虑加入当前$a_c$后超重因此$a_c+k>m$并且$k\le m$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 55, M = N * N;

int n, m;
int w[N];
// f[i][j]表示从n头牛中选择i头牛并且总重量为j的所有方案
LL f[N][M];

// 计算组合数
LL C(int a, int b) {
   
	if (a < b) return 0;
	LL res = 1;
	for (int i = a, j = 1; j <= b; ++j, --i) {
   
		res = res * i / j;
	}

	return res;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; ++i){
   
		cin >> w[i];
		sum += w[i];
	}
	cin >> m;

	// 汽车能装在全部的奶牛
	if (sum <= m) {
   
		cout << n << "\n";
		return 0;
	}

	double res = 0;
	// 枚举哪一头牛是超重的牛
	for (int c = 1; c <= n; ++c) {
   

		memset(f, 0, sizeof f);
		f[0][0] = 1;
		for (int i = 1; i <= n; ++i) {
   
			// 因为第c头奶牛超重
			if (i == c) continue;
			for (int j = i; j; --j) {
   
				for (int k = m; k >= w[i]; --k) {
   
					f[j][k] += f[j - 1][k - w[i]];
				}
			}
		}

		// 因为已经选择了一个奶牛 因此剩余奶牛数量是n - 1
		for (int j = 0; j < n; ++j) {
   
			for (int k = max(m - w[c] + 1, 0); k <= m; ++k) {
   
				double val = (double) f[j][k] / C(n - 1, j) / n * j;
				res += val;
			}
		}
	}

	cout << res << "\n";
	return 0;
}