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\)的奖励，达成条件为，对于每个技能要达到指定等级或以上。
问最大的收益，即奖励\(-\)花费的最大值。
解题思路
<++>
神奇的代码