2024 年 syzx 春季训练 1（20240315）
https://www.cnblogs.com/caijianhong/p/18076181
SS240323（20240323）
http://cplusoj.com/d/senior/contest/65fd9320ccaa6dc9eee1e44f
- [A 魔环上的树] 计数，数树，平面图三角剖分
- [B 序列舞蹈] 斜率相关，数据结构
- C 脱单计划 最小费用最大流，曼哈顿距离转化
\(100+100+100=300\)。
冲刺NOI2024联测1（20240329）
http://47.92.197.167:5283/contest/482
- [A 帽子] 序列构造双射的构造题
- [B 我希望你们永远不要用到的洗牌法] 很困难写的分治贪心题
- [C 一路向“北” / CF1621H Trains and Airplanes] 数据结构，整除分段的值
\(10+35(50)+40(30)=85(90)\)。
反思：T1 想错方向了，往相邻颜色上面想（具体见题目），没有发现是一个构造题；T2 的暴力 dp 复杂度写成 \(O(n^4)\) 了，以为是 \(O(n^3)\) 的。然后正解也不是很会，很像省选 D2T1 迷宫守卫，这种贪心题是一个弱点。T3 结束前半小时大概知道怎么做，结果没写完，下午写完了发现有一部分是假的，但是离正解也很近。然后这个 T3 还重写了一遍。
线段树合并新写法
- 定义 static 的数组可以不写括号
- 如果 static 函数与 std 重名（如下面的 merge），需要指明
int T;
struct segtree {
static constexpr int N = 200010 << 6;
static int ch[N + 10][2], tot, ans[N + 10];
static void maintain(int p) { ans[p] = ans[ch[p][0]] + ans[ch[p][1]]; }
static void insert(int x, int k, int &p, int l, int r) {
if (!p) p = ++tot;
if (l == r) return ans[p] += k, void();
int mid = (l + r) >> 1;
if (x <= mid)
insert(x, k, ch[p][0], l, mid);
else
insert(x, k, ch[p][1], mid + 1, r);
maintain(p);
}
static int merge(int p, int q, int l, int r) {
if (!p || !q) return p + q;
int z = ++tot;
if (l == r) return ans[z] = ans[p] + ans[q], z;
int mid = (l + r) >> 1;
ch[z][0] = merge(ch[p][0], ch[q][0], l, mid);
ch[z][1] = merge(ch[p][1], ch[q][1], mid + 1, r);
maintain(z);
return z;
}
static int query(int L, int R, int p, int l, int r) {
if (!p) return 0;
if (L <= l && r <= R) return ans[p];
int mid = (l + r) >> 1;
int ret = 0;
if (L <= mid) ret += query(L, R, ch[p][0], l, mid);
if (mid < R) ret += query(L, R, ch[p][1], mid + 1, r);
return ret;
}
int root = 0;
void insert(int x, int k) { insert(x, k, root, 0, T - 1); }
static segtree merge(segtree a, segtree b) {
return {merge(a.root, b.root, 0, T - 1)};
}
int query(int L, int R) { return query(L, R, root, 0, T - 1); }
int qall() { return query(0, T - 1, root, 0, T - 1); }
};
int segtree::ch[][2], segtree::tot, segtree::ans[];
int n, Q, K, col[200010];
vector<pair<int, int>> g[200010];
segtree t[200010][26];
int top[200010];
LL det[200010], f[26], w[26];
void dfs(int u, int fa, int topf) {
top[u] = topf;
t[u][col[u]].insert((det[u] - 1) % T, 1);
for (auto e : g[u]) {
int v = e.first, w = e.second;
if (v == fa) continue;
if (col[v] == col[u])
det[v] = det[u] + w, dfs(v, u, topf);
else
det[v] = w, dfs(v, u, u);
for (int j = 0; j < K; j++) t[u][j] = segtree::merge(t[u][j], t[v][j]);
}
}
原来以为是单点的，写的 dsu on tree。大家可以欣赏一下狗屎 shared_ptr 代码。其实线段树更好写更短。
struct dsuontree {
int me;
int buc[200010], tot, rsz[200010];
vector<pair<int, shared_ptr<int>>> qry[200010];
map<int, int> mp;
shared_ptr<int> ask(int u, int T) {
if (T >= 0) {
shared_ptr<int> ansp = make_shared<int>(-1);
if (!mp.count(T)) {
int t = mp.size();
mp[T] = t;
}
qry[u].emplace_back(mp[T], ansp);
return ansp;
} else {
return shared_ptr<int>(&rsz[u], [](int*) {});
}
}
void dfs(int u, int fa, int ban, int k) {
if (col[u] == me && det[u] >= 0)
buc[det[u]] += k, tot += k;
for (auto e : g[u]) {
int v = e.first;
if (v == fa || v == ban)
continue;
dfs(v, u, ban, k);
}
}
void solve(int u, int fa, bool keep) {
if (col[u] == me)
det[u] = mp.count(det[u] % T) ? mp[det[u] % T] : -1, rsz[u] = 1;
for (auto e : g[u]) {
int v = e.first;
if (v == fa || v == son[u])
continue;
solve(v, u, false);
rsz[u] += rsz[v];
}
if (son[u])
solve(son[u], u, true), rsz[u] += rsz[son[u]];
dfs(u, fa, son[u], 1);
for (auto q : qry[u]) *q.second = buc[q.first];
if (!keep)
dfs(u, fa, 0, -1);
}
} robot[26];
struct func {
map<int, LL> mp; // record delta
map<int, shared_ptr<int>> ques;
shared_ptr<int> all;
LL gen = 0;
void askall(int me, int u) {
for (auto e : mp) ques[e.first] = robot[me].ask(u, e.second);
all = robot[me].ask(u, -1);
}
LL answer() {
int gall = *all;
for (auto e : ques) gall -= *e.second;
if (gall)
return gen;
LL mn = 1e18;
for (auto e : ques) {
if (*e.second)
mn = min(mn, mp[e.first]);
}
return mn + gen;
}
};