AtCoder Beginner Contest 326
A - 2UP3DOWN (abc326 A)
题目大意
100楼层,一次可以上最多两层,或下最多三层。
给定两楼层,问能否一次到达。
解题思路
比较大小,然后判断其差是是不是在\(2\)或 \(3\)内即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int x, y;
cin >> x >> y;
if (x > y && x - y <= 3)
cout << "Yes" << '\n';
else if (x <= y && y - x <= 2)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - 326-like Numbers (abc326 B)
题目大意
给定一个\(n\),问不小于 \(n\)的形如 \(326\)的数字是多少。
形如 \(326\)的数字,即数位有 \(3\),且百位 \(\times\)十位 \(=\)个位。
解题思路
只有\(1000\)个数,枚举判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
auto is_326 = [](int x) {
auto s = to_string(x);
return (s[0] - '0') * (s[1] - '0') == (s[2] - '0');
};
while (!is_326(n))
++n;
cout << n << '\n';
return 0;
}
C - Peak (abc326 C)
题目大意
给定一维数轴上的\(n\)个礼物点,问长度为\(M\)的左闭右开的区间最多有多少个点。
解题思路
注意到最好情况下,其区间的左端点一定是礼物点。
因此我们可以枚举左端点所在的礼物点,然后看看到右端点时包含了多少个礼物。这个可以先对礼物点排序然后二分找到右端点礼物,作差得到数量。
当然也可以双指针。
ranges::
的用法是c++20
的特性。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto& i : a)
cin >> i;
ranges::sort(a);
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, int(ranges::lower_bound(a, a[i] + m) - a.begin() - i));
}
cout << ans << '\n';
return 0;
}
D - ABC Puzzle (abc326 D)
题目大意
给定两个仅包含ABC
的长度为\(n\)的串\(a,b\),要求构造一个\(n \times n\)的矩阵,要求:
- 每行每列包含恰好一个
ABC
- 每行最左边的字母组成字符串\(a\)
- 每列最顶部的字母组成字符串\(a\)
解题思路
因为\(n\)只有 \(5\),考虑朴素搜索。
每行ABC
的排列情况只有\(5 \times 4 \times 3 = 60\)种, \(5\)行的总情况为 \(60^5 = 7e9\),但如果中间剪枝的话其合法情况数远远小于该数。
具体来说,考虑当前位置 \((x,y)\)放什么,我们需要第 \(x\)行的放置情况 \(row[x]\),第 \(y\)列的放置情况 \(col[y]\),以决定该位置能否放该字母(代码里是二进制压缩的状态)。还需要 \(left[x]\)表示第 \(x\)行的是否放过字母,以决定是否和字符串 \(a\)比较,同理也需要 \(top[y]\)表示第 \(y\)列是否放过字母,以决定是否和字符串 \(b\)比较。这里的剪枝可以减去大部份合法情况。
在考虑完一行后,可以看看 \(row[x]\)是否放了ABC
三个字母,没放满则直接剪枝。
感觉写的很复杂。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string a, b;
cin >> n >> a >> b;
vector<vector<int>> ans(n, vector<int>(n, -1));
vector<int> top(n, 1);
vector<int> left(n, 1);
vector<int> row(n);
vector<int> col(n);
auto not_have = [&](int x, int y) { return ((~x >> y) & 1); };
function<bool(int, int)> dfs = [&](int x, int y) {
if (x == n) {
for (auto& i : row)
if (i != 7)
return false;
for (auto& i : col)
if (i != 7)
return false;
return true;
}
for (int i = 0; i < 3; ++i) {
if (not_have(row[x], i) && not_have(col[y], i)) {
if (top[y] && b[y] - 'A' != i)
continue;
if (left[x] && a[x] - 'A' != i)
continue;
row[x] |= (1 << i);
col[y] |= (1 << i);
ans[x][y] = i;
int ttop = top[y], lleft = left[x];
top[y] = 0;
left[x] = 0;
if (y == n - 1) {
if (row[x] == 7 && dfs(x + 1, 0))
return true;
} else {
if (dfs(x, y + 1))
return true;
}
row[x] ^= (1 << i);
col[y] ^= (1 << i);
ans[x][y] = -1;
top[y] = ttop;
left[x] = lleft;
}
}
if (y == n - 1) {
if (row[x] != 7)
return false;
if (dfs(x + 1, 0))
return true;
} else {
if (dfs(x, y + 1))
return true;
}
return false;
};
if (dfs(0, 0)) {
cout << "Yes" << '\n';
for (auto& i : ans) {
for (auto& j : i) {
if (j == -1)
cout << '.';
else
cout << char(j + 'A');
}
cout << '\n';
}
} else
cout << "No" << '\n';
return 0;
}
E - Revenge of "The Salary of AtCoder Inc." (abc326 E)
题目大意
给定包含\(n\)个数字的数组 \(a\),以及一个等概率的 \(n\)面骰子。进行以下游戏:
初始\(x=0\),投掷一次骰子,得到 \(y\)
- 如果\(x < y\),则获得 \(a_y\)元,同时令 \(x=y\)
- 否则游戏结束
问期望获得的钱数。
解题思路
期望题,根据定义,一个状态的期望,它是所有后继状态的期望的加权平均,这里的权重是概率。
当前状态是\(x\),则设\(dp[x]\)表示当前掷出的值为 \(x\),继续游戏至游戏结束,这期间获得的期望钱数。
很显然初始条件 \(dp[n] = 0\),即 \(x=n\)时,无论怎么骰,始终有 \(y \leq n\),游戏总是会结束。
考虑一般情况,当前状态是\(x\),考虑投掷一次骰子的后继状态:
- 有\(\frac{x}{n}\)的概率投掷出\(y \leq x\),此时游戏结束,后继状态的期望收入为 \(0\)。
- 有\(\frac{1}{n}\)的概率投掷出\(y = x + 1\),此时进入后继状态\(dp[x+1]\),获得收益\(a_{x+1}\)
- 有\(\frac{1}{n}\)的概率投掷出\(y = x + 2\),此时进入后继状态\(dp[x+2]\),获得收益\(a_{x+2}\)
- 有\(\frac{1}{n}\)的概率投掷出\(y = x + 3\),此时进入后继状态\(dp[x+3]\),获得收益\(a_{x+3}\)
- ...
- 有\(\frac{1}{n}\)的概率投掷出\(y = n\),此时进入后继状态\(dp[n]\),获得收益\(a_{n}\)
由此可以写出转移式子:
这是一个后缀和,求\(dp\)的时候维护一下就可以了。观察到\(dp\)数组和后缀和的关系,代码里直接把\(dp\)数组省掉了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b) {
long long qwq = 1;
while (b) {
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x) { return qpower(x, mo - 2); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a)
cin >> i;
int presum = 0, invn = inv(n);
for (int i = n - 1; i >= 0; --i) {
presum = (0ll + presum + 1ll * presum * invn % mo + a[i]) % mo;
}
cout << 1ll * presum * invn % mo << '\n';
return 0;
}
F - Robot Rotation (abc326 F)
题目大意
二维平面,机器人初始 \((0,0)\),面向\(x\)轴正方向。给定\(n\)次移动的距离数组\(d\),每次移动前,你需要指定机器人顺时针或逆时针转 \(90\)度,随后移动。
问能否移动到达目标点 \((x,y)\),能移动到则给出一个可行的旋转序列。
解题思路
注意到\(n\)只有\(80\),且每次必须旋转机器人,这意味着机器人有一半是上下移动,一半是左右移动,最多 \(40\)次。
横纵坐标的移动我们是可以分开考虑的,因此我们就分别考虑横坐标移动的 \(40\)次操作和纵坐标移动的 \(40\)次操作。
而操作,事实上就是决定移动距离的正负性。注意到 \(40\)其实是个很微妙的性质,它的一半 \(20\)是可以承受指数的复杂度的。即采用折半搜索的策略。
即对于这 \(40\)次操作,我们要对它们赋予正负号,看它们的和能否成为 目标移动距离\(x\)(或 \(y\))。
我们可以分别对前\(20\)个数和后\(20个数\),花 \(O(2^{20})\)枚举它们的正负号,记录它们的和。
然后再把这两部份的结果合并:能否从左右两边的结果各挑一个数,它们的和\(=x\)。这是一个非常简单的子问题,对两边排序后一个双指针就可以解决了。这里的时间复杂度是 \(O(2^{20} \log)\)。
分别对\(x,y\)方向进行一次折半搜索,就可以搜到结果了。
由于要输出方案,因此我们得记录该结果的每一项的正负号,下面代码是通过二进制压缩的形式记录的,最后还要通过每一项的正负号,以及当前机器人的朝向决定向左向右转。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, x, y;
cin >> n >> x >> y;
array<vector<int>, 2> a;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
a[i & 1].push_back(x);
}
auto dfs = [&](auto self, const vector<int>& a, int pos, int sum, int sol,
int l, int r, vector<array<int, 2>>& tmp) {
if (pos + l == r) {
tmp.push_back({sum, sol});
return;
}
self(self, a, pos + 1, sum + a[pos + l], sol, l, r, tmp);
self(self, a, pos + 1, sum - a[pos + l], (sol | (1 << pos)), l, r, tmp);
};
auto solve = [&](const vector<int>& a, int val) {
int mid = a.size() / 2;
vector<array<int, 2>> l, r;
dfs(dfs, a, 0, 0, 0, 0, mid, l);
dfs(dfs, a, 0, 0, 0, mid, a.size(), r);
vector<int> lid(l.size()), rid(r.size());
iota(lid.begin(), lid.end(), 0);
iota(rid.begin(), rid.end(), 0);
ranges::sort(lid, [&](int x, int y) { return l[x][0] < l[y][0]; });
ranges::sort(rid, [&](int x, int y) { return r[x][0] > r[y][0]; });
auto lp = lid.begin(), rp = rid.begin();
while (lp != lid.end() && rp != rid.end()) {
if (l[*lp][0] + r[*rp][0] == val) {
return l[*lp][1] + ((1ll * r[*rp][1]) << mid);
} else if (l[*lp][0] + r[*rp][0] < val) {
lp = next(lp);
} else if (l[*lp][0] + r[*rp][0] > val) {
rp = next(rp);
}
}
return -1ll;
};
auto dy = solve(a[0], y); // 0 => +, 1 => -
auto dx = solve(a[1], x);
if (dy == -1 || dx == -1)
cout << "No" << '\n';
else {
cout << "Yes" << '\n';
vector<int> ans;
for (int i = 0; i <= n / 2; ++i) {
ans.push_back((dy >> i) & 1);
if (i < n / 2)
ans.push_back((dx >> i) & 1);
}
int dir = 0;
for (int i = 0; i < n; ++i) {
cout << "LR"[ans[i] ^ dir ^ (i & 1)];
dir = ans[i];
}
cout << '\n';
}
return 0;
}
G - Unlock Achievement (abc326 G)
题目大意
给定\(n\)个技能和 \(m\)个成就。对于第 \(i\)个技能,升一级花费 \(c_i\)。
达成第 \(i\)个成就, 有\(a_i\)的奖励,达成条件为,对于每个技能要达到指定等级或以上。
问最大的收益,即奖励\(-\)花费的最大值。
解题思路
<++>
神奇的代码