AtCoder Beginner Contest 312
A - Chord (abc312 A)
题目大意
给定一个长度为\(3\)的字符串，问是不是ACE, BDF, CEG, DFA, EGB, FAC, GBD中的一个。
解题思路
依次判断即可。
神奇的代码
#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);
set<string> q{"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"};
string a;
cin >> a;
if (q.find(a) != q.end()) {
cout << "Yes" << '\n';
} else {
cout << "No" << '\n';
}
return 0;
}
B - TaK Code (abc312 B)
题目大意
给定一个仅包含#.的二维图案，找出所有符合以下模板的\(9 \times 9\)的子图案。
###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###
其中#.必须严格符合，而?随意。
解题思路
数据规模不大，直接枚举\(9 \times 9\)的左上角，然后暴力判断这个图案是否符合上述要求即可。
神奇的代码
#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 t = "###.?????"
"###.?????"
"###.?????"
"....?????"
"?????????"
"?????...."
"?????.###"
"?????.###"
"?????.###";
int n, m;
cin >> n >> m;
vector<string> s(n);
for (auto& i : s)
cin >> i;
auto ok = [&](int x, int y) {
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
int pos = i * 9 + j;
int nx = x + i, ny = y + j;
if (nx >= n || ny >= m)
return false;
if (t[pos] != '?' && s[nx][ny] != t[pos])
return false;
}
return true;
};
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (ok(i, j))
cout << i + 1 << ' ' << j + 1 << '\n';
return 0;
}
C - Invisible Hand (abc312 C)
题目大意
有\(n\)个售卖者和\(m\)个购买者。
你现在要决定一个最小的价格\(x\)，使得愿意售卖的人数不小于愿意购买的人数。
对于第\(i\)个售卖者，如果 \(x \geq a_i\)，则他愿意售卖。
对于第\(i\)个购买者，如果 \(x \leq b_i\)，则他愿意购买。
解题思路
注意到\(x\)越大，愿意售卖的人会越来越多，愿意购买的人会越来越小，两者均呈现一个单调性，因而愿意售卖人数-愿意购买人数也具有 单调性，而题意就是找零点。因此我们可以二分这个x。
事先对售卖者的\(a_i\)和购买者的\(b_i\)排个序，对于一个\(x\)，可通过二分找到愿意售卖和购买的人数，然后判断是否符合条件即可。
时间复杂度是\(O(\log 10^9 \log nm)\)
神奇的代码
#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), b(m);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
int l = -1, r = 1e9 + 1;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
while (l + 1 < r) {
int mid = (l + r) >> 1;
int seller = upper_bound(a.begin(), a.end(), mid) - a.begin();
int buyer = b.end() - lower_bound(b.begin(), b.end(), mid);
if (seller >= buyer)
r = mid;
else
l = mid;
}
cout << r << '\n';
return 0;
}
或许你可以注意到最终答案一定是其中的\(a_i\)或 \(b_i\)，因此可以从小到大枚举这些候选答案，故愿意售卖的人数会越来越多，愿意购买的人数会越来越小，两个双指针维护一下其人数也可以。
D - Count Bracket Sequences (abc312 D)
题目大意
给定一个()?的序列，将其中的?替换成(或)。
问有多少种替换方案，满足替换后的序列符合一个合法的括号序列。
解题思路
要判断一个序列是否是合法的括号序列，就要求从左到右的每个位置，(的数量不少于)的数量，且最后两者数量相等。
因此为了保证方案的合法性，我们在搜索时需要记录此时有多少个(和)，但这样的状态是\(O(n^2)\)，注意到我们实际上并不需要记录括号的对数，只需要保证其差 不小于0，且最后的差等于0，因此我们只需记录两者的差，就可以转移了。
即设\(dp[i][j]\)表示前 \(i\)个字符中，替换 ?后(数量 - )数量 = j的方案数。
根据当前的字符转移即可，如果是?则决定是(还是)。
初始条件就是\(dp[0][0] = 1\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int n = s.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (auto& c : s) {
vector<int> dp2(n + 1, 0);
for (int i = 0; i <= n; ++i) {
if (c == '(' && i)
dp2[i] = dp[i - 1];
else if (c == ')' && i != n)
dp2[i] = dp[i + 1];
else if (c == '?') {
if (i)
dp2[i] = dp[i - 1];
if (i != n)
dp2[i] += dp[i + 1];
if (dp2[i] >= mo)
dp2[i] -= mo;
}
}
dp.swap(dp2);
}
cout << dp[0] << '\n';
return 0;
}
E - Tangency of Cuboids (abc312 E)
题目大意
给定\(n\)个没有相交的正方体，对于每个正方体，问它与多少个正方体会有面的相切。
解题思路
考虑正方体面相切的情况，分别为上下切、左右切、前后切，其实分别对应着某一维度的坐标相同。
因此我们分别考虑三个坐标相同的情况。
比如对于同为\(z=1\)的面，我们要判断的就是这个面上的一个正方形与多少个正方形相交。
考虑如何判断正方形相交，或者相离，由于坐标大小只有\(100\)，感觉可以前缀和然后容斥下，但发现貌似非常复杂。
注意到正方形相交的情况，由于题意表示正方体之间没有相交，这意味着在这个平面内，某点最多被两个正方形覆盖（上下相切的话，那么某点被正方形覆盖，只有上正方体和下正方体的两个面），这意味着我们可以直接记录某个位置是被哪个正方形覆盖的，这样通过遍历每个位置，就知道每个位置有哪两个正方形相互覆盖了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int sz = 101;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<array<int, 6>> p(n);
for (auto& i : p) {
for (auto& j : i)
cin >> j;
}
vector<unordered_set<int>> ans(n);
auto solve = [&](int x, int y, int z) {
array<vector<int>, sz> id;
for (int i = 0; i < n; ++i) {
id[p[i][x]].push_back(i);
id[p[i][x + 3]].push_back(i);
}
for (int Z = 0; Z < sz; ++Z) {
array<array<int, sz>, sz> belong{};
for (auto& i : belong)
fill(i.begin(), i.end(), -1);
for (auto& i : id[Z]) {
for (int X = p[i][y]; X < p[i][y + 3]; ++X)
for (int Y = p[i][z]; Y < p[i][z + 3]; ++Y) {
int& own = belong[X][Y];
if (own != -1) {
ans[own].insert(i);
ans[i].insert(own);
} else {
own = i;
}
}
}
}
};
solve(0, 1, 2);
solve(1, 0, 2);
solve(2, 0, 1);
for (auto& i : ans) {
cout << i.size() << '\n';
}
return 0;
}
F - Cans and Openers (abc312 F)
题目大意
给定\(n\)个物品，物品分三种：
- 普通物品，快乐值 \(x_i\)
- 特殊物品，需要钥匙打开，快乐值 \(x_i\)
- 钥匙物品，可打开\(x_i\) 个特殊物品。
你现在只能拿\(m\)个物品，问最大的快乐值。
解题思路
初看此题，有一些比较显然的性质。
如果规定了只能拿\(a\)个普通物品，那我肯定拿快乐值最大的那 \(a\)个。 同理对于特殊物品、钥匙物品，都是贪心的取最大的那些。
由于\(n\)有 \(10^5\)，注定我们只能枚举一种物品的数量。
可以发现如果考虑枚举取\(a\)个钥匙物品的数量的话，假设这\(a\)个钥匙物品可打开 \(b\)个特殊物品，那剩下的就是从所有普通物品和前 \(b\)大的特殊物品中取快乐值最大的 \(m-a\)个。随着这个 \(a\)的递增，可取的特殊物品的范围越来越大，这意味着我们可以继承上一步的信息，考虑新增的特殊物品是否取即可。
维护一堆物品的前 \(m\)大的和，用一个小根堆的优先队列维护，当新增的物品的快乐值大于堆顶时，且堆大小等于 \(m\)，则丢弃堆顶，将新的放进去。
神奇的代码
#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;
array<vector<int>, 3> items;
for (int i = 0; i < n; ++i) {
int t, x;
cin >> t >> x;
items[t].push_back(x);
}
for (auto& item : items)
sort(item.begin(), item.end(), greater<int>());
priority_queue<int> s;
LL sum = 0;
for (int i = 0; i < items[0].size(); ++i) {
if (s.size() == m)
break;
s.push(-items[0][i]);
sum += items[0][i];
}
LL ans = sum;
int l = 0;
for (auto& i : items[2]) {
--m;
if (m < 0)
break;
int r = l + i;
while (s.size() > m) {
sum += s.top();
s.pop();
}
while (l < r) {
if (l >= items[1].size())
break;
if (s.size() < m) {
sum += items[1][l];
s.push(-items[1][l]);
} else if (-s.top() < items[1][l]) {
sum += s.top();
s.pop();
sum += items[1][l];
s.push(-items[1][l]);
}
++l;
}
ans = max(ans, sum);
}
cout << ans << '\n';
return 0;
}
G - Avoid Straight Line (abc312 G)
题目大意
给定一棵树，问有多少个递增的三元组\((i,j,k)\)，满足不存在一条简单路径覆盖这三个点。
解题思路
首先考虑怎样的三个点不能被一条简单路径覆盖。
树上两点确定唯一一条路径，如果第三点在这条路径上，或者在两点的子树里，则可以存在一条路径覆盖这三个点，其点数时两个子树大小+路径长度，这两个值都可以通过预处理很快算出来，其补集就是不存在覆盖情况。
但如果枚举这两点的话，复杂度避免不了\(O(n^2)\)，因此只能枚举一个点。
同样考虑枚举这条路径，要么枚举路径最边边的点要么枚举路径的中间点。
可以发现枚举路径的中间点\(u\)时，另外两个点的所在情况只有两种：
- 两个点在\(u\)的两个不同的儿子子树中，这个用类似树形\(dp\)的方式合并求答案即可。
- 一个点在\(u\)的儿子子树 ，另一个点在父亲往上的其余位置。父亲往上的情况数就是总点数减去子树大小。
两种情况累加存在简单路径覆盖三个点的情况。
用总情况数(\(\frac{n(n-1)(n-2)}{6}\))减去即为答案。
神奇的代码
#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<vector<int>> edge(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
edge[u].push_back(v);
edge[v].push_back(u);
}
LL ans = 0;
vector<int> son(n, 0);
function<void(int, int)> dfs = [&](int u, int fa) {
for (auto& v : edge[u]) {
if (v == fa)
continue;
dfs(v, u);
ans += 1ll * son[u] * son[v];
son[u] += son[v];
}
son[u] += 1;
ans += 1ll * (son[u] - 1) * (n - son[u]);
};
dfs(0, 0);
ans = (1ll * n * (n - 1) * (n - 2) / 6 - ans);
cout << ans << '\n';
return 0;
}
Ex - snukesnuke (abc312 Ex)
题目大意
有\(n\)个人及其名字 \(s_i\)。
但名字可能有重复，为了不重复，你需要依次对每个人的名字操作。
对于第 \(i\)个人的名字，如果它与前面的重复了，你需要决定一个最小的数 \(k\)，使得 \(s_i\)重复 \(k\)次后与前面不重复。
对于每个人，输出 \(k\)的大小。
解题思路
考虑对字符串hash，这样的话重复操作相当于hash的一个简单四则运算（乘以一个关于长度的基底+原字符串hash值）。
然后我们记录哪些hash值出现过，暴力做貌似最坏会\(O(n^2)\) ，就像样例\(3\)的五个 x。究其原因是我们经过了很多次的x -> xx -> xxx这样重复的变换了，为了不重复，我们可以把这样的信息记录下来，即记录某个hash值因冲突而被重复的最高次数，或许就能\(O(\text{能过})\)?
写了写发现过了，朴素的自然hash也没被卡。细想一下复杂度貌似确实是\(O(n)\)的，考虑每个字符串被后面字符串考虑是否冲突的次数，会发现最多只有一次，即在因冲突而进行重复操作后，之后因为记录了最高重复次数，所以之后考虑时就不再会考虑这个字符串了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int x = 135;
const int N = 2e5 + 10;
ULL xp[N];
void init_xp() {
xp[0] = 1;
for (int i = 1; i < N; ++i) {
xp[i] = xp[i - 1] * x;
}
}
ULL hash_string(const string& s) {
int l = s.size();
ULL val = 0;
for (int j = l - 1; j >= 0; --j) {
val = val * x + s[j];
}
return val;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init_xp();
int n;
cin >> n;
unordered_set<ULL> name;
unordered_map<ULL, int> k;
unordered_map<ULL, ULL> khash;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
ULL val = hash_string(s);
ULL cur = val;
int ans = 0;
if (name.find(val) == name.end()) {
ans = 1;
} else {
if (k.find(val) == k.end())
ans = 1;
else {
ans = k[val];
cur = khash[val];
}
while (name.find(cur) != name.end()) {
cur = cur * xp[s.size()] + val;
++ans;
}
}
k[val] = ans;
khash[val] = cur;
name.insert(cur);
cout << ans << " \n"[i == n - 1];
}
return 0;
}