ABC340

C

黑板上给一个数N，一直不停重复到黑板上的数组里面只剩下1：
擦去每个大于1的数n
加入$\lfloor \frac{n}{2}\rfloor 和\lceil \frac{n}{2}\rceil$
每擦一个数n计入分数n
求最后的总分数

---

用map记录一下每个n的总得分

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;ll n;
map<ll, ll> h;ll get(ll x) {if (h.count(x)) return h[x];if (x == 1) return 0;if (x % 2 == 0) {return h[x] = get(x / 2) * 2 + x;}else {return h[x] = get(x / 2) + get(x / 2 + 1) + x;}
}int main(){//freopen("in.txt", "r", stdin);cin >> n;ll ans = get(n);printf("%lld\n", ans);return 0;
}

D

1…N的一个数组，一开始在格子1
对于格子i有两个操作，一个花费$A_i$到i+1，第二个花费$B_i$到d
求最后到N的最小花费

---

优先队列

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;int n;
int a[200020], b[200020], x[200020];
ll f[200020];
vector<pair<int, ll>> g[200020];struct Node {ll w;int u;bool operator < (const Node& rhs) const {return w > rhs.w;}
};int main(){//freopen("in.txt", "r", stdin);cin >> n;memset(f, 0x33, sizeof(f));f[1] = 0;for (int i = 1; i < n; ++i) {cin >> a[i] >> b[i] >> x[i];g[i].push_back({ x[i], b[i] });g[i].push_back({ i + 1, a[i] });}priority_queue<Node> qu;qu.push({ 0, 1 });while (qu.size()) {auto [w, u] = qu.top();qu.pop();if (u == n) {break;}for (auto [v, tw]: g[u]) {if (w + tw < f[v]) {f[v] = w + tw;qu.push({ f[v], v });}}}printf("%lld\n", f[n]);return 0;
}

E

围成一圈的n个格子，每个格子里都放着$A_i$个球
m个操作，格子$M_i$
将格子里面的球拿出来，按顺序依次放到所有格子里面，每次放一个
求最后每个格子里有几个球

---

对单点更新（清零）–就是区间更新，单点查询，裸的线段树。BIT+差分也可。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;int n, m;
const int N = 200020;
ll a[N];
#define lu (u * 2)
#define ru (u * 2 + 1)struct SegTree {struct Node {int l, r;ll val, add;}tr[N << 2];void push_down(int u) {if (tr[u].add) {tr[lu].add += tr[u].add;tr[ru].add += tr[u].add;tr[u].add = 0;}}public:void build(int l, int r, int u) {tr[u].l = l, tr[u].r = r, tr[u].add = 0;if (l == r) {tr[u].val = a[l];return;}int mi = (l + r) / 2;build(l, mi, lu);build(mi + 1, r, ru);}void update(int l, int r, int u, ll v) {if (l <= tr[u].l && tr[u].r <= r) {tr[u].add += v;return;}push_down(u);int mi = (tr[u].l + tr[u].r) / 2;if (mi >= l)update(l, r, lu, v);if (mi < r) update(l, r, ru, v);}ll query(int p, int u) {if (tr[u].l == tr[u].r) {return tr[u].val + tr[u].add;}push_down(u);int mi = (tr[u].l + tr[u].r) / 2;if (p <= mi) return query(p, lu);else return query(p, ru);}
} seg;int main(){//freopen("in.txt", "r", stdin);cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];seg.build(1, n, 1);for (int i = 0; i < m; ++i) {int t;cin >> t;t++;ll c = seg.query(t, 1);seg.update(t, t, 1, -c);seg.update(1, n, 1, c / n);ll r = c % n;if (r) {if (t + r <= n) {seg.update(t + 1, t + r, 1, 1);}else {if (t < n) {seg.update(t + 1, n, 1, 1);}seg.update(1, r - (n - t), 1, 1);}}}for (int i = 1; i <= n; ++i) {ll c = seg.query(i, 1);printf("%lld ", c);}printf("\n");return 0;
}

F

给(0,0)点和(X,Y)点，求任意（A,B）点使得三角形面积为1

---

三角形面积公式
$x_1{y}_2+x_2{y}_3+x_3{y}_1-x_1{y}_3-x_2{y}_1-x_3{y}_2=S$
化简为$ay-bx=2$
扩展欧几里得做就好了

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;ll X, Y;
// ax - by = 2ll gcd(ll a, ll b) {if (a < b) swap(a, b);if (b == 0) return a;return gcd(b, a % b);
}ll exgcd(ll a, ll b, ll& x, ll& y) {if (b == 0) {x = 1, y = 0;return a;}ll x0, y0;ll d = exgcd(b, a % b, x0, y0);// b x0 + a%b y0 = d// b x0 + (a - (a / b)b) y0 = d// b x0 + a y0 - (a / b) b y0 = d// b(x0 - (a/b) y0) + a y0 = d// by + ax = d// y = x0 - (a/b)y0, x = y0y = x0 - (a / b) * y0, x = y0;return d;
}int main(){//freopen("in.txt", "r", stdin);cin >> X >> Y;ll lx = abs(X), ly = abs(Y);ll d = gcd(lx, ly);if (d > 2) {printf("-1\n");return 0;}ll x, y;exgcd(X, Y, y, x);y = -y;if (d == 1) {printf("%lld %lld\n", x * 2, y * 2);}else {printf("%lld %lld\n", x, y);}return 0;
}