AtCoder Beginner Contest 308
这几天在收拾东西搬家，先附上代码，晚点补上题解
感觉这次FG都写不太明白
A - New Scheme (abc308 A)
题目大意
给定八个数，问是否满足以下要求：
- 不严格升序
- 每个数在\(100 \sim 675\)之间
- 每个数都是 \(25\)的倍数
解题思路
依次对每个数判断是否符合这三个条件即可。
神奇的代码
#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);
array<int, 8> a;
for(auto &i : a)
cin >> i;
auto ok = [&](){
for(int i = 0; i < 8; ++ i){
if (i && a[i] < a[i - 1])
return false;
if (a[i] < 100 || a[i] > 675)
return false;
if (a[i] % 25)
return false;
}
return true;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Default Price (abc308 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, m;
cin >> n >> m;
map<string, int> price;
vector<string> a(n);
for(auto &i : a)
cin >> i;
vector<string> col(m);
for(auto &i : col)
cin >> i;
int ano;
cin >> ano;
for(auto &i : col){
int p;
cin >> p;
price[i] = p;
}
int ans = 0;
for(auto &i : a){
if (price.find(i) == price.end())
ans += ano;
else
ans += price[i];
}
cout << ans << '\n';
return 0;
}
C - Standings (abc308 C)
题目大意
<++>
解题思路
<++>
神奇的代码
#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<array<int, 2>> p(n);
for(auto &i : p)
cin >> i[0] >> i[1];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int a, int b){
LL l = 1ll * p[a][0] * (p[b][0] + p[b][1]);
LL r = 1ll * p[b][0] * (p[a][0] + p[a][1]);
return l != r ? l > r : a < b;
});
for(auto &i : id)
cout << i + 1 << ' ';
cout << '\n';
return 0;
}
D - Snuke Maze (abc308 D)
题目大意
<++>
解题思路
<++>
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> tu(h);
for(auto &i : tu)
cin >> i;
string target = "snuke";
vector<vector<vector<int>>> visit(h, vector<vector<int>>(w, vector<int>(target.size(), 0)));
function<bool(int, int, int)> dfs = [&](int x, int y, int len){
visit[x][y][len] = 1;
if (tu[x][y] != target[len])
return false;
if (x == h - 1 && y == w - 1)
return true;
for(int i = 0; i < 4; ++ i){
int nx = x + dx[i], ny = y + dy[i], nlen = (len + 1) % target.size();
if (nx < 0 || nx >= h || ny < 0 || ny >= w || visit[nx][ny][nlen])
continue;
if (dfs(nx, ny, nlen))
return true;
}
return false;
};
auto ok = [&](){
return dfs(0, 0, 0);
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
E - MEX (abc308 E)
题目大意
<++>
解题思路
如果是找两个字符，比如EX，我们可以从右往左统计每个X对应的数组\(a\)的值，这样对于此时的每一个 E，假设对应的数组\(a\)的值是 \(e\)，那么所有 EX的组成的mex只有三种情况：
- \(mex(e, 0)\)
- \(mex(e, 1)\)
- \(mex(e, 2)\)
此时以该E开始，右边的所有X组成的EX，对答案的贡献就分这三类，因此我们就记录一下右边有多少个是\(0\)的 X，\(1\)的 X，\(2\)的 X。然后乘以对应的mex值就是对答案的贡献。
解决了EX，对于MEX，其实可以看成M和EX，只是这时候的EX有\(6\)种情况：
- mex(M, 0, 0)
- mex(M, 0, 1)
- mex(M, 0, 2)
- mex(M, 1, 1)
- mex(M, 1, 2)
- mex(M, 2, 2)
同样我们就记录EX分别是\(00,01,02,11,12,22\)这些情况的数量，再乘以对应的 mex值，就是该M对答案的贡献。而统计EX 的数量就是刚刚的问题。
代码里记录\(00,01\)的情况用的二进制状压的方法。
神奇的代码
#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;
string s;
cin >> s;
array<int, 3> x{};
array<LL, 8> ex{};
map<int, int> tr{{0, 1}, {1, 2}, {2, 4}};
map<int, int> mex;
auto get_mex = [&](int x, int y, int z){
set<int> candidate{0, 1, 2, 3};
if (candidate.count(x))
candidate.erase(x);
if (candidate.count(y))
candidate.erase(y);
if (candidate.count(z))
candidate.erase(z);
return *candidate.begin();
};
for(int i = 0; i < 3; ++ i)
for(int j = 0; j < 3; ++ j)
for(int k = 0; k < 3; ++ k){
mex[tr[i] | tr[j] | tr[k]] = get_mex(i, j, k);
}
LL ans = 0;
for(int i = n - 1; i >= 0; -- i){
if (s[i] == 'X'){
x[a[i]] ++;
}else if (s[i] == 'E'){
for(int j = 0; j < 3; ++ j){
int status = (tr[a[i]] | tr[j]);
ex[status] += x[j];
}
}else{
for(int j = 0; j < 8; ++ j){
ans += mex[tr[a[i]] | j] * ex[j];
}
}
}
cout << ans << '\n';
return 0;
}
F - Vouchers (abc308 F)
题目大意
<++>
解题思路
两种方向，分别按照商品价格的升序或降序依次考虑。
可以发现以升序方式考虑的话，先前考虑的优惠券同样适用后面的商品，因此我们就可以从这些未使用且可使用的优惠券中选优惠力度最大的。
考虑是否存在反例，因为每个商品只能用一个优惠券，因此每次都只会从未使用中选最好的一个。当考虑一个新商品，同时还有更多的优惠券变得可使用时，这些优惠券不能代替先前的优惠券适用（不满足最低价格），因此也替换不了。
感觉这个贪心貌似就对了。
神奇的代码
#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> p(n);
for(auto &i : p)
cin >> i;
vector<array<int, 2>> coupon(m);
for(auto &i : coupon)
cin >> i[1];
for(auto &i : coupon)
cin >> i[0];
priority_queue<array<int, 2>> best{};
sort(p.begin(), p.end());
sort(coupon.begin(), coupon.end(), [](const auto& a, const auto& b){
return a[1] < b[1];
});
int pos = 0;
LL ans = 0;
for(auto &i : p){
while(pos < m && coupon[pos][1] <= i){
best.push(coupon[pos]);
++ pos;
}
int discout = 0;
if (!best.empty()){
discout = best.top()[0];
best.pop();
}
ans += i - discout;
}
cout << ans << '\n';
return 0;
}
G - Minimum Xor Pair Query (abc308 G)
题目大意
<++>
解题思路
不考虑修改，从数组里选两个异或值最小，我们可以遍历由这n个数构成的trie数，我们选择的两个数尽量选择同一边的。如果某个节点下只有两个数，且是该节点产生分歧的，此时就选择这两个数的异或者，作为一个备选答案。通过一次dfs就能得到。
考虑修改的话，我们发现上述产生答案的信息是可以实时维护的，于是问题貌似就解决了？
具体来说，考虑一个节点\(u\)，左儿子(二进制下为\(0\))\(lson\)，右儿子(二进制下为\(1\))\(rson\) 。
- 如果\(u\)下只有两个数，一个数在 \(lson\)子树内，一个在 \(rson\)内，那以 \(u\)节点的子树的最小异或值 \(ans_u = lson \oplus rson\)。一般我们要遍历到叶子才知道这个\(lson,rson\)是多少，但为了减少时间复杂度，可以把这个信息往上提到\(lson,rson\)处，这样就不用遍历到叶子。
- 如果\(lson\)下有至少两个数，那么以\(u\)节点的子树的最小异或值 \(ans_u = min(ans_u, ans_{lson})\)，而\(ans_{lson}\)是个子问题。
- 如果\(rson\)下有至少两个数，那么以\(u\)节点的子树的最小异或值 \(ans_u = min(ans_u, ans_{rson})\)，\(ans_{rson}\)同样是个子问题。
对于叶子节点，如果该叶子对应两个数，那么 \(ans_{leaf} = 0\)，否则为无穷大。
对于题意的增加和删除，这些信息都可以在进行这些操作时\(O(1)\)维护，感觉就可以了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = (1 << 30) + 114514;
const int SZ = 2;
template<typename T, typename K>
struct Trie {
struct node {
K value;
int ans;
int vis_count;
array<int, SZ> children;
node(K val) : value(val) {
vis_count = 0;
fill(children.begin(), children.end(), 0);
ans = inf;
}
};
int cast(K val) {
int ret = val;
assert(ret < SZ and ret >= 0);
return ret;
}
vector<node> tree;
Trie(K val) {
tree.push_back(node(val));
}
void insert(int v, int pos, int cur, const T &sequence, bool remove = false) {
if (remove) {
tree[cur].vis_count -= 1;
} else {
tree[cur].vis_count += 1;
}
if (pos < sequence.size()){
K value = sequence[pos];
if (tree[cur].children[cast(value)] == 0) {
tree[cur].children[cast(value)] = (int) tree.size();
tree.emplace_back(v);
}
insert(v, pos + 1, tree[cur].children[cast(value)], sequence, remove);
if (tree[cur].vis_count == 1){
int lson = tree[cur].children[cast(value)];
int rson = tree[cur].children[cast(value) ^ 1];
if (lson != 0 && tree[lson].vis_count != 0)
tree[cur].value = tree[lson].value;
else
tree[cur].value = tree[rson].value;
}
tree[cur].ans = inf;
int lson = tree[cur].children[0], rson = tree[cur].children[1];
if (lson != 0 && tree[lson].vis_count > 1)
tree[cur].ans = min(tree[cur].ans, tree[lson].ans);
if (rson != 0 && tree[rson].vis_count > 1)
tree[cur].ans = min(tree[cur].ans, tree[rson].ans);
if (lson != 0 && rson != 0 && tree[lson].vis_count == 1 && tree[rson].vis_count == 1)
tree[cur].ans = tree[lson].value ^ tree[rson].value;
}else{
tree[cur].ans = inf;
if (tree[cur].vis_count > 1)
tree[cur].ans = 0;
}
}
void remove(int v, const T& sequence) {
insert(v, 0, 0, sequence, true);
}
int get_min(){
return tree.front().ans;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
Trie<array<int, 30>, int> tree(0);
auto tr2bin = [](int x){
array<int, 30> bin{};
for(int i = 0; i < 30; ++ i){
bin[i] = ((x >> (29 - i)) & 1);
}
return bin;
};
int q;
cin >> q;
while(q--){
int op;
cin >> op;
if (op == 1){
int x;
cin >> x;
tree.insert(x, 0, 0, tr2bin(x));
}else if (op == 2){
int x;
cin >> x;
tree.remove(x, tr2bin(x));
}else{
cout << tree.get_min() << '\n';
}
}
return 0;
}
Ex - Make Q (abc308 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码