A 小沙的炉石
题意：n张攻击牌（用攻击牌会耗1点法力，攻击力为1），m张加法力牌（加1点法力），一开始有1点法力，并且每用一张牌，额外的攻击力会多1。q个询问，每个询问给定x滴血，问能否正好攻击一定次数，恰好扣为0滴血。
（3）在最小伤害值的出牌策略的基础上，把攻击牌和它后面邻近的回复牌的位置进行交换，每次交换可以使得总伤害值加一，最终可以到达最大伤害值的出牌策略
思路： 1. 首先需要：n = min(n，m + 1) 2. 二分攻击次数，判该攻击下的最大范围能否覆盖x，同时尽可能使这个数小，以方便区间左端点尽可能的小，使得x可以被区间覆盖
#include <bits/stdc++.h> using namespace std; #define int long long int n, m, k, x; bool check(int mid) { return mid * m + mid * (mid + 1) / 2 >= x; } signed main() { cin >> n >> m; cin >> k; n = min(n, m + 1); int right = n * m + n * (n + 1) / 2; // n * (2 * m + n + 1) / 2; while(k--) { cin >> x; if(x <= right) { int l = 1, r = n; while(l < r) { int mid = (l + r) >> 1; if(check(mid)) r = mid; else l = mid + 1; } if(x >= l * l) puts("YES"); else puts("NO"); } else puts("NO"); } return 0; }
另解：以血量x确定最小攻击的攻击次数，在直接判断该攻击的最大覆盖范围，能覆盖x就可以。
#include <bits/stdc++.h> using namespace std; #define int long long int n, m, k, x; signed main() { cin >> n >> m; cin >> k; n = min(n, m + 1); while(k -- ) { cin >> x; int s = sqrt(x); s = min(s, n); if(s * m + s * (s + 1) / 2 >= x) puts("YES"); else puts("NO"); } return 0; }
B 小沙的魔法
pass
C 小沙的杀球
- 贪心
void solve() { int x, a, b; cin >> x >> a >> b; string s; cin >> s; int res = 0; rep(i, 0, s.sz) { if(s[i] == '0') x += b; else if(s[i] == '1') { if(x - a >= 0) res += 1, x -= a; else x += b; } } cout << res << endl; }
D 小沙的涂色
pass
E 小沙的长路
题意：n个点完全图，求出最长路的最小和最大值。
思路： 1. 最小值： 只需构成的图尽可能没环，那么只会经过所有点各一次，即 n - 1 2. 最大值 奇：每个点的出入度都是偶数，可以构成欧拉回路，每条边都能经过一次，n * (n - 1) / 2 偶：删除最少的边，构成一个欧拉回路，删n / 2 - 1 条边， n * (n - 1) / 2 - n / 2 + 1
void solve() { int n; cin >> n; cout << n - 1 << ' '; if(n & 1) { cout << n * (n - 1) / 2 << endl; } else { cout << n * (n - 1) / 2 - n / 2 + 1 << endl; } }
F 小沙的算数
题意：给一串运算式（* 、 +） 两种运算符，m个询问，x位置的值该位y。每次输出该运算式的结果。
思路： 1. + 运算符明显之间相互独立 2. 并查集，用于连接 * 运算符所在集合 3. 每次对改前的数除去，乘回改后的数 4. 注意除法要用逆元
#include <iostream> #include <string> #include <cmath> using namespace std; #define int long long const int N = 2000010, mod = 1000000007; int fa[N], a[N], mul[N]; int qmi(int x, int y) { int res = 1ll; while(y) { if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); } int n, m; string s; signed main() { cin >> n >> m; cin >> s; s = ' ' + s; for (int i = 1; i <= n; i++) { cin >> a[i]; fa[i] = i; mul[i] = a[i]; } for (int i = 1; i < n; i++) { if(s[i] == '*') { int pa = find(i), pb = find(i + 1); fa[pb] = pa; mul[pa] = a[i + 1] * mul[pa] % mod; } } int res = 0; // 先算出当前运算式的值 for (int i = 1; i <= n; i++) if(fa[i] == i) // 因为 * 后的值已经放到父节点的mul中去了，只需加一个 res = (res + mul[i]) % mod; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; int p = find(x); res = (res - mul[p] + mod) % mod; // 先把(*的值)减掉 // (* 的值) / 改变前的值， 在 *上改变后的值 mul[p] = mul[p] * qmi(a[x], mod - 2) % mod; a[x] = y; mul[p] = mul[p] * y % mod; // (* 的值)加回 res = (res + mul[p]) % mod; cout << res << endl; } return 0; }
G 小沙的身法
题意：求一棵树两点间最短距离，u->v，但一开始上u要算距离（即+w[u]），然后从高到低距离为0，即假设： w[u] == 3, w[fa[u]] == 2, 则 u -> fa[u] == 0。
思路：LCA板子题，up数组表示从点u到root， down表示从root到u
#include <iostream> #include <cstring> #define int long long using namespace std; const int N = 1000010, M = N << 1; int h[N], e[M], ne[M], idx; int fa[N][21], depth[N], w[N]; int q[N]; int up[N], down[N]; int n, m; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void bfs(int root) { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[root] = 1; int hh = 0, tt = 0; q[tt++] = root; while(hh != tt) { int t = q[hh++]; if(hh == N) hh = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if(fa[t][0] == j) continue; // 不然 seg q[tt++] = j; if(tt == N) tt = 0; fa[j][0] = t; if(depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; for (int k = 1; k <= 20; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1]; } up[j] = up[t] + max(0ll, w[t] - w[j]); // 勿写反 down[j] = down[t] + max(0ll, w[j] - w[t]); } } } int lca(int x, int y) { if(depth[x] < depth[y]) swap(x, y); for (int k = 20; k >= 0; k--) if(depth[fa[x][k]] >= depth[y]) x = fa[x][k]; if(x == y) return x; for (int k = 20; k >= 0; k--) if(fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k]; return fa[x][0]; } signed main() { memset(h, -1, sizeof h); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> w[i]; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b); add(b, a); } int root = 1; bfs(root); while(m--) { int a, b; cin >> a >> b; int k = lca(a, b); cout << up[a] + down[b] - up[k] - down[k] + w[a] << endl; } return 0; }
