题意
给定一颗以 1 1 1 为根的树,每条边都有边权 w i w_i wi,经过一条边的花费为边的边权 。
你可以多次使用“魔法”,对于两个节点 u , v u,v u,v 如果 ∣ d e p [ u ] − d e p [ v ] ∣ = k |dep[u]−dep[v]|=k ∣dep[u]−dep[v]∣=k (深度之差为 k k k ),那么只需要花费 p p p 就可以从 u u u 到 v v v ,或者从 v v v 到 u u u 。
求从点 s s s 到点 t t t 的最小花费。
思路
如果暴力对所有 i i i 和 i + k i+k i+k 层的点都建双向边,边数太多会超时。
考虑每 k k k 层建两个虚拟节点。
假设第 i i i 层与第 i + k i+k i+k 层的两个虚拟结点是 a 1 , a 2 a_{1},a_{2} a1,a2,
第 i i i 层的所有点都指向 a 1 a_{1} a1,权值为 0 0 0; a 1 a_1 a1 指向第 i + k i+k i+k 层的所有点,权值为 p p p.
第 i + k i+k i+k 层的所有点都指向 a 2 a_{2} a2,权值为 0 0 0; a 2 a_2 a2 指向第 i i i 层的所有点,权值为 p p p.
#include1010 - Bragging Diceusing namespace std; #define endl 'n' //#define int long long typedef pair PII; typedef long long ll; const int N = 3000010, M = 2 * N; const ll INF = 0x3f3f3f3f3f3f3f3f; int n, k, p, s, t, maxdep; int h[N], e[M], ne[M], w[M], idx; ll dis[N]; bool st[N]; vector dep[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } ll dijkstra(int ss, int tt) { memset(dis, INF, sizeof dis); memset(st, 0, sizeof st); dis[ss] = 0; priority_queue , vector >, greater >> heap; heap.push({0, ss}); while(heap.size()) { auto t = heap.top(); heap.pop(); int now = t.second; if(st[now]) continue; st[now] = 1; for(int i = h[now]; ~i; i = ne[i]) { int j = e[i]; if(dis[j] > dis[now] + w[i]) { dis[j] = dis[now] + w[i]; heap.push({dis[j], j}); } } } if(dis[tt] == INF) return -1; return dis[tt]; } void dfs(int u, int fa,int depth) { dep[depth].push_back(u); maxdep = max(maxdep, depth); for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (v == fa)continue; dfs(v, u, depth + 1); } } void solve() { memset(h, -1, sizeof h); idx = 0; maxdep = 0; cin >> n; int a, b, c; for(int i = 1; i < n; i++) { cin >> a >> b >> c; add(a, b, c); add(b, a, c); } cin >> k >> p; cin >> s >> t; dfs(1, 0, 0); int cnt = n + 1; for(int i = 0; i <= maxdep; i++) { int h = i + k; if(h > maxdep) break; if(dep[i].size() == 0 || dep[h].size() == 0) continue; for(auto t : dep[i]) { add(t, cnt, 0); add(cnt + 1, t, p); } for(auto t : dep[h]) { add(cnt, t, p); add(t, cnt + 1, 0); } cnt += 2; } cout << dijkstra(s, t) << endl; for(int i = 0; i <= maxdep; i++) dep[i].clear(); return; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; cin >> T; while(T--) { solve(); } return 0; }
题意
大话骰游戏
思路
因为两个人都知道每个骰子的点数,先手一定叫最大的。
所以如果每个杯子里点数都不同,先手就输,否则先手必赢。
void solve() { memset(st1, 0, sizeof st1); memset(st2, 0, sizeof st2); cin >> n; bool flag = true; int a, b; for(int i = 1; i <= n; i++) { cin >> a; if(st1[a]) flag = false; st1[a] = true; } for(int i = 1; i <= n; i++) { cin >> b; if(st2[b]) flag = false; st2[b] = true; } if(flag) cout << "Just a game of chance." << endl; else cout << "Win!" << endl; return; }1012 - Buy Figurines
题意
有 n n n 个人会在 a i a_i ai 时刻来排队,需要花费 s i s_i si 的时间购买后离开。
有 m m m 个队伍,每个人来的时候会选择当前时刻中,排队人数最少的那个,如果有多个最少的,选择编号最小的队伍。
问最后一个人离开的时间。
思路
用线段树维护每个队伍的人数和编号,也可以用 s e t set set
用 s e t set set 保存已经在排队的人 <离开时间,队伍编号>,
遍历每一个人,如果队伍中的人 离开时间 小于等于当前这个人的 到达时间,从队伍中删除。
然后查询人数最少且编号最小的队伍,更新该条队伍的最后一个人离开的时间,
再把这个人加入队伍。
#includeusing namespace std; //#define int long long #define endl 'n' typedef pair PII; typedef long long ll; const int N = 200010; int n, m; struct Node { ll a, s; bool operator<(const Node &t) const { return a < t.a; } }a[N]; struct TreeNode { int id; // 队列编号 int sz; // 队列人数 bool operator<(const TreeNode &a) const { if(sz == a.sz) return id < a.id; return sz < a.sz; } bool operator=(const TreeNode &a) { id = a.id; sz = a.sz; } }; struct Tree { ll l, r; TreeNode v; }tr[4 * N]; void pushup(int u) { tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v); } void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) { tr[u].v.id = l; tr[u].v.sz = 0; return; } int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int x, int v) { if(tr[u].l == x && tr[u].r == x) tr[u].v.sz += v; else{ int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } TreeNode query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) return tr[u].v; else{ int mid = tr[u].l + tr[u].r >> 1; if(r <= mid) return query(u << 1, l, r); else if(l > mid) return query(u << 1 | 1, l, r); else{ auto left = query(u << 1, l, r); auto right = query(u << 1 | 1, l, r); TreeNode res; res = min(left, right); return res; } } } set > q; // 结束时间,队伍id ll ed[N]; void solve() { memset(ed, 0, sizeof ed); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i].a >> a[i].s; sort(a + 1, a + 1 + n); build(1, 1, m); for(int i = 1; i <= n; i++) { while(q.size() && q.begin()->first <= a[i].a) { modify(1, q.begin()->second, -1); q.erase(q.begin()); } TreeNode tmp = query(1, 1, m); //人数最少且编号最少的队伍 modify(1, tmp.id, +1); ed[tmp.id] = a[i].s + max(ed[tmp.id], a[i].a); pair p; p.first = ed[tmp.id]; p.second = tmp.id; q.insert(p); } ll res = 0; while(q.size()) { res = max(res, q.begin()->first); q.erase(q.begin()); } cout << res << endl; return; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); // freopen("1012.in","r",stdin); // freopen("out.txt","w",stdout); int T = 1; cin >> T; while(T--) solve(); return 0; }