“蔚来杯”2022牛客暑期多校训练营4()

比赛链接:

https://ac.nowcoder.com/acm/contest/33189

A.Task Computing

题意:

从 \(n\) 个服务器中选择 \(m\) 个提供服务,每个服务器有两个属性 \(w\) 和 \(p\),选择的服务器提供的总权值为 \(\sum_{i = 1}^{m} w_{a_i} \prod_{j = 0}^{i – 1} p_{a_i}\),求出总权值最大为多少。

思路:

首先要对服务器进行排序,现在有两个服务器 \(i\) 和 \(j\),假设最后的排序为 \(i < j\)。
那么满足的条件为 \(w_i + w_j * p_i < w_j + w_i * p_j\)。
因为题目给定的是 \(q\)(\(p = \frac{p}{10000}\)),对公式进行移项 \(w_i * (1 – p_j) < w_j * (1 – p_i)\)。
排完序之后,枚举每个服务器进行转移,定义 \(dp[i][j]\) 表示前 \(i\) 个服务器选择了 \(j\) 个服务器能获得的最大权值。
类似于 01 背包,可以压缩一下,变成 \(dp[j]\),然后转移即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, m;
	cin >> n >> m;
	vector < array<LL, 2> > a(n);
	for (int i = 0; i < n; i ++ )
		cin >> a[i][0];
	for (int i = 0; i < n; i ++ )
		cin >> a[i][1];
	sort(a.begin(), a.end(), [&](auto x, auto y){
		return x[0] * (10000 - y[1]) < y[0] * (10000 - x[1]);
	});
	vector <double> dp(m + 1);
	for (int i = 0; i < n; i ++ ){
		for (int j = m; j >= 1; j -- ){
			dp[j] = max(dp[j], dp[j - 1] * 0.0001 * a[i][1] + a[i][0]);
		}
	}
	cout << fixed << setprecision(15) << dp[m] << "\n";
	return 0;
}

D.Jobs (Easy Version)

题意:

有 \(n\) 家公司,第 \(i\) 家公司有 \(m_i\) 个工作,当一个人的 IQ,EQ,AQ 都满足工作的要求时,他才能胜任这份工作,当一个人能胜任公司中任何一份工作,他就会被公司录用,现在有 \(q\) 次询问,每次询问给出一个人的三商,问他能被几家公司录用。

思路:

定义 \(dp[i][a][b]\) 表示第 \(i\) 家公司录取 IQ 为 \(a\),EQ 为 \(b\) 的人需要的 \(AQ\) 最低为多少,容易得到转移方程。
题目需要的答案可以通过递推优化一下,秦九韶算法。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, q;
	cin >> n >> q;
	vector dp(n, vector(401, vector<LL>(401, 401)));
	for (int i = 0; i < n; i ++ ){
		LL m;
		cin >> m;
		for (int j = 0; j < m; j ++ ){
			LL a, b, c;
			cin >> a >> b >> c;
			dp[i][a][b] = min(dp[i][a][b], c);
		}
		for (int a = 1; a <= 400; a ++ )
			for (int b = 1; b <= 400; b ++ ){
				dp[i][a][b] = min(dp[i][a][b], dp[i][a - 1][b]);
				dp[i][a][b] = min(dp[i][a][b], dp[i][a][b - 1]);
			}
	}
	LL seed;
	cin >> seed;
	mt19937 rng(seed);
	uniform_int_distribution<> u(1, 400);
	auto solve = [&](LL a, LL b, LL c){
		LL ans = 0;
		for (int i = 0; i < n; i ++ )
			ans += (c >= dp[i][a][b]);
		return ans;
	};
	LL lastans = 0, ans = 0;
	for (int i = 1; i <= q; i ++ ){
		LL IQ = (u(rng) ^ lastans) % 400 + 1;
		LL EQ = (u(rng) ^ lastans) % 400 + 1;
		LL AQ = (u(rng) ^ lastans) % 400 + 1;
		lastans = solve(IQ, EQ, AQ);
		ans = (ans * seed + lastans) % mod;
	}
	cout << ans << "\n";
	return 0;
}

H.Wall Builder II

题意:

有长为 1 的矩形 \(n\) 个,长为 2 的矩形 \(n – 1\) 个,…,长为 \(n\) 的矩形 1 个,所有矩形的高度为 1,将这些矩形拼成一个大矩形,求出拼成的大矩形的周长的最小值,并输出每个矩形放置的位置(左下角的坐标和右上角的坐标)。放置矩形的时候是将长的那条边对应 \(x\) 轴放置,不能旋转矩形再放置。

思路:

因为矩形的总面积确定了,所以可以枚举可能的长和高,然后每次判断一下当前的矩形能不能拼出来。
通过 \(multiset\) 去存每个矩形,删除的时候需要删除指定位置,不能删某个值(\(multiset\) 删除值会将集合中所有等于这个值的元素都删除)。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
	LL n;
	cin >> n;
	LL area = 0;
	for (int i = 1; i <= n; i ++ )
		area += i * (n - i + 1);
	LL ans = 1e9;
	vector < vector<LL> > point(n * (n + 1) / 2);
	auto check = [&](LL w, LL h){
		vector < vector<LL> > t(n * (n + 1) / 2);
		multiset <LL> seg;
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= n - i + 1; j ++ )
				seg.insert(i);
		LL cnt = 0;
		for (int i = 0; i < h; i ++ ){
			LL tw = w;
			while(tw > 0){
				auto it = seg.lower_bound(tw);
				LL len = *it;
				LL mx = *(prev(seg.end()));
				if (len > mx){
					len = mx;
					it = prev(seg.end());
				}
				if (len > tw) return;
				seg.erase(it);
				t[cnt].push_back(w - tw);
				t[cnt].push_back(i);
				t[cnt].push_back(w - tw + len);
				t[cnt].push_back(i + 1);
				cnt ++ ;
				tw -= len;
			}
		}
		ans = min(ans, 2 * (w + h));
		for (int i = 0; i < n * (n + 1) / 2; i ++ )
			point[i] = t[i];
	};
	for (int w = 1; w <= area / w; w ++ ){
		if (area % w == 0){
			check(w, area / w);
			check(area / w, w);
		}
	}
	cout << ans << "\n";
	for (int i = 0; i < n * (n + 1) / 2; i ++ )
		for (int j = 0; j < 4; j ++ )
			cout << point[i][j] << " \n"[j == 3];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

K.NIO’s Sword

题意:

有一把初始攻击力为 \(A(A = 0)\) 的剑,需要依次杀死 \(n\) 个敌人(从 1 到 \(n\)),当剑的攻击力模 \(n\) 与 \(i\) 同余的时候,可以杀死第 \(i\) 个敌人。可以升级剑,选择一个值 \(x(0 <= x <= 9)\),让 \(A = A * 10 + x\),问最少需要升级多少次才能杀死 1 到 \(n\) 的所有敌人。

思路:

设 \(k\) 为升级的次数,那么可以得到 \((i – 1) * 10^k + x \equiv i (mod n)\),\(x\) 为一个小于 \(10^k\) 的数。所以 \(x = i – (i – 1) * 10^k\),因为数据限制,所以枚举 \(x\) 是否存在即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL fac[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n;
	cin >> n;
	if (n == 1){
		cout << "0\n";
	}
	else{
		LL ans = 0;
		for (int i = 1; i <= n; i ++ ){
			for (int j = 1; j <= 6; j ++ ){
				LL x = (i - fac[j] * (i - 1) % n + n) % n;
				if (x < fac[j]){
					ans += j;
					break;
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

N.Particle Arts

题意:

有 \(n\) 个粒子,每个粒子有一个值 \(a_i\),两两之间会不断相互碰撞,\(a_i\) 和 \(a_j\) 碰撞后,\(a_i = a_i and a_j\),\(a_j = a_i or a_j\),问最后稳定之后的粒子的方差收敛至多少。

思路:

假设碰撞后,左边的值为 \(or\) 的值,那么最后稳定状态下,每一位上的 1 肯定都挤在左边,容易得到稳定之后的序列。
因为直接求会溢出,根据 \(D(x) = E(x^2) – E(x) ^ 2\) 求解即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n;
	cin >> n;
	vector <LL> a(n), bit(20);
	for (int i = 0; i < n; i ++ ){
		cin >> a[i];
		LL cnt = 0;
		while(a[i]){
			bit[cnt ++ ] += (a[i] & 1);
			a[i] >>= 1;
		}
	}
	LL sum1 = 0, sum2 = 0;
	for (int i = 0; i < n; i ++ ){
		for (int j = 15; j >= 0; j -- ){
			a[i] <<= 1;
			if (bit[j]){
				a[i] ++ ;
				bit[j] -- ;
			}
		}
		sum1 += a[i];
		sum2 += a[i] * a[i];
	}
	LL p = sum2 * n - sum1 * sum1;
	LL q = n * n;
	LL g = gcd(p, q);
	cout << p / g << "/" << q / g << "\n";
	return 0;
}
————————

比赛链接:

https://ac.nowcoder.com/acm/contest/33189

A.Task Computing

题意:

从 \(n\) 个服务器中选择 \(m\) 个提供服务,每个服务器有两个属性 \(w\) 和 \(p\),选择的服务器提供的总权值为 \(\sum_{i = 1}^{m} w_{a_i} \prod_{j = 0}^{i – 1} p_{a_i}\),求出总权值最大为多少。

思路:

首先要对服务器进行排序,现在有两个服务器 \(i\) 和 \(j\),假设最后的排序为 \(i < j\)。
那么满足的条件为 \(w_i + w_j * p_i < w_j + w_i * p_j\)。
因为题目给定的是 \(q\)(\(p = \frac{p}{10000}\)),对公式进行移项 \(w_i * (1 – p_j) < w_j * (1 – p_i)\)。
排完序之后,枚举每个服务器进行转移,定义 \(dp[i][j]\) 表示前 \(i\) 个服务器选择了 \(j\) 个服务器能获得的最大权值。
类似于 01 背包,可以压缩一下,变成 \(dp[j]\),然后转移即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, m;
	cin >> n >> m;
	vector < array<LL, 2> > a(n);
	for (int i = 0; i < n; i ++ )
		cin >> a[i][0];
	for (int i = 0; i < n; i ++ )
		cin >> a[i][1];
	sort(a.begin(), a.end(), [&](auto x, auto y){
		return x[0] * (10000 - y[1]) < y[0] * (10000 - x[1]);
	});
	vector <double> dp(m + 1);
	for (int i = 0; i < n; i ++ ){
		for (int j = m; j >= 1; j -- ){
			dp[j] = max(dp[j], dp[j - 1] * 0.0001 * a[i][1] + a[i][0]);
		}
	}
	cout << fixed << setprecision(15) << dp[m] << "\n";
	return 0;
}

D.Jobs (Easy Version)

题意:

有 \(n\) 家公司,第 \(i\) 家公司有 \(m_i\) 个工作,当一个人的 IQ,EQ,AQ 都满足工作的要求时,他才能胜任这份工作,当一个人能胜任公司中任何一份工作,他就会被公司录用,现在有 \(q\) 次询问,每次询问给出一个人的三商,问他能被几家公司录用。

思路:

定义 \(dp[i][a][b]\) 表示第 \(i\) 家公司录取 IQ 为 \(a\),EQ 为 \(b\) 的人需要的 \(AQ\) 最低为多少,容易得到转移方程。
题目需要的答案可以通过递推优化一下,秦九韶算法。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, q;
	cin >> n >> q;
	vector dp(n, vector(401, vector<LL>(401, 401)));
	for (int i = 0; i < n; i ++ ){
		LL m;
		cin >> m;
		for (int j = 0; j < m; j ++ ){
			LL a, b, c;
			cin >> a >> b >> c;
			dp[i][a][b] = min(dp[i][a][b], c);
		}
		for (int a = 1; a <= 400; a ++ )
			for (int b = 1; b <= 400; b ++ ){
				dp[i][a][b] = min(dp[i][a][b], dp[i][a - 1][b]);
				dp[i][a][b] = min(dp[i][a][b], dp[i][a][b - 1]);
			}
	}
	LL seed;
	cin >> seed;
	mt19937 rng(seed);
	uniform_int_distribution<> u(1, 400);
	auto solve = [&](LL a, LL b, LL c){
		LL ans = 0;
		for (int i = 0; i < n; i ++ )
			ans += (c >= dp[i][a][b]);
		return ans;
	};
	LL lastans = 0, ans = 0;
	for (int i = 1; i <= q; i ++ ){
		LL IQ = (u(rng) ^ lastans) % 400 + 1;
		LL EQ = (u(rng) ^ lastans) % 400 + 1;
		LL AQ = (u(rng) ^ lastans) % 400 + 1;
		lastans = solve(IQ, EQ, AQ);
		ans = (ans * seed + lastans) % mod;
	}
	cout << ans << "\n";
	return 0;
}

H.Wall Builder II

题意:

有长为 1 的矩形 \(n\) 个,长为 2 的矩形 \(n – 1\) 个,…,长为 \(n\) 的矩形 1 个,所有矩形的高度为 1,将这些矩形拼成一个大矩形,求出拼成的大矩形的周长的最小值,并输出每个矩形放置的位置(左下角的坐标和右上角的坐标)。放置矩形的时候是将长的那条边对应 \(x\) 轴放置,不能旋转矩形再放置。

思路:

因为矩形的总面积确定了,所以可以枚举可能的长和高,然后每次判断一下当前的矩形能不能拼出来。
通过 \(multiset\) 去存每个矩形,删除的时候需要删除指定位置,不能删某个值(\(multiset\) 删除值会将集合中所有等于这个值的元素都删除)。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
	LL n;
	cin >> n;
	LL area = 0;
	for (int i = 1; i <= n; i ++ )
		area += i * (n - i + 1);
	LL ans = 1e9;
	vector < vector<LL> > point(n * (n + 1) / 2);
	auto check = [&](LL w, LL h){
		vector < vector<LL> > t(n * (n + 1) / 2);
		multiset <LL> seg;
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= n - i + 1; j ++ )
				seg.insert(i);
		LL cnt = 0;
		for (int i = 0; i < h; i ++ ){
			LL tw = w;
			while(tw > 0){
				auto it = seg.lower_bound(tw);
				LL len = *it;
				LL mx = *(prev(seg.end()));
				if (len > mx){
					len = mx;
					it = prev(seg.end());
				}
				if (len > tw) return;
				seg.erase(it);
				t[cnt].push_back(w - tw);
				t[cnt].push_back(i);
				t[cnt].push_back(w - tw + len);
				t[cnt].push_back(i + 1);
				cnt ++ ;
				tw -= len;
			}
		}
		ans = min(ans, 2 * (w + h));
		for (int i = 0; i < n * (n + 1) / 2; i ++ )
			point[i] = t[i];
	};
	for (int w = 1; w <= area / w; w ++ ){
		if (area % w == 0){
			check(w, area / w);
			check(area / w, w);
		}
	}
	cout << ans << "\n";
	for (int i = 0; i < n * (n + 1) / 2; i ++ )
		for (int j = 0; j < 4; j ++ )
			cout << point[i][j] << " \n"[j == 3];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}

K.NIO’s Sword

题意:

有一把初始攻击力为 \(A(A = 0)\) 的剑,需要依次杀死 \(n\) 个敌人(从 1 到 \(n\)),当剑的攻击力模 \(n\) 与 \(i\) 同余的时候,可以杀死第 \(i\) 个敌人。可以升级剑,选择一个值 \(x(0 <= x <= 9)\),让 \(A = A * 10 + x\),问最少需要升级多少次才能杀死 1 到 \(n\) 的所有敌人。

思路:

设 \(k\) 为升级的次数,那么可以得到 \((i – 1) * 10^k + x \equiv i (mod n)\),\(x\) 为一个小于 \(10^k\) 的数。所以 \(x = i – (i – 1) * 10^k\),因为数据限制,所以枚举 \(x\) 是否存在即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL fac[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n;
	cin >> n;
	if (n == 1){
		cout << "0\n";
	}
	else{
		LL ans = 0;
		for (int i = 1; i <= n; i ++ ){
			for (int j = 1; j <= 6; j ++ ){
				LL x = (i - fac[j] * (i - 1) % n + n) % n;
				if (x < fac[j]){
					ans += j;
					break;
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

N.Particle Arts

题意:

有 \(n\) 个粒子,每个粒子有一个值 \(a_i\),两两之间会不断相互碰撞,\(a_i\) 和 \(a_j\) 碰撞后,\(a_i = a_i and a_j\),\(a_j = a_i or a_j\),问最后稳定之后的粒子的方差收敛至多少。

思路:

假设碰撞后,左边的值为 \(or\) 的值,那么最后稳定状态下,每一位上的 1 肯定都挤在左边,容易得到稳定之后的序列。
因为直接求会溢出,根据 \(D(x) = E(x^2) – E(x) ^ 2\) 求解即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n;
	cin >> n;
	vector <LL> a(n), bit(20);
	for (int i = 0; i < n; i ++ ){
		cin >> a[i];
		LL cnt = 0;
		while(a[i]){
			bit[cnt ++ ] += (a[i] & 1);
			a[i] >>= 1;
		}
	}
	LL sum1 = 0, sum2 = 0;
	for (int i = 0; i < n; i ++ ){
		for (int j = 15; j >= 0; j -- ){
			a[i] <<= 1;
			if (bit[j]){
				a[i] ++ ;
				bit[j] -- ;
			}
		}
		sum1 += a[i];
		sum2 += a[i] * a[i];
	}
	LL p = sum2 * n - sum1 * sum1;
	LL q = n * n;
	LL g = gcd(p, q);
	cout << p / g << "/" << q / g << "\n";
	return 0;
}