Description
题库链接：
Solution
Code
Day1 T1 铺设道路
#includeusing namespace std;int n, a, la, ans;int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a); if (a > la) ans += a-la; la = a; } printf("%d\n", ans); return 0;}
Day1 T2 货币系统
#includeusing namespace std;int t, n, f[25005], a[105], ma, ans;void work() { memset(f, ma = 0, sizeof(f)); scanf("%d", &n); ans = n, f[0] = 1; for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ma = max(a[i], ma); for (int i = 1; i <= n; i++) for (int j = a[i]; j <= ma; j++) if (f[j-a[i]]) f[j]++; for (int i = 1; i <= n; i++) ans -= f[a[i]] > 1; printf("%d\n", ans);}int main() { scanf("%d", &t); while (t--) work(); return 0;}
Day1 T3 赛道修建
#includeusing namespace std;const int N = 50000+5, inf = 500000000;int n, m, u, v, l, cnt, mid, vis[N];struct tt {int nxt, to, dis; } edge[N<<1];int path[N], top;multiset q[N];multiset ::iterator it;void add(int u, int v, int c) { edge[++top] = (tt){path[u], v, c}; path[u] = top;}int dfs(int u, int c) { vis[u] = 1; if (q[u].size()) q[u].clear(); for (int i = path[u], l; i; i = edge[i].nxt) if (!vis[edge[i].to]) { l = dfs(edge[i].to, edge[i].dis); if (l >= mid) ++cnt; else q[u].insert(l); } int ans = 0; while (!q[u].empty()) { it = q[u].lower_bound(mid-(*q[u].begin())); if (it == q[u].begin() && q[u].count(*q[u].begin()) == 1) ++it; if (it != q[u].end()) ++cnt, q[u].erase(q[u].find(*it)); else ans = max(ans, *q[u].begin()); q[u].erase(q[u].find(*q[u].begin())); } return ans+c;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i < n; i++) { scanf("%d%d%d", &u, &v, &l); add(u, v, l), add(v, u, l); } int ans, R = inf, L = 0; while (L <= R) { mid = (L+R)>>1; cnt = 0; for (int i = 1; i <= n; i++) vis[i] = 0; if (dfs(1, 0) >= mid) ++cnt; if (cnt >= m) ans = mid, L = mid+1; else R = mid-1; } printf("%d\n", ans); return 0;}
Day2 T1 旅行
#include#define pb push_backusing namespace std;const int N = 5000+5;int n, m, a[N], b[N], ku, kv, t, ans[N], kp[N], vis[N];vector to[N];void update() { if (ans[1] == 0) memcpy(ans, kp, sizeof(ans)); else for (int i = 1; i <= n; i++) if (ans[i] != kp[i]) { if (ans[i] > kp[i]) memcpy(ans, kp, sizeof(ans)); return; }}bool dfs(int u, int fa) { if (vis[u]) return false; kp[++t] = u; vis[u] = 1; for (int i = 0, sz = to[u].size(), v; i < sz; i++) if ((v = to[u][i]) != fa && !(u == ku && v == kv || u == kv && v == ku)) if (!dfs(v, u)) return false; return true;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &a[i], &b[i]); to[a[i]].pb(b[i]), to[b[i]].pb(a[i]); } for (int i = 1; i <= n; i++) sort(to[i].begin(), to[i].end()); if (n == m+1) {dfs(1, 0); update(); } else for (int i = 1; i <= m; i++) { ku = a[i], kv = b[i]; t = 0; memset(vis, 0, sizeof(vis)); if (dfs(1, 0) && t == n) update(); } for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]); return 0;}
Day2 T2 填数游戏
#includeusing namespace std;const int N = 1000000+15, yzh = 1000000007;int n, m, ans, s[N], a[N]; int main() { scanf("%d%d", &n, &m); if (n > m) swap(n, m); if (n == 1) { ans = 1; for (int i = 1; i <= m; i++) ans = 2ll*ans%yzh; } else if (n == 2) { ans = 4; for (int i = 1; i < m; i++) ans = 3ll*ans%yzh; } else { s[n+m] = 1; for (int i = n+m-1; i >= 1; i--) a[i] = 2+(i <= n)+(i <= m), s[i] = 1ll*s[i+1]*a[i]%yzh; (ans += 4ll*s[3]%yzh) %= yzh; (ans += 4ll*(a[4]+1)*s[5]%yzh) %= yzh; for (int i = 4; i <= n; i++) { (ans += 2ll*(3+(i <= m))*(a[i+1]+1)*s[i+2]%yzh) %= yzh; } (ans += 2ll*(a[n+1]+1)*s[n+2]%yzh) %= yzh; for (int i = 4; i <= m; i++) { (ans += 2ll*(3+(i <= n))*(a[i+1]+1)*s[i+2]%yzh) %= yzh; } (ans += 2ll*(a[m+1]+1)*s[m+2]%yzh) %= yzh; } printf("%d\n", ans); return 0;}
Day2 T3 保卫王国
#include#define ll long long#define min(a, b) ((a) < (b) ? (a) : (b))using namespace std;const int N = 100000+5;const ll inf = 1e10+1;char rubbish_bin[3];int n, m, lim, p[N], u, v, path[N], top, x, y, fa[N][20], dep[N];ll dp[N][2], f[N][20][2][2];struct tt { int to, nxt; } edge[N<<1];void read(int &x) { x = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = (x<<1)+(x<<3)+ch-48, ch = getchar(); }void add(int u, int v) { edge[++top] = (tt){v, path[u]}; path[u] = top;}void dfs(int u, int f, int d) { dep[u] = d, fa[u][0] = f, dp[u][1] = p[u]; for (int i = 1; i <= lim; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for (int i = path[u], v; i; i = edge[i].nxt) if ((v = edge[i].to) != f) { dfs(v, u, d+1); dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0], dp[v][1]); }}ll cal(int u, int x, int v, int y) { if (dep[u] < dep[v]) swap(u, v), swap(x, y); ll u0, u1, v0, v1, t0, t1, l0, l1; int lca; if (x) u1 = dp[u][1], u0 = inf; else u1 = inf, u0 = dp[u][0]; if (y) v1 = dp[v][1], v0 = inf; else v1 = inf, v0 = dp[v][0]; for (int i = lim; i >= 0; i--) if (dep[fa[u][i]] >= dep[v]) { t0 = u0, t1 = u1; u0 = min(t0+f[u][i][0][0], t1+f[u][i][1][0]); u1 = min(t0+f[u][i][0][1], t1+f[u][i][1][1]); u = fa[u][i]; } if (u == v) { lca = u; if (y) l0 = inf, l1 = u1; else l0 = u0, l1 = inf; } else { for (int i = lim; i >= 0; i--) if (fa[u][i] != fa[v][i]) { t0 = u0, t1 = u1; u0 = min(t0+f[u][i][0][0], t1+f[u][i][1][0]); u1 = min(t0+f[u][i][0][1], t1+f[u][i][1][1]); t0 = v0, t1 = v1; v0 = min(t0+f[v][i][0][0], t1+f[v][i][1][0]); v1 = min(t0+f[v][i][0][1], t1+f[v][i][1][1]); u = fa[u][i], v = fa[v][i]; } lca = fa[u][0]; l0 = dp[lca][0]-dp[u][1]-dp[v][1]+u1+v1; l1 = dp[lca][1]-min(dp[u][0], dp[u][1])-min(dp[v][0], dp[v][1])+min(u0, u1)+min(v0, v1); } for (int i = lim; i >= 0; i--) if (fa[lca][i]) { t0 = l0, t1 = l1; l0 = min(t0+f[lca][i][0][0], t1+f[lca][i][1][0]); l1 = min(t0+f[lca][i][0][1], t1+f[lca][i][1][1]); lca = fa[lca][i]; } if (min(l0, l1) < inf) return min(l0, l1); else return -1;}int main() { read(n), read(m); scanf("%s", rubbish_bin); lim = log(n)/log(2); for (int i = 1; i <= n; i++) read(p[i]); for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); add(u, v), add(v, u); } dfs(1, 0, 1); for (int u = 1; u <= n; u++) { f[u][0][0][0] = inf; f[u][0][1][0] = dp[fa[u][0]][0]-dp[u][1]; f[u][0][0][1] = f[u][0][1][1] = dp[fa[u][0]][1]-min(dp[u][0], dp[u][1]); } for (int i = 1; i <= lim; i++) for (int u = 1; u <= n; u++) { int t = fa[u][i-1]; f[u][i][0][0] = min(f[u][i-1][0][0]+f[t][i-1][0][0], f[u][i-1][0][1]+f[t][i-1][1][0]); f[u][i][0][1] = min(f[u][i-1][0][0]+f[t][i-1][0][1], f[u][i-1][0][1]+f[t][i-1][1][1]); f[u][i][1][0] = min(f[u][i-1][1][0]+f[t][i-1][0][0], f[u][i-1][1][1]+f[t][i-1][1][0]); f[u][i][1][1] = min(f[u][i-1][1][0]+f[t][i-1][0][1], f[u][i-1][1][1]+f[t][i-1][1][1]); } while (m--) { read(u), read(x), read(v), read(y); printf("%lld\n", cal(u, x, v, y)); } return 0;}