• 欢迎光临~

"蔚来杯"2022牛客暑期多校训练营4

开发技术 开发技术 2022-08-06 次浏览

比赛链接:

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 << "0n";
	}
	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;
}
程序员灯塔
转载请注明原文链接:"蔚来杯"2022牛客暑期多校训练营4
喜欢 (0)