AtCoder Beginner Contest 340
A - Arithmetic Progression (abc340 A)
题目大意
给定等差数列的首项、末项、公差。
输出这个等差数列。
解题思路
从首相依次累加公差到末项即可。
神奇的代码
#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, d;
cin >> a >> b >> d;
while (a <= b) {
cout << a << ' ';
a += d;
}
cout << '\n';
return 0;
}
B - Append (abc340 B)
题目大意
依次进行\(Q\)次操作，分两种。
1 x，将x放到数组\(a\)的末尾。2 k，输出数组\(a\)的倒数第 \(k\)项。
解题思路
用vector模拟即可，操作2可快速寻址访问。
神奇的代码
#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 q;
cin >> q;
vector<int> a;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
a.push_back(x);
} else {
int k;
cin >> k;
cout << a[a.size() - k] << '\n';
}
}
return 0;
}
C - Divide and Divide (abc340 C)
题目大意
黑板一个数\(x\)，依次进行以下操作，直到黑板上的数全是\(1\)。
- 将 \(x\)擦去，写上 \(\lfloor x \rfloor\)和 \(\lceil x \rceil\)，耗费 \(x\)精力。
问最后耗费精力的和。
解题思路
朴素做法就一个简单的队列模拟即可。
但这会超时，因为对于同一个数可能会出现多次，而上述做法会对每个数都进行一次操作，这样之后的数的个数是指数增长的。
如何优化呢？那就是对于出现多次的同一个数，我们一次全部做完。
即记录\(cnt[x]\)表示黑板上 \(x\) 的出现次数，然后我们分解它，\(cnt[\lfloor x \rfloor] += cnt[x], cnt[\lceil x \rceil] += cnt[x]\)。为了不重复分解，每次取最大的数进行分解即可。
感觉上这样分解的次数不会超过 \(O(\log)\)或者 \(O(\log^2)\) 次。
神奇的代码
#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;
cin >> n;
set<LL> team;
map<LL, LL> cnt;
cnt[n] = 1;
team.insert(n);
LL ans = 0;
while (!team.empty()) {
LL u = *team.rbegin();
if (u == 1)
break;
team.erase(u);
if (cnt[u] > 0) {
ans += u * cnt[u];
team.insert(u / 2);
cnt[u / 2] += cnt[u];
team.insert(u - u / 2);
cnt[u - u / 2] += cnt[u];
cnt[u] = 0;
}
}
cout << ans << '\n';
return 0;
}
D - Super Takahashi Bros. (abc340 D)
题目大意
\(n\)个关卡，初始只能打第一关卡。
对于第 \(i\)关卡，可以花 \(a_i\)代价解锁第 \(i+1\)关卡，或花 \(b_i\)代价解锁第 \(x_i\)关卡。
问解锁第 \(n\)关卡的最小代价。
解题思路
虽然说是解锁，但很显然打的下一关肯定是刚刚解锁的关卡。
根据上述解锁关系建一张图，边权就是解锁代价，原问题就是问点\(1\)到点 \(n\)的最短距离，跑一遍 dijkstra即可。
神奇的代码
#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<array<int, 2>>> edge(n);
for (int i = 0; i < n - 1; ++i) {
int a, b, d;
cin >> a >> b >> d;
--d;
edge[i].push_back({i + 1, a});
edge[i].push_back({d, b});
}
priority_queue<array<LL, 2>, vector<array<LL, 2>>, greater<array<LL, 2>>>
pq;
vector<LL> dis(n, 1e18);
dis[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dis[u])
continue;
for (auto [v, w] : edge[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
cout << dis[n - 1] << endl;
return 0;
}
E - Mancala 2 (abc340 E)
题目大意
\(n\)个盒子，第 \(i\)个盒子有 \(a_i\)个球。
依次进行以下 \(m\)次操作：
- 第 \(i\)次操作，将第 \(b_i\)个盒子的所有球均分，多余的球从第\(b_i + 1\)个盒子依次放一个。
问最后每个盒子的球数量。
解题思路
朴素做法为\(O(nm)\)，考虑优化每次操作的复杂度。
注意到均分和放一个都是区间加法，用线段树维护即可，时间复杂度是\(O(m\log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 10;
class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
public:
LL sum[N << 2];
LL lazy[N << 2];
void build(int root, int l, int r, vector<int>& a) {
if (l == r) {
sum[root] = a[l - 1];
lazy[root] = 0;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a);
build(rson, mid + 1, r, a);
lazy[root] = 0;
}
void pushdown(int root) {
if (lazy[root]) {
sum[lson] += lazy[root];
sum[rson] += lazy[root];
lazy[lson] += lazy[root];
lazy[rson] += lazy[root];
lazy[root] = 0;
}
}
void update(int root, int l, int r, int L, int R, LL val) {
if (L <= l && r <= R) {
sum[root] += val;
lazy[root] += val;
return;
}
pushdown(root);
int mid = (l + r) >> 1;
if (L <= mid)
update(lson, l, mid, L, R, val);
if (R > mid)
update(rson, mid + 1, r, L, R, val);
}
LL query(int root, int l, int r, int pos) {
if (l == r) {
return sum[root];
}
pushdown(root);
int mid = (l + r) >> 1;
if (pos <= mid)
return query(lson, l, mid, pos);
else
return query(rson, mid + 1, r, pos);
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto& i : a)
cin >> i;
sg.build(1, 1, n, a);
for (int i = 0; i < m; ++i) {
int b;
cin >> b;
++b;
LL cnt = sg.query(1, 1, n, b);
sg.update(1, 1, n, b, b, -cnt);
LL div = cnt / n;
if (div)
sg.update(1, 1, n, 1, n, div);
LL mo = cnt % n;
if (mo) {
if (b + mo <= n) {
sg.update(1, 1, n, b + 1, b + mo, 1);
} else {
sg.update(1, 1, n, b + 1, n, 1);
sg.update(1, 1, n, 1, mo - (n - b), 1);
}
}
}
for (int i = 1; i <= n; ++i) {
cout << sg.query(1, 1, n, i) << " \n"[i == n];
}
return 0;
}
F - S = 1 (abc340 F)
题目大意
给定点\((x_0, y_0)\)，求一整数点 \((a,b)\)，使得 \((0,0), (a, b), (x_0,y_0)\) 形成的三角形的面积为\(1\)。
解题思路
考虑将\((0,0) \to (x_0,y_0)\) 作为三角形的底，高的长度\(h\) 需满足\(\frac{1}{2} h \sqrt{x_0^2 + y_0^2} = 1\)
即将直线\((0,0) \to (x_0,y_0)\) 平移一下，距离其为\(h\)的直线即为 \((a,b)\)所处的位置。
直线 \((0,0) -> (x_0,y_0)\) 的直线方程为\(y_0 x - x_0 y = 0\)
根据两平行直线的方程，得\((a,b)\)所处的直线为 \(y_0 x - x_0 y + c = 0\)。
根据俩平行直线距离公式，得其距离为\(\frac{|c|}{\sqrt{x_0^2 + y_0^2}}\)，其为三角形的高 \(h\)，代入上述公式得 \(|c| = 2\)。
因此得到了 \((a,b)\)所处的直线方程为 \(y_0 x - x_0 y + 2 = 0\)以及\(y_0 x - x_0 y - 2 = 0\) 。
现在的问题就是找到一组整数解\((x,y)\)，满足上述方程。
注意到上述即为一个不定方程，用扩展欧几里德解得即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template <typename T> T extgcd(T a, T b, T& x, T& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T p = b / a;
T g = extgcd(b - p * a, a, y, x);
x -= p * y;
return g;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL a, b;
cin >> a >> b;
auto ok = [](LL a, LL b) {
LL x, y;
LL d = extgcd(b, a, x, y);
if (2 % d != 0) {
return false;
}
cout << x * 2 / d << ' ' << y * 2 / d << '\n';
return true;
};
if (!ok(-a, b) && !ok(a, -b))
cout << "-1\n";
return 0;
}
G - Leaf Color (abc340 G)
题目大意
给定一棵树，点有颜色。
问子树的数量，其叶子颜色相同。
解题思路
<++>
神奇的代码