10.25
这场神秘场。
t1 简单题，t2 虽然没做出来但其实不难，t3 是折半警报器（新trick） ，t4 是李超树合并板题（甚至小样例都一样）。
神秘原因其实不在题上（你只能说这个 t4 水），数据过于抽象了。
t2 卡常，但t3,t4 原数据都放暴力过了。
就是说这场哪怕 t1 都不会然后狂打暴力都有200,可以A掉 t3,t4 。
显然赛后全杀了。
t1
最小生成树，但是连边为区间连边。
我的做法是直接上线段树维护区间信息。
简单题。
code:
锵锵
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m, siz;
long long sum;
struct edge
{int l, r, val;
} e[N];
int fa[N];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline bool cmp(edge a, edge b) { return a.val < b.val; }struct tree
{int l, r;int fa;
} t[N << 2];
#define lid (id << 1)
#define rid (id << 1 | 1)void build(int id, int l, int r)
{t[id].l = l, t[id].r = r;if (l == r){t[id].fa = t[id].l;return;}int mid = (l + r) >> 1;build(lid, l, mid);build(rid, mid + 1, r);t[id].fa = (t[lid].fa == t[rid].fa ? t[lid].fa : -1);
}inline void update(int id, int l, int r, int x, int f)
{if (t[id].fa == f)return;if (t[id].l == t[id].r){int fv = find(t[id].l);t[id].fa = fv;if (fv == f)return;fa[fv] = f;t[id].fa = f;++siz;sum += x;if (siz == n - 1){cout << sum;exit(0);}return;}int mid = (t[id].l + t[id].r) >> 1;if (mid >= l)update(lid, l, r, x, f);if (mid < r)update(rid, l, r, x, f);t[id].fa = (t[lid].fa == t[rid].fa ? t[lid].fa : -1);
}signed main()
{freopen("tree.in", "r", stdin);freopen("tree.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i)fa[i] = i;for (int i = 1, l, r, x; i <= m; ++i){cin >> l >> r >> x;e[i] = {l, r, x};}sort(e + 1, e + 1 + m, cmp);build(1, 1, n);for (int i = 1; i <= m; ++i){int u = e[i].l;update(1, e[i].l, e[i].r, e[i].val, find(u));}cout << -1;return 0;
}
t2
最短路，但是边权魔改。
其实也比较容易，观察到边权是否更改只和上一条边的 \(a\) 值有关，开个数组记录，若 \(a\) 和 \(dis\) 均大，则显然不优，剩下暴力转移即可。
发现每条边至多被松弛两次：第一次是第一次经过，第二次是被任意一条 \(a\) 值更小的边经过。
所以时间复杂度是对的。
这题教会我用 tuple 了
code:
噔噔
#include <bits/stdc++.h>
#define int long long
#define ter tuple<int, int, int>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1e16;
int n, m;
int ans[N], lasa[N];
vector<ter> e[N];
priority_queue<ter, vector<ter>, greater<ter>> q;inline bool cmp(ter a, ter b) { return get<1>(a) < get<1>(b); }inline int fen(int id, int a)
{// cout << "id=" << id << " a=" << a << "\n";if (e[id].empty())return 1;// if (a > get<1>(e[id][e[id].size() - 1]))// return e[id].size();int l = 0, r = e[id].size(), ans = r;while (l <= r){int mid = (l + r) >> 1;// cout << "l=" << l << " r=" << r << " mid=" << mid << " ans=" << ans << "\n";if (get<1>(e[id][mid]) > a)r = mid - 1, ans = mid;elsel = mid + 1;}// cout << "ans=" << ans << "\n";return ans;
}inline void dij(int op)
{for (int i = 1; i <= n; ++i)ans[i] = lasa[i] = inf;ans[1] = 0;q.push({0, inf - 1, 1});while (q.size()){int dis, au, u;tie(dis, au, u) = q.top();q.pop();// cerr << "u=" << u << " au=" << au << " lasa=" << lasa[u] << "\n";ans[u] = min(ans[u], dis);if (au >= lasa[u])continue;// cerr << "!!u=" << u << "\n";if (lasa[u] == inf){for (auto y : e[u]){int v, a, b;tie(v, a, b) = y;q.push({dis + (au < a ? a - b : a), a, v});}}else{int pos = fen(u, au);// cerr << "pos=" << pos << "\n";for (int i = pos; i < e[u].size(); ++i){int v, a, b;tie(v, a, b) = e[u][i];if (a > lasa[u])break;q.push({dis + (au < a ? a - b : a), a, v});}}lasa[u] = au;}
}signed main()
{freopen("roads.in", "r", stdin);freopen("roads.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 1, u, v, a, b; i <= m; ++i){cin >> u >> v >> a >> b;e[u].emplace_back((ter){v, a, b});}for (int i = 1; i <= n; ++i)sort(e[i].begin(), e[i].end(), cmp);dij(1);for (int i = 1; i <= n; ++i)cout << (ans[i] == inf ? -1 : ans[i]) << ' ';return 0;
}
t3
赛时盯半天，最后打了个暴力创飞了。
trick:折半警报器。
鬼街弱化版（其实还有更强的二进制警报器，但是过于困难看不懂）。
做完鬼街就会了，所以不多讲（不会先去做那道）。
code:
嘻嘻哈哈
#include <bits/stdc++.h>
#define pir pair<int, int>
#define fi first
#define se second
#define emp emplace_back
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, tot, lasans;struct node
{int id, dep, lim;friend bool operator<(node a, node b) { return a.lim > b.lim; }
};
priority_queue<node> q[N];
vector<int> e[N];
int cnt[N], cnt_dep[N];
bool vis[N];
int Lim[N];inline int get_val(int x)
{int sum = 0;for (auto y : e[x])sum += cnt[y];return sum;
}inline void solve1()
{++tot;int y, k, p;cin >> y >> k;y ^= lasans;for (int i = 1; i <= k; ++i){cin >> p;p ^= lasans;e[tot].emp(p);}++cnt_dep[tot];int up = (y - 1) / k + 1;int sum = 0;for (auto i : e[tot])q[i].push({tot, 1, up + cnt[i]}), sum += cnt[i];Lim[tot] = y + sum;
}inline void solve2()
{vector<int> ans;int x, y;cin >> x >> y;x ^= lasans, y ^= lasans;cnt[x] += y;for (int k = max(1ll, x - 2); k <= min(n, x + 2); ++k){while (q[k].size() && q[k].top().lim <= cnt[k]){node x = q[k].top();q[k].pop();if (vis[x.id]) // 被删过continue;if (cnt_dep[x.id] != x.dep) // 懒惰删除continue;int val = get_val(x.id);if (val >= Lim[x.id]) // 超过阈值vis[x.id] = 1, ans.emp(x.id);else{int nup = (Lim[x.id] - val - 1) / e[x.id].size() + 1; // 上取整++cnt_dep[x.id];for (auto j : e[x.id])q[j].push({x.id, cnt_dep[x.id], nup + cnt[j]});}}}lasans = ans.size();sort(ans.begin(), ans.end());cout << lasans << ' ';for (auto y : ans)cout << y << ' ';cout << "\n";
}signed main()
{freopen("mission.in", "r", stdin);freopen("mission.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;int opt;while (m--){cin >> opt;if (opt == 1)solve1();elsesolve2();}return 0;
}
t4
李超线段树模板题+原题。
CF932F Escape Through Leaf
赛时没搓出来。
code:
板
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, L = -1e5 - 10, R = 1e5 + 10;
const int inf = LLONG_MAX;
int n;
vector<int> e[N];
int a[N], b[N], rt[N];
int K[N], B[N], tot;
struct tree
{int l, r;int dat;
} t[N << 2];
#define lid t[id].l
#define rid t[id].rinline int calc(int id, int x) { return K[id] * x + B[id]; }inline void insert(int &id, int l, int r, int x)
{if (!id)id = ++tot;if (!t[id].dat){t[id].dat = x;return;}int &y = t[id].dat;int mid = (l + r) >> 1;if (calc(x, mid) < calc(y, mid))swap(x, y);if (calc(x, l) < calc(y, l))insert(lid, l, mid, x);if (calc(x, r) < calc(y, r))insert(rid, mid + 1, r, x);
}inline int query(int id, int l, int r, int x)
{if (!id)return inf;int ans = calc(t[id].dat, x);if (l == r)return ans;int mid = (l + r) >> 1;if (mid >= x)return min(ans, query(lid, l, mid, x));elsereturn min(ans, query(rid, mid + 1, r, x));
}inline int merge(int l, int r, int x, int y)
{if (!x || !y)return x | y;if (l == r)return calc(t[x].dat, l) > calc(t[y].dat, l) ? y : x;int mid = (l + r) >> 1;t[x].l = merge(l, mid, t[x].l, t[y].l);t[x].r = merge(mid + 1, r, t[x].r, t[y].r);insert(x, l, r, t[y].dat);return x;
}inline void dfs(int x, int f)
{int cnt = 0;for (auto y : e[x]){if (y == f)continue;++cnt;dfs(y, x);rt[x] = merge(L, R, rt[x], rt[y]);}K[x] = b[x];if (cnt)B[x] = query(rt[x], L, R, a[x]);elseB[x] = 0;insert(rt[x], L, R, x);
}signed main()
{// freopen("ture.in", "r", stdin);// freopen("ture.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0); cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i <= n; ++i)cin >> b[i];for (int i = 1, u, v; i < n; ++i){cin >> u >> v;e[u].emplace_back(v);e[v].emplace_back(u);}dfs(1, 0);for (int i = 1; i <= n; ++i)cout << B[i] << ' ';return 0;
}