AtCoder Beginner Contest 346
A - Adjacent Product (abc346 A)
题目大意
给定\(n\)个数，依次输出相邻俩数的乘积。
解题思路
按照题意模拟即可。
神奇的代码
#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;
int la = 0;
cin >> la;
for (int i = 1; i < n; i++) {
int a;
cin >> a;
cout << la * a << '\n';
la = a;
}
return 0;
}
B - Piano (abc346 B)
题目大意
给定一个由wbwbwwbwbwbw无限拼接的字符串。
给定\(w,b\)，问是否由一个子串，其有 \(w\)个 w， \(b\)个 b
解题思路
考虑枚举子串的起点，其实只有\(len(wbwbwwbwbwbw)=12\)种情况。
枚举起点后，统计其后的\(w+b\)个字符，看看是否满足上述需求即可。
时间复杂度是 \(O(12(w+b))\)
神奇的代码
#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);
string s = "wbwbwwbwbwbw";
int w, b;
cin >> w >> b;
int len = w + b;
bool ok = false;
for (int i = 0; i < s.size(); ++i) {
map<char, int> cc;
for (int j = i, cnt = 0; cnt < len; j = (j + 1) % s.size(), ++cnt) {
cc[s[j]]++;
}
if (cc['w'] == w && cc['b'] == b) {
ok = true;
break;
}
}
if (ok)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
C - Σ (abc346 C)
题目大意
给定\(n\)个数 \(a_i\)。
问 \(1 \sim k\)中，不是 \(a_i\)的数的和。
解题思路
先计算\(\sun_{i=1}{k}i = \frac{k(k+1)}{2}\)，然后减去 \(a_i\)中出现过的数即可。注意要对 \(a_i\)去重，可以先 \(sort\)再 \(unique\)，或者直接丢到 \(set\)里。
神奇的代码
#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, k;
cin >> n >> k;
vector<int> a(n);
for (auto& i : a)
cin >> i;
LL ans = 1ll * k * (k + 1) / 2;
for (auto& i : set<int>(a.begin(), a.end())) {
if (i <= k) {
ans -= i;
}
}
cout << ans << '\n';
return 0;
}
D - Gomamayo Sequence (abc346 D)
题目大意
给定一个\(01\)字符串\(s\)，对第 \(i\)位翻转需要 \(c_i\)的代价。
定义一个好的字符串，当且仅当只有一个相邻位置上的数字是相同的。
问将字符串变成好的字符串的最小代价。
解题思路
注意到好的字符串的情况数只有\(O(n)\)个，其中 \(n\)是串 \(s\)的长度。因此我们可以枚举所有情况。
枚举相邻数字相同的位置，然后计算变成 \(010101.....\)和 \(101010...\)这两种情况的代价，所有位置情况代价取最小值即为答案。
如何快速计算代价？考虑到由相邻数字相同的位置左右分割开来的都是固定的\(010101\)或 \(101010\)，因此事先预处理所有前缀和后缀变换成 \(010101\)和 \(101010\)的代价后，通过前缀代价+后缀代价，就可以\(O(1)\)得到当前枚举的情况的代价。
神奇的代码
#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 s;
cin >> n >> s;
vector<int> c(n);
for (auto& i : c)
cin >> i;
vector<array<LL, 2>> pre(n + 1), suff(n + 1);
const string expect = "01";
for (int i = 0; i < n; ++i) {
pre[i][0] =
(s[i] == expect[i & 1] ? c[i] : 0) + (i > 0 ? pre[i - 1][0] : 0);
pre[i][1] =
(s[i] == expect[~i & 1] ? c[i] : 0) + (i > 0 ? pre[i - 1][1] : 0);
}
for (int i = n - 1; i >= 0; --i) {
suff[i][0] = (s[i] == expect[i & 1] ? c[i] : 0) +
(i < n - 1 ? suff[i + 1][0] : 0);
suff[i][1] = (s[i] == expect[~i & 1] ? c[i] : 0) +
(i < n - 1 ? suff[i + 1][1] : 0);
}
LL ans = 1e18 + 7;
;
for (int i = 0; i < n - 1; ++i) {
ans =
min({ans, pre[i][0] + suff[i + 1][1], pre[i][1] + suff[i + 1][0]});
}
cout << ans << '\n';
return 0;
}
E - Paint (abc346 E)
题目大意
\(h \times w\)的平面，格子初始全为颜色 \(0\)。
依次进行 \(m\)次操作，每次操作将某一行或某一列的格子涂成颜色 \(x_i\)。
问最后各个颜色的格子数量。
解题思路
朴素的想法，最后统计每块格子的颜色，时间复杂度避免不了为为\(O(hw)\)。
考虑到每次操作都是对一行或一列涂色，其涂的格子数是已知的，所以可以直接累计结果。
但这样的问题是，后面的操作会影响到前面的结果，颜色会覆盖，导致先前涂的颜色数量可能会减少。
注意到后面的操作会覆盖前面的操作，如果我们对操作反过来考虑，先考虑最后一次操作，再考虑前一个操作，那么后考虑的操作不会影响先考虑的操作，就不会出现上面的先前涂的颜色会减少的问题。
因此我们对操作倒过来考虑，每次操作所涂的格子数。格子数的求法比较简单，比如一次操作对某一行涂色，其涂得格子数为\(w-\)已经涂过的列操作数。维护一下已经涂过的列和行数量即可。当然还要维护某一列和某一行是否被涂过，后涂的操作是无效的。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int up = 2e5 + 8;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w, m;
cin >> h >> w >> m;
vector<array<int, 3>> op(m);
for (auto& [t, a, x] : op) {
cin >> t >> a >> x;
--a;
}
vector<LL> cnt(up, 0);
vector<int> used_row(h, 0);
vector<int> used_col(w, 0);
int row = h, col = w;
reverse(op.begin(), op.end());
for (auto& [t, a, x] : op) {
if (t == 1) {
if (used_row[a])
continue;
used_row[a] = 1;
--row;
cnt[x] += col;
} else {
if (used_col[a])
continue;
used_col[a] = 1;
--col;
cnt[x] += row;
}
}
cnt[0] += 1ll * h * w - accumulate(cnt.begin(), cnt.end(), 0ll);
vector<pair<int, LL>> ans;
for (int i = 0; i < up; ++i) {
if (cnt[i] != 0)
ans.emplace_back(i, cnt[i]);
}
cout << ans.size() << '\n';
for (auto& [i, c] : ans) {
cout << i << " " << c << '\n';
}
return 0;
}
F - SSttrriinngg in StringString (abc346 F)
题目大意
给定两个字符串\(s,t\)，定义 \(f(s,n)\)表示将字符串 \(s\)重复拼接 \(n\)次。 \(g(t,k)\)表示将 \(t\)的每个字符重复 \(k\)次得到。
给定 \(n\)，问最大的 \(k\)，使得 \(g(t,k)\)是 \(f(s,n)\)的子序列。
解题思路
\(k\)越小越好满足， \(k\)越大越难满足是子序列，容易发现\(k\)与 是否是子序列具有单调性，因此二分\(k\)。
二分\(k\)后，就按照匹配子序列那样（就近匹配）的暴力匹配 \(t\)的每个字符即可。只是细节有点多。
匹配 \(t\)的每个字符时，每个字符\(c\)有 \(k\)个，假设 \(s\)有该字符 \(cnt_c\)个，那先每 \(cnt_c\)个 \(cnt_c\)个匹配，耗掉 \(\frac{k}{cnt_c}\)个 \(s\)，然后剩下的 \(k \% cnt_c\)个\(c\)匹配 新一份的\(s\)的一部分。此时剩下的 字符就匹配\(t\)的下一个字符。
因此二分验证时需要维护信息有：
- 当前匹配的是 \(t\)的第\(cur\)个字符
- 当前字符还剩下 \(left\)个要匹配，
- 当前用了 \(sum\)份\(s\)
- 当前份正匹配到第\(it\)个字符。
神奇的代码
#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);
LL n;
string s, t;
cin >> n >> s >> t;
vector<vector<int>> pos(26);
for (int i = 0; i < s.size(); ++i) {
pos[s[i] - 'a'].push_back(i);
}
LL l = 0, r = 1e18;
auto check = [&](LL x) {
if (x == 0)
return true;
LL sum = 0;
int cur = 0;
int it = 0;
LL left = x;
while (sum <= n && cur < t.size()) {
int c = t[cur] - 'a';
if (pos[c].size() == 0)
return false;
if (it == 0) {
int cnt = pos[c].size();
LL cost = left / cnt;
sum += cost;
left -= cost * cnt;
LL mod = left % cnt;
if (mod != 0) {
sum += 1;
it = (pos[c][mod - 1] + 1) % s.size();
left -= mod;
} else {
it = (pos[c].back() + 1) % s.size();
}
} else {
int st = lower_bound(pos[c].begin(), pos[c].end(), it) -
pos[c].begin();
int cnt = pos[c].size() - st;
if (left > cnt) {
left -= cnt;
it = 0;
} else {
it = (pos[c][st + left - 1] + 1) % s.size();
left = 0;
}
}
if (left == 0) {
++cur;
left = x;
}
}
return sum <= n;
};
while (l + 1 < r) {
LL mid = (l + r) >> 1;
if (check(mid))
l = mid;
else
r = mid;
}
cout << l << '\n';
return 0;
}
G - Alone (abc346 G)
题目大意
给定\(n\)个数\(a_i\)。问 \((l,r)\)的数量，满足\(a[l..r]\)中有数字仅出现一次。
解题思路
<++>
神奇的代码