NOI2019同步赛 day2

今天的题目有些难

T1

一看是非常的可做 32分直接$O(n^2)$连边跑$dijkstra$ 再来20分，使用二分查找对应点，然后连边，跑$dijkstra$ 再来20分，我就不会啦，应该是线段树优化建边，我没学过，所以我在线学习了一下，然后是疯狂调试，看起来是过了……

满分的应该是想不出来的

Code：

#include <bits/stdc++.h> #define maxn 100010 using namespace std; struct Edge{ int to, next, len; }edge[maxn << 1]; struct POS{ int x, y, id; }pos[maxn]; struct node{ int val, len; bool operator < (const node &x) const{ return x.len < len; } }; priority_queue <node> q; int num, head[maxn], n, m, W, H, cnt; int dis[maxn << 4], vis[maxn << 4]; int pp1[maxn], pp2[maxn]; struct Seg{ int l, r, num; }seg[5][maxn << 2]; struct Vec{ int v, w; }; vector <Vec> G[maxn << 4]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void addedge(int x, int y, int z){ edge[++num] = (Edge){ y, head[x], z }; head[x] = num; } void dijkstra(){ dis[1] = 0; for (int i = 2; i <= n; ++i) dis[i] = 1e9; q.push((node) { 1, 0 }); while (!q.empty()){ node tmp = q.top(); q.pop(); int u = tmp.val, len = tmp.len; if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if (dis[v] > len + edge[i].len){ dis[v] = len + edge[i].len; if (!vis[v]) q.push( (node) { v, dis[v] }); } } } for (int i = 2; i <= n; ++i) printf("%d\n", dis[i]); } void do1(){ for (int i = 1; i <= m; ++i){ int p = read(), t = read(), l = read(), r = read(), d = read(), u = read(); for (int j = 1; j <= n; ++j) if (p != j && pos[j].x >= l && pos[j].x <= r && pos[j].y >= d && pos[j].y <= u) addedge(p, j, t); } dijkstra(); } #define ls rt << 1 #define rs rt << 1 | 1 typedef pair<int, int> pii; void build(int rt, int l, int r, int op){ seg[op][rt].l = l, seg[op][rt].r = r, seg[op][rt].num = ++cnt; if (l == r){ if (op == 1) pp1[l] = cnt; else{ pp2[l] = cnt; G[pp2[l]].push_back( (Vec) { pp1[l], 0} ); } return; } int mid = (l + r) >> 1; build(ls, l, mid, op); build(rs, mid + 1, r, op); if (op == 1){ G[seg[op][ls].num].push_back( (Vec){seg[op][rt].num, 0} ); G[seg[op][rs].num].push_back( (Vec){seg[op][rt].num, 0} ); } else{ G[seg[op][rt].num].push_back( (Vec){seg[op][ls].num, 0} ); G[seg[op][rt].num].push_back( (Vec){seg[op][rs].num, 0} ); } } void update(int rt, int l, int r, int u, int w, int op){ if(seg[op][rt].l == l && seg[op][rt].r == r) { if (op == 1) G[u].push_back( (Vec){seg[2][rt].num, w} ); else G[seg[1][rt].num].push_back( (Vec){u, w} ); return; } int mid = (seg[op][rt].l + seg[op][rt].r) >> 1; if (r <= mid) update(ls, l, r, u, w, op); else if (l > mid) update(rs, l, r, u, w, op); else { update(ls, l, mid, u, w, op); update(rs, mid + 1, r, u, w, op); } } void do2_dijkstra(int s) { for (int i = 1; i <= cnt; ++i) dis[i] = 1e9; dis[pp1[s]] = 0; priority_queue<pii, vector<pii>, greater<pii> > q; q.push( (pii){0, pp1[s]} ); while (!q.empty()) { int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = 1; int v; for (int i = 0; i < (int) G[u].size(); ++i) { v = G[u][i].v; if (dis[v] > dis[u] + G[u][i].w) { dis[v] = dis[u] + G[u][i].w; q.push( (pii){dis[v], v} ); } } } } void do2(){ build(1, 1, W, 1); build(1, 1, W, 2); for (int i = 1; i <= m; ++i){ int p = read(), t = read(), l = read(), r = read(), d = read(), u = read(); update(1, l, r, pp1[pos[p].x], t, 1); } do2_dijkstra(pos[1].x); for (int i = 2; i <= n; ++i) printf("%d\n", min(dis[pp1[pos[i].x]], dis[pp2[pos[i].x]])); } bool do3_cmp(POS a, POS b){ return a.x == b.x ? a.y < b.y : a.x < b.x; } void do3(){ for (int i = 1; i <= n; ++i) pos[i].id = i; sort(pos + 1, pos + 1 + n, do3_cmp); for (int i = 1; i <= m; ++i){ int p = read(), t = read(), l = read(), r = read(), d = read(), u = read(); int ll = 1, rr = n, q = 0; while (ll <= rr){ int mid = (ll + rr) >> 1; if (pos[mid].x < l || pos[mid].x == l && pos[mid].y < d) ll = mid + 1; else rr = mid - 1, q = mid; } addedge(p, pos[q].id, t); } dijkstra(); } int main(){ freopen("jump.in", "r", stdin); freopen("jump.out", "w", stdout); n = read(), m = read(), W = read(), H = read(); for (int i = 1; i <= n; ++i) pos[i].x = read(), pos[i].y = read(); if (n <= 100) do1(); else if (H == 1) do2(); else do3(); return 0; }

T2

T1写了3.5h，后面的题目没时间写了，T2一看，没什么思路，直接上dfs拿10分

Code：

#include <bits/stdc++.h> #define maxn 110 #define qy 998244353 #define int long long using namespace std; int ans[maxn], lena, lenb, a[maxn], b[maxn], f[maxn], A[maxn], n, m, type; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int ksm(int n, int k){ if (!k) return 1; int sum = ksm(n, k >> 1); sum = 1LL * sum * sum % qy; if (k & 1) sum = 1LL * sum * n % qy; return sum; } void dfs(int i, int j, int p){ int inv = ksm(i + j, qy - 2); (ans[i + j] += a[i] * i % qy * inv % qy * p % qy) %= qy; (ans[i + j] += b[j] * j % qy * inv % qy * p % qy) %= qy; if (i) dfs(i - 1, j, p * i % qy * inv % qy); if (j) dfs(i, j - 1, p * j % qy * inv % qy); } signed main(){ freopen("landlords.in", "r", stdin); freopen("landlords.out", "w", stdout); n = read(), m = read(), type = read(); for (int i = 1; i <= n; ++i) f[i] = type == 1 ? i : i * i; for (int i = 1; i <= m; ++i) A[i] = read(); for (int i = 1; i <= A[1]; ++i) a[i] = f[i]; for (int i = A[1] + 1; i <= n; ++i) b[i - A[1]] = f[i]; lena = A[1], lenb = n - lena; dfs(lena, lenb, 1); int M = read(); while (M--){ int x = read(); printf("%lld\n", ans[x]); } return 0; }

T3

交互题什么的我完全不会了。。。 我不知道他是怎么操作的 所以这道题我直接弃疗了

所以期望得分72+10+0=82吧 如果能达到，两天加起来刚好200.。。。 感觉不错