本文主要是介绍AtCoder Beginner Contest 246，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

AtCoder Beginner Contest 246 Solution

A - Four Points

题意

\(xy\) 平面上有一个边平行于 \(x\) 轴和 \(y\) 轴的矩形。其中三个顶点\((x_1,y_1)(x_2,y_2)(x_3,y_3)\)已知，求出另外一个顶点\((x_4,y_4)\)。

数据范围： \(-100 \leq x_i,y_i \leq 100\)。

题解

\(xy\) 平面上有一个边平行于 \(x\) 轴和 \(y\) 轴的矩形，四个顶点的 \(x\) 坐标和 \(y\) 坐标各由 \(2\) 个不同的数字组成。

问题转化为求 \(x_1,x_2,x_3\) 中出现次数为 \(1\) 次的数为多少， \(y_1,y_2,y_3\) 中出现次数为 \(1\) 次的数为多少。

显然答案： \(x_4 = x_1 \text{ xor } x_2 \text{ xor } x_3, y_4 = y_1 \text{ xor } y_2 \text{ xor } y_3\)。

时间复杂度为 \(O(1)\)

C++ 代码示例

# include <bits/stdc++.h>
using namespace std;
int main() {
	int ansx = 0, ansy = 0;
	for (int i = 1; i <= 3; i++) {
		int x, y; cin >> x >> y;
		ansx ^= x; ansy ^= y;
	}
	cout << ansx << " " << ansy << endl;
	return 0;
}

B - Get Closer

题意

从 \((0,0)\) 向着方向向量 \((a,b)\) 走 \(1\) 个单位，所在的坐标为多少。（精确到小数点后 \(6\) 位）

数据范围： \(0 \leq a,b \leq 1000, (a,b) \ne (0,0)\)

题解

从 \((0,0)\) 向着方向向量 \((a,b)\) 走若干个单位后所在的坐标为 \((ta,tb) (t > 0)\)。

让\(|(ta,tb)| = 1\)，得到 \(t^2(a^2 + b^2) = 1\)，则\(t = \sqrt{\frac{1}{a^2 + b^2}}\)

所以，从 \((0,0)\) 向着方向向量 \((a,b)\) 走 \(1\) 个单位，所在的坐标为\((a\sqrt{\frac{1}{a^2 + b^2}}, b\sqrt{\frac{1}{a^2 + b^2}})\)。

时间复杂度为： \(O(1)\)。

C++代码示例

# include <bits/stdc++.h>
using namespace std;
int main() {
	double x, y; cin >> x >> y;
	double t = sqrt(x * x + y * y);
	printf("%.7lf %.7lf\n", x / t, y / t);
	return 0;
}

C - Coupon

题意

有 \(n\) 个商品，每个商品的价格为\(a_i\)。有 \(k\) 张优惠券，每张优惠券可以让某个商品的价格降低 \(x\)。

即商品原价为 \(a\) ，使用 \(k\) 张优惠券后，商品的现价为 \(\max\{a - kx, 0\}\)。

求使用优惠券买下所有商品所需要的价格。

数据范围：\(1 \leq n \leq 2\times 10^5, 1 \leq k,x \leq 10^9, 1 \leq a_i \leq 10^9\)。

题解

一张优惠券最多可以让购买的总金额下降 \(x\) 价格，因此我们先对所有物品尽可能使用优惠券，让这些优惠券能抵扣的价格等于其面值。

接下来若还剩余一些代金券，从剩余价格中从大到小依次使用。

这个贪心策略可以让代金券降低的价格最大。

时间复杂度为 \(O(n \log_2 n)\)

C++ 代码示例

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
signed main() {
	int n, k, x; cin >> n >> k >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; 
		int t = min(a[i] / x, k);
		k -= t;
		a[i] -= t * x;
	}
	sort(a + 1, a + 1 + n);
	reverse(a + 1, a + 1 + n);
	int ans = 0;
	for (int i = k + 1; i <= n; i++) {
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}

D - 2-variable Function

题意

设 \(f(a,b) = a^3 + a^2 b +ab^2 + b^3 (a,b \in N)\)。

给出 \(n\) ，求出最小的 \(x\) 满足：\(x \geq n, x = f(a,b)\)。

数据范围：\(0 \leq n \leq 10^{18}\)。

题解

函数 \(f(a,b)\)，如果确定 \(a\)，则函数值和 \(b\) 的大小正相关。

考虑从小到大枚举 \(a\) ，那么满足 \(f(a,b) \geq n\) 最小的 \(b_{min}\) 一定单调不升。

由于 \(f(a,b) = (a^2 + b^2)(a+b)\)，取 \(a = 10^6, b = 10^6\)，满足\(f(a,b) \geq n\)。

所以利用上述 \(b_{min}\) 一定单调不升的单调性，可以采用双指针的方法解决本题。

时间复杂度为：\(O(n^{1/3})\)。

C++ 代码示例

# include <bits/stdc++.h>
# define int long long
using namespace std;
int f(int a, int b) {
	return (a * a + b * b) * (a + b);
}
signed main() {
	int n; cin >> n;
	int ans = LLONG_MAX, t = pow(n, 1.0/3.0);
	int j = t;
	for (int i = 0; i <= t; i++) {
		while (f(i, j) >= n && j >= 0) {
			ans = min(ans, f(i, j));
			j--;
		}
	}
	cout << ans << endl;		
	return 0;
}

E - Bishop 2

题意

\(n \times n\) 的棋盘，能走的地方为.不能走的地方为#。

从 \((A_x,A_y)\) 出发走到 \((B_x, B_y)\) 最短路长度为多少（如果不能走到输出-1）。

从\((i_1,j_1)\) 能 \(1\) 步走到 \((i_2,j_2)\) 当且仅当，这两个点在同一条对角线上，并且之间都是.。

数据范围：\(2 \leq n \leq 1500\)。

题解

我好像暴力广搜搜索就过了www。

不知道是不是数据的锅...

跑了 \(5913 ms/6000ms\)

时间复杂度：\(O(kn^2) / O(\text{可过})\)。

C++ 代码示例

# include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int dx[] = {1, 1, -1, -1};
const int dy[] = {1, -1, 1, -1};
bool mp[N][N], vis[N][N];
int main() {
	int n; cin >> n;
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	for (int i = 1; i <= n; i++) {
		string s; cin >> s;
		for (int j = 1; j <= n; j++)
			mp[i][j] = (s[j - 1] == '.');
	}
	queue<pair<int, pair<int, int>>>q;
	q.push({sx, {sy, 0}}); vis[sx][sy] = 1;
	while (q.size()) {
		pair<int, pair<int, int>> frt = q.front(); q.pop();
		int x = frt.first, y = frt.second.first, step = frt.second.second;
		if (x == ex && y == ey) {
			cout << step << endl;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int xx = x, yy = y;
			while (xx >= 1 && xx <= n && yy >= 1 && yy <= n && mp[xx][yy]) {
				if (!vis[xx][yy]) {
					vis[xx][yy] = 1;
					q.push({xx, {yy, step + 1}});
				}
				xx += dx[i];
				yy += dy[i];
			}
		}
	}
	cout << -1 << endl;
	return 0;
}

F - typewriter

题意

有 \(n\) 个字符串\(s_i\)，要求使用同一个字符串中的字母构造一个长度为 \(l\) 的字符串。

有多少种不同的字符串可以构造，输出答案对 \(998244353\) 取模的结果。

数据范围：\(1 \leq n \leq 18, 1 \leq l \leq 10^9, s_i \in \text{subsequence}(\text{“abcdefghijklmnopqrstuvwxyz”})\)。

题解

字符串\(s\)中不同字母的个数为 \(c\)，使用其中的字母构造一个长度为 \(l\) 的字符串个数为 \(l^c\)。

使用第 \(i\) 个字符串字符可以构造出的长度为 \(l\) 的字符串的集合为 \(S_i\)。

那么答案为\(|\bigcup _{i = 1}^{n} S_i|\)。

根据容斥原理：\(|\bigcup _{i = 1}^{n} S_i| = \sum\limits_{i = 1} ^{n} (-1)^{k - 1} \sum\limits_{1\leq i_1< i_2 < ... < i_k \leq n} |\bigcap _{i = 1}^{k} S_{i_k} |\)。

枚举 \(n\) 个数选 \(k (1 \leq k \leq n)\) 个数后（子集枚举）：

问题转化为求出使用 \(k\) 个字符串，都能构造出长度为 \(l\) 的字符串个数为多少。

答案显然是这 \(k\) 个字符串都有的字符（设个数为 \(d\)），构造出长度为 \(l\) 的字符串个数，是\(l^d\)个。

时间复杂度为 \(O(2^n\sum |s_i|)\)。

C++代码示例

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 20;
const int mo = 998244353;
string s[N];
int ch[27];
int Pow(int x, int n) {
	int ans = 1;
	while (n) {
		if (n & 1) ans = ans * x % mo;
		n >>= 1;
		x = x * x % mo;
	}
	return ans % mo;
}
signed main() {
	int n, l; cin >> n >> l;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	int ans = 0;
	for (int mask = 1; mask < (1 << n); mask++)	{
		for (int i = 0; i < 26; i++) ch[i] = 0;
		int cnt = 0;
		for (int i = 0; i < n; i++) if ((mask >> i) & 1) {
			cnt++;
			for (char x : s[i]) ch[x - 'a']++;
		}
		int res = 0;
		for (int i = 0; i < 26; i++) 
			if (ch[i] == cnt) res++;
		if (cnt & 1) (ans += Pow(res, l)) %= mo;
		else (ans -= Pow(res, l)) %= mo, ans = (ans + mo) % mo;
	}
	cout << ans << endl;
	return 0;
}

G - Game on Tree 3

题意

小 \(A\) 和小 \(B\) 在玩游戏。有一棵 \(n\) 个节点的树，节点 \(1\) 为根，节点\(2 ... n\) 都有权值 \(a_i\)。

初始棋子在 \(1\) 节点，接下去的游戏：

• 小 \(A\) 选择一个节点将上面的数字设为 \(0\)。
• 小 \(B\) 选择移动棋子到所在节点的某个子节点。
• 如果当前棋子在叶子节点或者小 \(B\) 选择结束，则游戏结束，否则返回第 \(1\) 步。

游戏得分为最后棋子落在的节点上的数。

小 \(A\) 想要最小化这个值，小 \(B\) 想要最大化这个值，如果两个人都完美完成，输出最后的游戏得分。

数据范围：\(2 \leq n \leq 2\times 10^5, 1 \leq a_i \leq 10^9\)。

题解

考虑二分答案，问题转化为答案能否大于等于 \(S\)。

那么树上节点的权值大于等于 \(S\) 设为 \(1\) 节点，否则为 \(0\) 节点。

问题转化为，小 \(A\) 每次能选择一个 \(1\) 节点，变成 \(0\) 节点。

如果判定答案为 \(\text{true}\)，那么最优操作时，最后棋子还是能落在 \(1\) 节点。

设 \(f[u]\) 表示若棋子最终停在 \(u\) 的子树中，小\(A\) 还需要额外做的最小“选择一个 \(1\) 节点，变成 \(0\) 节点”次数，使得无论棋子停在 \(u\) 子树中什么位置，棋子停止时一定是 \(0\) 节点。

转移方程：\(f[u] = \max\{(\sum\limits_{v \in u_{son}} f[v]) - 1,0\} + \text{(u is type 1 vertex)}\)。

如果 \(f[1] > 0\) 那么说明，答案会变大，否则\(f[u] = 0\)答案将变小。

时间复杂度为\(O(n \log_2 A_{max})\)

C++ 代码示例

# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, f[N], a[N], b[N];
vector<int>e[N];
void dfs(int u, int fa) {
	f[u] = b[u];
	int sum = -1;
	for (int v : e[u]) if (v != fa) {
		dfs(v, u);
		sum += f[v];
	}
	f[u] += max(sum, 0);
}
bool check(int key) {
	for (int i = 1; i <= n; i++) 
		b[i] = (a[i] >= key), f[i] = 0;
	dfs(1, 0);
	return !(f[1] == 0);
}
int main() {
	cin >> n;
	for (int i = 2; i <= n; i++) cin >> a[i];
	for (int i = 2; i <= n; i++) {
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	int l = 0, r = 1e9, ans;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	cout << ans << endl;
	return 0;
}

这篇关于AtCoder Beginner Contest 246的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！