#include<bits/stdc++.h> #define N 37 usingnamespacestd;
inlineintrd(){ int x = 0; bool f = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) f |= (c == '-'); for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); return f ? -x : x; }
intdfs(set<node> s){ if (s.empty()) return0; node nw = *s.begin(); s.erase(nw); set<node> l, r; for (auto t : s) { if (t.k <= nw.k) l.insert(t); else r.insert(t); } ls[nw.id] = dfs(l); rs[nw.id] = dfs(r); return nw.id; }
queue<int> q;
intmain(){ int n = rd(); for (int i = 1; i <= n; ++i) { c[i].id = i; c[i].k = rd(); c[i].p = rd(); S.insert(c[i]); } int ptr = 0, rt = dfs(S); q.push(rt); while (!q.empty()) { int u = q.front(); q.pop(); if (ls[u]) q.push(ls[u]); if (rs[u]) q.push(rs[u]); k[++ptr] = c[u].k; p[ptr] = c[u].p; } for (int i = 1; i < n; ++i) printf("%d ", k[i]); printf("%d\n", k[n]); for (int i = 1; i < n; ++i) printf("%d ", p[i]); printf("%d", p[n]); return0; }
#include<bits/stdc++.h> #define N 100007 #define inf 1e9 usingnamespacestd;
inlineintrd(){ int x = 0; bool f = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) f |= (c == '-'); for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); return f ? -x : x; }
int f[N], mn[N], mnid[N], sz[N], totr, totc;
structroad { int u, v, w; }r[N];
inlineboolcmp2(road a, road b){ return a.w < b.w; }
inlineintfind(int x){ return x == f[x] ? x : f[x] = find(f[x]); }
inlinevoidmerge(int a, int b, int w){ a = find(a); b = find(b); if (a == b) { mn[a] = min(mn[a], w); return; } f[a] = b; sz[b] += sz[a]; mnid[b] = min(mnid[b], mnid[a]); mn[b] = min(mn[b], min(mn[a], w)); }
structnode { int mnid, sz, str; }c[N];
inlineboolcmp1(node a, node b){ if (a.str != b.str) return a.str > b.str; if (a.sz != b.sz) return a.sz > b.sz; return a.mnid < b.mnid; }
intmain(){ int n = rd(); int m = rd(); for (int i = 1; i <= n; ++i) { f[i] = i; mn[i] = inf; mnid[i] = i; sz[i] = 1; } for (int i = 1, u, v, w; i <= m; ++i) { u = rd(); v = rd(); w = rd(); if (w > 0) merge(u, v, w); else r[++totr] = (road){u, v, -w}; } for (int i = 1; i <= n; ++i) if (f[i] == i) c[++totc] = (node){mnid[i], sz[i], (mn[i] == inf ? 0 : mn[i])}; sort(c + 1, c + 1 + totc, cmp1); for (int i = 1; i < totc; ++i) printf("%d-%d ", c[i].mnid, c[i].str); printf("%d-%d\n", c[totc].mnid, c[totc].str); int ans = 0; sort(r + 1, r + 1 + totr, cmp2); for (int i = 1; i <= totr; ++i) { int u = find(r[i].u); int v = find(r[i].v); if (u != v) {merge(u, v, r[i].w); ans += r[i].w;} } int cnt = 0; for (int i = 1; i <= n; ++i) cnt += (f[i] == i); ans += (cnt - 1) * 10000; printf("%d", ans); return0; }
#include<bits/stdc++.h> #define N 100007 #define mod 1000000007 usingnamespacestd;
inlineintrd(){ int x = 0; bool f = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) f |= (c == '-'); for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); return f ? -x : x; }
int f[N][10];
#define add(a,b) a = (a + b) % mod
intmain(){ f[0][5] = 1; int n = rd(); for (int i = 1, x; i <= n; ++i) { x = rd(); for (int j = 1; j <= 9; ++j) { if (j - x <= 1) add(f[i][1], f[i - 1][j]); if (j + x >= 9) add(f[i][9], f[i - 1][j]); } for (int j = 2; j <= 8; ++j) { if (j - x > 1 && j - x <= 5) add(f[i][j - x], f[i - 1][j]); if (j + x < 9 && j + x >= 5) add(f[i][j + x], f[i - 1][j]); } } int ans = 0; for (int i = 1; i <= 9; ++i) add(ans, f[n][i]); printf("%d", ans); return0; }