AtCoder Beginner Contest 329
劳累一天不该写题,启发式合并都写错了
A - Spread (abc329 A)
题目大意
给定一个字符串,将每个字符输出出来,中间留个空格。
解题思路
遍历输出即可。
神奇的代码
#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;
cin >> s;
for (auto& i : s)
cout << i << ' ';
cout << '\n';
return 0;
}
B - Next (abc329 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);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a)
cin >> i;
cout << *next(set<int>(a.begin(), a.end()).rbegin()) << '\n';
return 0;
}
C - Count xxx (abc329 C)
题目大意
给定一个字符串,问有多少个连续的子串,其由一个字母组成。
解题思路
对于一个字母c
,如果它连续出现了\(x\)个,那么就有 \(x\)个不同长度的由 c
组成的字符串。它对答案的贡献就是\(x\)。
一共有 \(26\)个字母,对这些字母的贡献累计求和即可。
神奇的代码
#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;
string s;
cin >> s;
array<int, 26> cnt{};
char la = 0;
int num = 0;
for (auto& i : s) {
if (i == la) {
++num;
} else {
cnt[la - 'a'] = max(cnt[la - 'a'], num);
la = i;
num = 1;
}
}
if (la) {
cnt[la - 'a'] = max(cnt[la - 'a'], num);
}
cout << accumulate(cnt.begin(), cnt.end(), 0) << '\n';
return 0;
}
D - Election Quick Report (abc329 D)
题目大意
给定\(n\)个人和 \(m\)个选票。
每个选票投给某个人。
对于 \(i \in [1,m]\),统计前\(i\)张选票,问票数最多的人的标号。同号数求最小。
解题思路
我们需要一个数据结构,它可以根据每个人的票数,动态对这\(n\)个人排序。需要动态更新票数+求最大值。刚好set
都可以以log
的复杂度内完成这些操作。
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, m;
cin >> n >> m;
vector<int> cnt(n);
set<pair<int, int>> candi;
auto remove = [&](int id) { candi.erase({-cnt[id], id}); };
auto insert = [&](int id) { candi.insert({-cnt[id], id}); };
for (int i = 0; i < n; ++i)
insert(i);
while (m--) {
int x;
cin >> x;
--x;
remove(x);
cnt[x]++;
insert(x);
cout << candi.begin()->second + 1 << '\n';
}
return 0;
}
E - Stamp (abc329 E)
题目大意
给定一个长度为\(n\)的目标串\(s\)和一个长度为\(m\)的盖章串 \(t\)。
给定一个长度为\(n\)的 #
串,拿\(t\)去盖章,问能否盖出 \(s\)。
解题思路
考虑盖章的性质,每次覆盖都是连续串被覆盖,因此可以认为串\(s\)是由若干个串\(t\)的子串构成的。比如样例一的 ABC B ABC
,都是ABC
的子串。
但是还有一些要求,考虑两次盖章\(a,b\),它们相互覆盖,由于盖章有先后顺序,因此要么\(a\)的后缀被覆盖了(此时\(b\)是前缀),要么 \(b\)的前缀被覆盖了(此时\(a\)是后缀) ,因此相邻子串,要么前者\(a\)是\(t\)的后缀,要么后者\(b\)是 \(t\)的前缀。比如样例二的AB BC ABC
是不可行的,因为子串 AB
和BC
不满足上述的要求,ABC
和ABC
相互覆盖,要么前者后覆盖,是ABC C
,要么后者后覆盖,是A ABC
,始终做不到AB
和BC
。
由此设\(dp[i][0/1]\)表示覆盖\(s\)的前 \(i\)个字符,且最后一次覆盖 不是/是
\(t\)的后缀 ,这情况是否存在。初始条件就是\(dp[0][0] = 1\)。
转移就枚举\(t\)的子串,如果是 \(t\)的前缀则直接从\(dp[][0/1]\)转移 ,不是前缀则从\(dp[][1]\)转移。
最后答案就是 \(dp[n][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, m;
string s, t;
cin >> n >> m >> s >> t;
vector<array<int, 2>> dp(n + 1, array<int, 2>{});
dp[0][0] = 1;
auto ok = [&](int l, int r, int L, int R) {
return s.substr(l, r - l + 1) == t.substr(L, R - L + 1);
};
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = j; k < m; ++k) {
int len = k - j + 1;
if (len > i)
break;
if (!ok(i - len, i - 1, j, k))
continue;
if (j == 0)
dp[i][k == m - 1] |= dp[i - len][0];
dp[i][k == m - 1] |= dp[i - len][1];
}
}
}
if (dp[n][1])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
反过来思考,从串\(s\)开始考虑最后一次覆盖,它一定是一个完整的\(t\)串。
我们从中找到一个完整的 \(t\)串,将其撤销
,那么这些位置的字母就变成 #
,相当于通配符,它可以匹配任何字母。为什么可以这样做呢?因为这个位置的字符会被最后的操作覆盖,因此原先是什么字母都无所谓,不会影响最后的结果,所以可以认为是通配符。
然后重复找到可以匹配串\(t\)的子串(其长度显然是\(m\)), 将其改成#
。如果最后串\(s\)所有字符都是 #
,那么是可行的。
如此暴力找的复杂度是\(O(n^2m)\) 。考虑到如果一个子串被改成了#
,那么可能能匹配\(t\)的串只有附近的 \(O(2m)\)个,因此我们只需检索周围的这 \(O(2m)\)个能否匹配,可以匹配则依次类推,就像 BFS
一样扩展判断。每个\(m\)长度的子串的判断次数只有 \(m\)次,每次判断的复杂度是\(O(m)\),因此总的复杂度是 \(O(nm^2)\)。
神奇的代码
#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;
string s, t;
cin >> n >> m >> s >> t;
vector<int> used(n);
auto ok = [&](int l) {
if (used[l])
return false;
for (int i = l; i < l + m; ++i) {
if (i >= n)
return false;
if (s[i] == '#')
continue;
if (s[i] != t[i - l])
return false;
}
return true;
};
queue<int> team;
for (int i = 0; i < n; ++i)
if (ok(i))
team.push(i);
while (!team.empty()) {
int u = team.front();
team.pop();
for (int i = u; i < u + m; ++i)
s[i] = '#';
used[u] = 1;
for (int i = max(u - m + 1, 0); i < min(u + m, n); ++i)
if (ok(i))
team.push(i);
}
if (ranges::count(s, '#') == n)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
F - Colored Ball (abc329 F)
题目大意
\(n\)个箱子,第\(i\)个箱子有一个 \(c_i\)颜色的球。
执行以下\(q\)次操作。
每个操作给定 \(a, b\),将第 \(a\)个箱子里的所有球放入第 \(b\)个箱子里,并输出第 \(b\)个箱子里的颜色数量。
解题思路
直接执行操作的复杂度是\(O(nq)\)。显然通过不了。
注意操作是一个合并,单纯的只有合并没有分裂的话,可以采用启发式合并,即合并的时候,始终保持数量小的合并到数量大的
。
由于要输出颜色数量,因此可以用set
或unordered_set
来维护一个箱子的球颜色。合并的时候将size
小的set
的元素插入到size
大的set
,由于可能会\(b \to a\),在此情况下 swap
两个set
即可。
注意set
的swap
是\(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, q;
cin >> n >> q;
vector<set<int>> cnt(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnt[i].insert(x);
}
while (q--) {
int a, b;
cin >> a >> b;
--a, --b;
bool swapp = false;
if (cnt[a].size() > cnt[b].size()) {
swapp = true;
swap(a, b);
}
cnt[b].insert(cnt[a].begin(), cnt[a].end());
cout << cnt[b].size() << '\n';
cnt[a].clear();
if (swapp)
cnt[a].swap(cnt[b]);
}
return 0;
}
G - Delivery on Tree (abc329 G)
题目大意
给定一棵二叉树,有\(m\)个球,初始在节点 \(s_i\),最终要去 \(t_i\),\(1\)号点有篮子,最多装\(k\)个球。
现在要移动篮子,装球,放球,不超过篮子容量,最终每个球都在对应的\(t_i\),要求每条边最多经过两次。
问移动方案数。
解题思路
<++>
神奇的代码