cf-920-div3

---

title: cf 920 div3
date: 2024-01-17 20:10:16
tags: vp
categories: 比赛

A. Square

题目大意

给出四个坐标点，求正方形面积

解题思路

最小的最小，最大的最大。

代码实现

void solve()
{
	int xmax = -1e9, xmin = 1e9, ymax = -1e9, ymin = 1e9;
	for (int i = 0; i < 4; i++) {
		int x, y;
		cin >> x >> y;
		xmax = max(x, xmax);
		xmin = min(x, xmin);
		ymax = max(y, ymax);
		ymin = min(ymin, y);
	}
	cout << (xmax - xmin) * (ymax - ymin) << endl;
}

B. Arranging Cats

题目大意

有三种操作，求字符串 $s$ 变成字符串 $t$ 的最少次数

解题思路

显然，相同的不变，只需要对不同的进行操作，统计两个字符串的 $1$ 的数量，取最多。

代码实现

void solve()
{
	int n; cin >> n;
	string a, b;
	cin >> a >> b;
	int c1 = 0, c2 = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			if (a[i] == '1') {
				++c1;
			}
			else ++c2;
		}
	}
	cout << max(c1, c2) << endl;
}

C. Sending Messages

题目大意

给出 $n$ 条信息，电量为 $f$，每秒钟耗电量 $a$，开机关机耗电量 $b$。求出能否在电量耗尽前发完信息

解题思路

模拟实现即可，发送信息的间隔，所耗电量与关机开机耗电量进行取最小即可

代码实现

void solve()
{
	int n, f, a, b;
	cin >> n >> f >> a >> b;
	vector<int> m(n + 1,0);
	for (int i = 1; i <= n; i++) cin >> m[i];
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		int x = min(b, (m[i] - m[i - 1]) * a);
		
		f -= x;
		if (f <= 0) {
			flag = 0;
			break;
		}
	}
	if (flag) cout << "YES" << endl;
	else cout << "NO" << endl;
}

D. Very Different Array

题目大意

找出 $n$ 个 $a$ 和 $n$ 个 $b$ 的最大差值

解题思路

将 $a、b$ 数组排序，最大的和最小的匹配即可

代码实现

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
 
	int ans = 0;
	for (int i = 0; i < n; i++) ans += abs(a[n - i - 1] - b[i]);
	int cur = ans;
	for (int i = 0; i < n; i++) {
		cur -= abs(a[i] - b[n - i - 1]);
		cur += abs(a[i] - b[m - i - 1]);
		ans = max(ans, cur);
	}
	cout << ans << endl;
}

E. Eat the Chip

题目大意

两人在棋盘上玩游戏，按照规定的走法走，谁先能够移动到对方的当前位置获胜，否则平局

解题思路

博弈论；分情况讨论，若是 $Bob$ 在 $Alice$ 上面，则平局；第一种情况就是，两人相差奇数行，并且列数相差小于 $1$ 或者能够逼到墙角边界，则 $Alice$ 获胜，否则平局；第二种情况则是偶数行，同理分析

代码实现

void solve()
{
	int h, w, x1, y1, x2, y2;
	cin >> h >> w >> x1 >> y1 >> x2 >> y2;
 
	if (x1 >= x2) {
		cout << "Draw" << endl;
	}
	else if ((x2 - x1) & 1) {
		int t = (x2 - x1 + 1) / 2;
		if (abs(y1 - y2) <= 1 || y2 < y1 && y1 - 1 <= t || y1 < y2 && w - y1 <= t) {
			cout << "Alice" << endl;
		}
		else cout << "Draw" << endl;
	}
	else {
		int t = (x2 - x1) / 2;
		if (y1 == y2 || y1 < y2 && y2 - 1 <= t || y2 < y1 && w - y2 <= t) {
			cout << "Bob" << endl;
		}
		else cout << "Draw" << endl;
	}
}

F. Sum of Progression

题目大意

给出一个数组 $a$，$q$ 次查询 $s、d、k$ 求$a_s+a_{s+d}?2+a_{s+2?d}?3+\dots \dots +a_{s+(k?1)?d}?k$ 的和

解题思路

根号分治。大于 $\sqrt{n}$ 直接暴力查询，间隔大；小于等于的则前缀和维护，区间查询

代码实现

int f[320][N], g[320][N];
int a[N];
 
void solve()
{
	int n, q;
	cin >> n >> q;
	int wc = sqrt(n);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= wc; i++) {
		for (int j = 1; j <= n; j++) {
			f[i][j] = (j - i >= 1 ? f[i][j - i] : 0) + (ll)a[j] * (j / i);
			g[i][j] = (j - i >= 1 ? g[i][j - i] : 0) + a[j];
		}
	}
	while (q--) {
		int s, d, k;
		cin >> s >> d >> k;
		int ans = 0;
		if (d > wc) {//暴力
			for (int i = 1, j = s; i <= k; i++, j += d) {
				ans += a[j] * i;
			}
		}
		else {//区间查询
			ans = f[d][s + (k - 1) * d] - (s - d >= 1 ? f[d][s - d] : 0);
			ans -= (s / d - 1) * (g[d][s + (k - 1) * d] - (s - d >= 1 ? g[d][s - d] : 0));
		}
		cout << ans << ' ';
	}
    cout << endl;
}