T1：Arithmetic Progression
模拟
代码实现
a, b, d = map(int, input().split())
for i in range(a, b+1, d):
print(i, end=' ')
T2：Append
模拟
代码实现
q = int(input())
a = []
for qi in range(q):
type, x = map(int, input().split())
if type == 1:
a.append(x)
else:
print(a[-x])
T3：Divide and Divide
记忆化搜索
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n;
cin >> n;
unordered_map<ll, ll> memo;
auto f = [&](auto& f, ll x) -> ll {
if (x == 1) return 0;
if (memo.count(x)) return memo[x];
ll res = f(f, x/2) + f(f, x-x/2) + x;
return memo[x] = res;
};
cout << f(f, n) << '\n';
return 0;
}
T4：Super Takahashi Bros.
注意到由于图可能不是dag，所以不能dp
考虑对点 \(i\) 到点 \(i+1\) 连一条有向边且边权为 \(A_i\)，再对点 \(i\) 到点 \(X_i\) 连一条有向边且边权为 \(B_i\)，这样就得到了一张带权有向图，所以直接跑一遍最短路就能得到答案
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
struct Edge {
int to, cost;
Edge() {}
Edge(int to, int cost): to(to), cost(cost) {}
};
int main() {
int n;
cin >> n;
vector<vector<Edge>> g(n);
rep(i, n-1) {
int a, b, x;
cin >> a >> b >> x;
--x;
g[i].emplace_back(i+1, a);
g[i].emplace_back(x, b);
}
const ll INF = 1e18;
vector<ll> dist(n, INF);
using P = pair<ll, int>;
priority_queue<P, vector<P>, greater<P>> q;
dist[0] = 0;
q.emplace(0, 0);
while (q.size()) {
auto [d, v] = q.top(); q.pop();
if (dist[v] != d) continue;
for (auto e : g[v]) {
ll nd = d+e.cost;
if (nd >= dist[e.to]) continue;
dist[e.to] = nd;
q.emplace(nd, e.to);
}
}
cout << dist[n-1] << '\n';
return 0;
}
T5：Mancala 2
- 区间更新
- 单点求值
可以用线段树或树状数组来做
树状数组的话，可以用差分来实现区间更新，用前缀和来实现单点求值
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
fenwick_tree<ll> d(n+1);
auto add = [&](int l, int r, ll x) {
d.add(l, x);
d.add(r, -x);
};
rep(i, n) {
int a;
cin >> a;
add(i, i+1, a);
}
rep(i, m) {
int b;
cin >> b;
ll x = d.sum(0, b+1);
add(b, b+1, -x);
ll c = x/n; x %= n;
add(0, n, c);
b++;
if (b+x < n) {
add(b, b+x, 1);
}
else {
add(b, n, 1);
add(0, b+x-n, 1);
}
}
rep(i, n) {
ll ans = d.sum(0, i+1);
cout << ans << ' ';
}
return 0;
}
T6：S = 1
由向量积的知识可知，三角形的面积等于 \(\frac{|BX-AY|}{2}\)，得到 \(|BX-AY| = 2\)，于是就转成了扩欧的板题
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// ai+bj=g
ll extgcd(ll a, ll b, ll& i, ll& j) {
if (b == 0) { i = 1; j = 0; return a; }
ll p = a/b, g = extgcd(b, a-b*p, j, i);
j -= p*i;
return g;
}
int main() {
ll x, y;
cin >> x >> y;
ll a, b;
ll g = extgcd(x, y, b, a);
a = -a;
if (2%g) {
puts("-1");
return 0;
}
a *= 2/g; b *= 2/g;
cout << a << ' ' << b << '\n';
return 0;
}