AtCoder Beginner Contest 318
咕咕咕，总力战还没打，凹不过卷狗，躺了.jpg
A - Full Moon (abc318 A)
题目大意
给定\(n, m, p\)，问有多少个 \(i\)满足 \(0 < m+pi \leq n\)
解题思路
减去初始的\(m\)，剩下的就是看 \(p\)的倍数个数。
神奇的代码
#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, p;
cin >> n >> m >> p;
cout << (n - m) / p + (n >= m) << '\n';
return 0;
}
B - Overlapping sheets (abc318 B)
题目大意
一个二维空间，有\(n\)个矩形覆盖。
问有多大的空间被覆盖了。重复覆盖算一次。
解题思路
空间大小只有\(100\)，矩形只有 \(100\)，对每个矩形直接 \(O(100^2)\)更新格子的覆盖情况，最后统计被覆盖的个数即可。
时间复杂度为 \(O(100^3)\)。
神奇的代码
#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;
array<array<int, 101>, 101> tu{};
while (n--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
for (int i = a; i < b; ++i)
fill(tu[i].begin() + c, tu[i].begin() + d, 1);
}
int ans = 0;
for (auto& i : tu)
ans += count(i.begin(), i.end(), 1);
cout << ans << '\n';
return 0;
}
C - Blue Spring (abc318 C)
题目大意
\(n\)天旅行，第 \(i\)天旅行花费 \(f_i\)元。
你可以购买一日游券，可以免去任意一天的旅游费用。
但是一日游券是捆绑售卖的，你需要花 \(p\)元买 \(d\)张 一日游券。这意味着你可以免去任意\(d\)天的旅游费用。你可以购买多次，最后一日游券可以剩余。
问旅游完 \(n\)天所需要的最小费用。
解题思路
假设我购买了\(x\)张一日游券，我肯定是免去旅游费用最高的那 \(x\)天的费用。
那就直接枚举买多少次一日游券，用于免去最高的旅游费用，然后其费用与剩余天数的费用相加求个最小值即可。
神奇的代码
#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, d, p;
cin >> n >> d >> p;
vector<int> f(n);
for (auto& i : f)
cin >> i;
sort(f.begin(), f.end(), greater<int>());
LL sum = accumulate(f.begin(), f.end(), 0ll);
LL ans = sum;
for (int i = 0; i < n; i += d) {
for (int j = i; j < min(n, i + d); ++j)
sum -= f[j];
sum += p;
ans = min(ans, sum);
}
cout << ans << '\n';
return 0;
}
D - General Weighted Max Matching (abc318 D)
题目大意
给定一张无向图，边有边权。要求选择一些边，最大化边权和，使得每条边的顶点不重复。
解题思路
点数只有\(16\)，考虑到每条边的顶点不能重复，那么当我们考虑某条边能不能选时，必须得知道目前已经选了哪些点，以决定这条边能不能选，因此设 \(dp[i]\)表示选择的点的情况是 \(i\)（二进制压缩的状态，0表示不选，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;
cin >> n;
vector<vector<int>> edge(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
int x;
cin >> x;
edge[i].push_back(x);
}
}
vector<LL> dp((1 << n), 0);
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if ((~i >> j) & 1)
continue;
for (int k = j + 1; k < n; ++k) {
if ((~i >> k) & 1)
continue;
int w = edge[j][k - j - 1];
dp[i] = max(dp[i], dp[i ^ (1 << j) ^ (1 << k)] + w);
}
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
E - Sandwiches (abc318 E)
题目大意
给定一个\(n\)个数的数组 \(a\)，问有多少个 \((i, j, k)\)，满足
- \(i < j < k\)
- \(a_i = a_k\)
- \(a_i \neq a_k\)
解题思路
由于数有\(10^5\)，我们只能枚举其中一个。要么枚举 \(i\)要么枚举 \(j\)。分别考虑后发现枚举 \(j\)简单一点。
如果枚举下标\(i\)会发现比较难计算，对于当前的 \(a_i\)，那么对于之后的每个 \(a_k\)都要考虑它们之间的其他数的个数，感觉复杂度会比较大。
考虑枚举下标\(j\)，剩下的就是考虑 \(j\)左边和 \(j\)右边的相同数。这个\(j\)对答案的贡献就是 \(\sum_{x \neq a_j} l_{x} \times r_{x}\)，其中 \(l_x\)表示 \(j\)左边 \(x\)（是值，不是下标）的个数， \(r_x\)就是右边的 \(x\)的个数。
考虑当 \(j\)移动时，只有 \(a_j\)和 \(a_{j + 1}\)这两个数的个数发生变化。因此我们事先维护 \(\sum\)的值，\(\sum - l_{a_j} \times r_{a_j}\)就是此时的 \(j\)对答案的贡献。转移时通过加减那两个数的贡献，就得到 \(j\)移动到下一个数时的 \(\sum\)的值。然后累计就是答案了。
神奇的代码
#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);
vector<int> l(n, 0), r(n, 0);
for (auto& i : a) {
cin >> i;
--i;
r[i]++;
}
LL ans = 0;
LL tmp = 0;
for (int i = 0; i < n; ++i) {
tmp -= 1ll * l[a[i]] * r[a[i]];
r[a[i]]--;
ans += tmp;
l[a[i]]++;
tmp += 1ll * l[a[i]] * r[a[i]];
}
cout << ans << '\n';
return 0;
}
F - Octopus (abc318 F)
题目大意
给定\(n\)个宝藏的位置，以及\(n\)只长度为 \(l_i\)的手。你要求合法的位置的个数。
一个位置\(x\)合法，意味着你可以用\(n\)只手拿到 \(n\)个宝藏。一只手只能拿一个宝藏，且拿的范围为 \([x - l_i, x + l_i]\)。
解题思路
考虑合法位置的情况，分三种，最左边，最右边，以及两个宝藏之间。
然后考虑最左边的种类，很显然，我们对手的长度进行从小到大排序，那就根据宝藏的坐标从小到大分配手。即对于第\(i\)个宝藏，分配的是长度为 \(l_i\)的手，那么能够及该宝藏的最左边的距离就是 \(x_i - l_i\)，对该距离取个最大值，就是最左边的合法位置了。
然后考虑这个合法位置不断往右边移动，在到达第一个宝藏的位置前都是合法位置。
然后合法位置到了第一个宝藏和第二个宝藏之间。考虑在这区间移动，我们的手分配宝藏的方案是不变的，直到第二个宝藏距离当前位置比第一个位置更近时，分配方案才发生变化，需要重新计算。
注意到需要重新计算的情况，是宝藏距离当前位置的排名发生了变化，因此手分配宝藏的方案需要改变，重新计算当前位置的合法性。而排名发生变化的位置被称为关键位置。
考虑这些关键位置在哪，既然是排名发生变化，那就是在某两个宝藏的中点，因此枚举左右两边宝藏，求个中点就能得到这些关键位置，注意到关键位置的数量只有\(O(n^2)\)个。
对于每个关键位置，重新计算下各个宝藏到该位置的距离，然后排个序分配手，在区间[当前关键位置，下一个关键位置-1]，其手的分配方案都不变，此时对于左边的宝藏，会有一个最小值 \(L = x_i + l_i\)，而对于右边的宝藏，会有个最大值 \(R = x_i - l_i\)，这之间的[R, L]就是合法位置的区间。
因此对所有这样的关键位置累计\(L - R + 1\)的值就是答案。总的时间复杂度是 \(O(n^3 \log n)\)。
神奇的代码
#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<LL> x(n), l(n);
for (auto& i : x)
cin >> i;
for (auto& i : l)
cin >> i;
LL ans = 0;
LL L = numeric_limits<LL>::min(), R = numeric_limits<LL>::max();
for (int i = 0; i < n; ++i) {
L = max(L, x[i] - l[i]);
R = min(R, x[i] + l[n - i - 1]);
}
ans += max(0ll, x[0] - L);
ans += max(0ll, R - x[n - 1] + 1);
vector<int> id(n);
vector<int> rk(n);
iota(id.begin(), id.end(), 0);
for (int i = 0; i < n - 1; ++i) {
vector<LL> div{x[i]};
for (int j = 0; j <= i; ++j) {
for (int k = i + 1; k < n; ++k) {
LL mid = (x[j] + x[k] + 1) / 2;
if (mid > x[i] && mid < x[i + 1])
div.push_back(mid);
}
}
sort(div.begin(), div.end());
div.push_back(x[i + 1]);
for (int k = 0; k < div.size() - 1; ++k) {
LL mid = div[k];
vector<LL> pos(n);
for (int j = 0; j < n; ++j) {
pos[j] = abs(x[j] - mid);
}
sort(id.begin(), id.end(), [&](int a, int b) {
if (pos[a] != pos[b])
return pos[a] < pos[b];
else
return a > b;
});
for (int j = 0; j < n; ++j)
rk[id[j]] = j;
L = div[k + 1] - 1, R = div[k];
for (int j = 0; j <= i; ++j) {
L = min(L, x[j] + l[rk[j]]);
}
for (int j = i + 1; j < n; ++j)
R = max(R, x[j] - l[rk[j]]);
ans += max(0ll, L - R + 1);
}
}
cout << ans << '\n';
return 0;
}
其实上面想复杂了（其实写也写复杂了，其实可以直接\(O(n^2)\)，枚举宝藏求中点，然后遍历所有关键点，上述这么写是因为当时考虑的每两个宝藏之间的情况，所以就一段一段的），不过是一个很朴素的从特殊位置开始的思路。
还是考虑关键位置，这个关键位置可以是两个宝藏的中点，它们的距离排名发生了变化；也可以是某个宝藏使用某只手的极限位置（即\(x_i - l_j\)和\(x_i + l_j\)，以这些极限距离作为分割点\(div_i\)，分别考虑每个分割点是否合法（同上面一样距离排序然后分配手），如果可以则代表 \([div_i, div_{i+1} - 1]\)都可以。可以参考jiangly的代码，但是正确性不太能理解，因为是以最优分配方式判断合法性，能保证这个区间都能取到最优方案吗（？
G - Typical Path Problem (abc318 G)
题目大意
给定一张简单无向图，问是否存在一个简单路径，从点\(a\)出发经过点 \(b\)到达点 \(c\)。
解题思路
题目可以转化成是否存在一棵生成树，其根为\(b\)，点 \(a\)和点 \(c\)的 \(lca\)是根，然后就一直在研究生成树，就不会了
神奇的代码
Ex - Count Strong Test Cases (abc318 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码