AtCoder Beginner Contest 347
A - Divisible (abc347 A)
题目大意
给定\(n\)个数\(a_i\)以及\(k\)，输出是 \(k\)的倍数的\(a_i\)整除以 \(k\)的值。
解题思路
按照题意判断取模和求整除即可。
神奇的代码
#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, k;
cin >> n >> k;
while (n--) {
int a;
cin >> a;
if (a % k == 0)
cout << a / k << ' ';
}
cout << '\n';
return 0;
}
B - Substring (abc347 B)
题目大意
给定字符串\(s\)，问子串种类数。
解题思路
\(|s|\)只有 \(100\)，直接 \(O(n^2)\)枚举子串丢进 \(set\)里，答案就是 \(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);
string s;
cin >> s;
set<string> ans;
for (int i = 0; i < s.size(); ++i)
for (int j = i; j < s.size(); ++j) {
ans.insert(s.substr(i, j - i + 1));
}
cout << ans.size() << '\n';
return 0;
}
C - Ideal Holidays (abc347 C)
题目大意
一周前\(a\)天假期，后 \(b\)天工作日。
给定 \(n\)天的安排，问第一个安排定在哪天，使得每个安排都在假期。
解题思路
先让安排日期对\(a+b\)取模，剩下的问题就是， \([0,a+b-1]\)数轴上有一堆点，问能否有一个长度为 \(a\)的区间覆盖了所有点。
枚举覆盖的左端点，看与最右边的点的距离是否超过 \(a\)即可。
注意计算\(a+b+d_i\)会超 \(int\)范围。
神奇的代码
#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);
LL n, a, b;
cin >> n >> a >> b;
LL tot = a + b;
vector<LL> d;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
--x;
x %= tot;
d.push_back(x);
d.push_back(x + tot);
}
ranges::sort(d);
LL dis = numeric_limits<LL>::max();
for (int i = 0; i < n; i++) {
dis = min(dis, d[i + n - 1] - d[i] + 1);
}
if (dis <= a)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
D - Popcount and XOR (abc347 D)
题目大意
给定\(a,b,c\)，输出一对 \(x,y\)，满足:
- \(x < 2^{60}, y < 2^{60}\)
- \(popcount(x) = a\)
- \(popcount(y) = b\)
- \(x \oplus y = c\)
\(popcount(x)\)即返回 \(x\)在二进制下\(1\)的个数。 \(\oplus\)是异或。
解题思路
构造题。
假设\(c\)在二进制下 \(1\)的个数为 \(cnt\)。
那么这 \(cnt\)个 \(1\)要分配在 \(x,y\)里。假设分配了 \(l\)个 \(1\)给 \(x\)， \(r\)个 \(1\)给 \(y\)，其中 \(l+r=cnt\)。
此时 \(x\)还剩下 \(a-l\)个 \(1\)， \(y\)还剩下 \(b-r\)个 \(1\)要分配，这些 \(1\)的分配需要在 \(\oplus\)时抵消掉。
所以应有 \(a-l=b-r\)。结合 \(l+r=cnt\)可以解得 \(l,r\)值。
即 \(over=\frac{a+b-cnt}{2}\)是分配给\(x,y\)的 \(1\)，以在 \(\oplus\)时抵消。
剩下的\(a-over\)和 \(b-over\)是分配给 \(x,y\)，以凑成 \(c\)。
因此就逐位遍历 \(c\)，如果是 \(1\)，则分配给 \(x\)或 \(y\)（看\(a,b > 0\)），如果是 \(0\)，则都分配给 \(x,y\)（如果 \(over > 0)\)。
至于无解条件，一个是 \(a+b < c\)，一个是 \(a+b-cnt\)不是偶数，还有的情况难以言说，比如 \(a=60,b=60,cnt=60\)，因为限定了\(x < 2^{60},y < 2^{60}\)，没有多余的位置分配给用于抵消的 \(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 a, b;
LL c;
cin >> a >> b >> c;
int aa = a, bb = b;
auto popcount = [](LL x) {
int ret = 0;
while (x) {
ret += x & 1;
x >>= 1;
}
return ret;
};
int cc = popcount(c);
if (cc > a + b || ((a + b - cc) & 1)) {
cout << -1 << '\n';
return 0;
}
int over = (a + b - cc) / 2;
a -= over;
b -= over;
if (a < 0 || b < 0) {
cout << -1 << '\n';
return 0;
}
LL A = 0, B = 0;
for (int i = 0; i < 60; i++) {
if (c & (1LL << i)) {
if (a) {
A |= 1LL << i;
a--;
} else if (b) {
B |= 1LL << i;
b--;
} else {
assert(0);
}
} else if (over) {
A |= 1LL << i;
B |= 1LL << i;
over--;
}
}
if (popcount(A) != aa || popcount(B) != bb) {
cout << -1 << '\n';
return 0;
}
cout << A << ' ' << B << '\n';
return 0;
}
E - Set Add Query (abc347 E)
题目大意
初始\(n\)个 \(0\)的数组\(a_i\)和空集合\(s\)。进行以下 \(q\)次操作。
每次操作给定一个 \(x\)，
- 如果 \(x\)在集合里，移除它，否则放入它。
- 对于\(j \in s\),\(a_j += |s|\)
解题思路
朴素的模拟的复杂度是\(O(nq)\)，考虑在这个过程，每个操作后，都要遍历一下集合里的元素，给数组\(a\)的对应位置相加。
当一个数\(x\)在集合 \(s\)里时，每个操作之后都会对 \(a_x\)作贡献，直到它被移除集合。
每次操作都计算贡献的话，就是朴素的模拟，复杂度上限就是 \(O(nq)\)。要优化，就不能每次操作算贡献了。
注意到一个数 \(x\)做出的贡献是一个连续的操作区间，贡献值就是这个操作区间的 \(|s|\)的和。那我们可以维护一个关于操作顺序的 \(|s|\)的前缀和\(presum\)，当 \(x\)被移除时，我们就结算它对 \(a_x\)的贡献：就一个前缀和的相减，这里需要记录下\(x\)何时放入的。
操作结束后，再对还在\(s\)里的元素结算下贡献就好了。
神奇的代码
#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<LL> presum;
presum.push_back(0);
set<int> s;
vector<int> la(n, 0);
vector<LL> ans(n, 0);
for (int i = 1; i <= q; ++i) {
int x;
cin >> x;
--x;
if (s.count(x)) {
ans[x] += presum[i - 1] - presum[la[x] - 1];
s.erase(x);
} else {
la[x] = i;
s.insert(x);
}
presum.push_back(presum.back() + s.size());
}
for (auto& i : s) {
ans[i] += presum[q] - presum[la[i] - 1];
}
for (auto& i : ans) {
cout << i << ' ';
}
cout << '\n';
return 0;
}
F - Non-overlapping Squares (abc347 F)
题目大意
给定一个\(n \times n\)的网格，问三个不重叠的 \(m \times m\)的网格覆盖，和的最大值。
解题思路
<++>
神奇的代码
G - Grid Coloring 2 (abc347 G)
题目大意
<++>
解题思路
<++>
神奇的代码