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;
}
- Beginner AtCoder Contest 312beginner atcoder contest 312 contest atcoder programming 312 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334