劳累一天不该写题,启发式合并都写错了
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\),要求每条边最多经过两次。
问移动方案数。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 329beginner atcoder contest 329 329 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332