A
设 表示两堆石头数量分别为 时是必胜态( ) 还是必败态()。初始有 。因为能到达一种必败态的状态是必胜的,所以对于 的状态,暴力枚举 ,令 。这样的时间复杂度是 ,是过不了的!
这里有一个结论,对于一个 ,只存在至多一个 使得 是必败态,证明如下:
若 都是必败态,因为 可以通过选择 转移到 ,所以 是必胜态,与假设矛盾。
这样时间复杂度就是 ,需要略微卡常。
#include <bits/stdc++.h> using namespace std; const int N = 5003; bool f[N][N]; signed main() { int T; scanf("%d", &T); for (int i = 0; i <= 5000; i++) for (int j = 0; j <= 5000; j++) if (!f[i][j]) { for (int k = 1; k <= 5000 - i; k++) for (int s = 0; s <= 5000 - j; s += k) f[i + k][j + s] |= 1; for (int k = 1; k <= 5000 - j; k++) for (int s = 0; s <= 5000 - i; s += k) f[i + s][j + k] |= 1; } while (T--) { int n, m; scanf("%d%d", &n, &m); if (f[n][m]) puts("Alice"); else puts("Bob"); } return 0; }
B
如果圆的直径大于 就掉不下去。
把梯形补全成等腰三角形。根据勾股定理可知,斜边
图中有 ,所以
$$
#include <bits/stdc++.h> using namespace std; int main() { long double r, a, b, h, x, c; scanf("%Lf%Lf%Lf%Lf", &r, &a, &b, &h); if (a < b) swap(a, b); if ((r * 2) <= b) { puts("Drop"); return 0; } puts("Stuck"); x = b * h / (a - b); c = sqrt((a * a / 4) + (x + h) * (x + h)); printf("%Lf", c * r / (a / 2) - x); return 0; }
D
因为放 的位置必须是横着连续 个,所以行与行之间是无关的。我们就把每一行若出来分别求答案
对于一行从 到 遍历,记录 表示当前最后出现了多少个连续的 。如果下一个是 , 加一,否则 。当 的时候,答案就可以加一。代表以当前这个位置结尾的一个合法方案。时间复杂度
#include <bits/stdc++.h> using namespace std; const int N = 2010; char s[N][N], t[N]; signed main() { int n, m, ans = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); scanf("%s", t + 1); for (int i = 1; i <= n; i++) { int cnt = 0; for (int j = 1; j <= n; j++) { if (s[i][j] == '0') cnt++; else cnt = 0; if (cnt >= m) ans++; } } cout << ans << endl; return 0; }
E
从起点到终点,记录来的方向。然后从终点反向找回到起点的路径,根据正确的方向旋转格子即可。
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 9; int T, n, m, a[N][N]; int vis[N][N][5]; int dir[5][2] = { 0, 0, -1, 0, 0, -1, 0, 1, 1, 0 }; struct node { int x, y, d; }; queue<node> q; vector<int> A; bool in(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } void bfs() { while (q.size()) q.pop(); q.push(node{ 1, 1, 1 }); while (q.size()) { int x = q.front().x; int y = q.front().y; int d = q.front().d; q.pop(); if (x == n && y == m && ((a[n][m] <= 3 && d == 2) || (a[n][m] > 3 && d == 1))) { vis[n][m][1] = d; break; } if (a[x][y] <= 3) { for (int i = 1; i <= 4; i++) { if (i == d || i + d == 5) continue; int tx = x + dir[i][0], ty = y + dir[i][1]; if (in(tx, ty) && vis[x][y][5 - i] == -1) { vis[x][y][5 - i] = d; q.push(node{ tx, ty, 5 - i }); } } continue; } int tx = x + dir[5 - d][0], ty = y + dir[5 - d][1]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[x][y][d] == -1) vis[x][y][d] = d, q.push(node{ tx, ty, d }); } } int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); memset(vis[i][j], -1, sizeof vis[i][j]); } bfs(); if ((a[n][m] <= 3 && vis[n][m][1] == 2) || (a[n][m] > 3 && vis[n][m][1] == 1)) { A.clear(); puts("YES"); int x = n, y = m; A.push_back(4); int d, dd = 1; while (!(x == 1 && y == 1)) { d = vis[x][y][dd]; A.push_back(5 - d); x = x + dir[d][0], y = y + dir[d][1]; dd = d; } cout << 2 * A.size() << endl; A.push_back(4); reverse(A.begin(), A.end()); x = 0, y = 1; for (int i = 1; i < A.size(); i++) { int tx = x + dir[A[i - 1]][0], ty = y + dir[A[i - 1]][1]; int now = A[i], last = 5 - A[i - 1]; int D, k; if (now > last) swap(now, last); if (now == 1 && last == 2) k = 0; if (now == 1 && last == 3) k = 1; if (now == 3 && last == 4) k = 2; if (now == 2 && last == 4) k = 3; if (now == 2 && last == 3) k = 4; if (now == 1 && last == 4) k = 5; D = ((k + 4 - a[tx][ty]) % 4) * 90; a[tx][ty] = k; printf("1 %d %d %d\n", D, tx, ty); printf("0 %d %d\n", tx, ty); x = tx, y = ty; } } else puts("NO"); } return 0; }
F
对于一个数 ,可以对每一位的数做一个前缀和 ( 意义下),如果存在两个位置值相等,那么这个数就是合法的。根据鸽巢原理,当 位数大于等于 的时候,一定存在两个位置值相等。也就是说, 一定合法。只需要对 暴力判断一下即可。
#include <bits/stdc++.h> using namespace std; int sum[1100]; long long get(long long x) { if (x >= 1000) return x - 1000 + 1 + sum[999]; return sum[x]; } int sta[5], top; int check(int x) { top = 0; while (x) sta[++top] = x % 10, x /= 10; for (int i = 1; i <= top; i++) { int k = 0; for (int j = i; j <= top; j++) { k = k * 10 + sta[j]; if (k % 3 == 0) return 1; } } return 0; } signed main() { int T; scanf("%d", &T); for (int i = 1; i <= 999; i++) { sum[i] = sum[i - 1]; sum[i] += check(i); } while (T--) { long long L, R; scanf("%lld%lld", &L, &R); printf("%lld\n", get(R) - get(L - 1)); } return 0; }
G
可以把问题变成在每个 前面放符号,但是要满足 号和 号各 个,最后答案就是带符号的权值和。
若 ,那么 中较大值为 ,较小值为 。
每次交换,优先考虑交换两个符号不同的数,试图交换他们的符号,(否则答案肯定不会变化)
考虑贪心,把所有 符号的数升序排序变成 ,所有 符号的数降序排列变成 。每次对于一个 ,看是否有 ,有的话交换,改变符号。考虑这样的一次交换对应在原序列上是否合法。
假设 的原位置分别是 :
- 交换 (假设 属于 )有 ,等价于交换 ,交换后符号改变。
- 交换 (假设 属于 )有 ,等价于交换 ,交换后符号改变。
剩下情况同理。由此可知这种方法是正确的。
注意,如果 次操作多了,交换同符号的即可消耗次数。但在 时候很特殊,必须强制交换一次,特判即可。时间复杂度
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 9; int a[N], b[N]; long long ans; vector<int> A, B; bool cmp(int x, int y) { return x > y; } signed main() { int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); if (n == 2 && k == 1) { cout << abs(a[1] - b[2]) + abs(a[2] - b[1]) << endl; } for (int i = 1; i <= n; i++) { A.push_back(max(a[i], b[i])); B.push_back(min(a[i], b[i])); } sort(A.begin(), A.end()); sort(B.begin(), B.end(), cmp); for (int i = 0; i < n; i++) { if (k && A[i] < B[i]) ans += B[i] - A[i], k--; else ans += A[i] - B[i]; } cout << ans << endl; return 0; }
H
首先,对于两个数 ,若 ,那么这个 一定是不合法的。因为 ,两边同时加上 就有 。
否则, 一定不等于 。
那么,只需要得到所有的 并把他们的因子排除掉,输出剩下的最小的一个未被排除的数即可。
具体的,可以用减法卷积得到所有的 ,这一步时间复杂度是 。然后从小到大枚举所有 ,看是否存在 不合法。这一步时间复杂度为
总时间复杂度
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2 * 1e6 + 10; const int p = 998244353; const int G = 3, Gi = 332748118; const int M = 500001; bool vis[M + 10], c[M + 10]; int n, len = 1, L, r[N]; int a[N], b[N]; int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = res * x % p; x = x * x % p; base >>= 1; } return res; } void NTT(int* A, int op) { for (int i = 0; i < len; i++) if (i < r[i]) swap(A[i], A[r[i]]); for (int mid = 1; mid < len; mid <<= 1) { int Wn = inv(op == 1 ? G : Gi, (p - 1) / (mid << 1)); for (int j = 0; j < len; j += (mid << 1)) { for (int k = 0, w = 1; k < mid; k++, w = (w * Wn) % p) { int x = A[j + k], y = w * A[j + k + mid] % p; A[j + k] = (x + y) % p, A[j + k + mid] = (x - y + p) % p; } } } } signed main() { cin >> n; for (int i = 1; i <= n; i++) { int x; scanf("%lld", &x); a[x] = 1; } for (int i = 0; i <= M; ++i) b[i] = a[M - i]; while (len <= 2 * M) len <<= 1, L++; for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1)); NTT(a, 1); NTT(b, 1); for (int i = 0; i < len; i++) a[i] = (a[i] * b[i]) % p; NTT(a, -1); for (int i = M + 1; i <= 2 * M; i++) if (a[i]) c[i - M] = true; for (int i = 1; i <= M; ++i) for (int j = i; j <= M; j += i) if (c[j]) vis[i] = true; for (int i = 1; i <= M; ++i) if (!vis[i]) { printf("%lld\n", i); return 0; } return 0; }
I
设 为上上一次选 ,上次选 的期望结束轮数。有 ,其中 表示 的位置, 是合法转移个数。
但是这样每次要枚举下一个合法的位置,时间复杂度是
我们从大到小枚举 ,从大到小枚举位置 ,若 ,我们记录 的后缀和及个数。否则更新 ,有 。时间复杂度
#include <bits/stdc++.h> #define int long long using namespace std; const int p = 998244353; const int N = 5e3 + 9; int n, ans; int f[N][N], a[N], inv[N]; signed main() { scanf("%lld", &n); inv[0] = inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p; for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int j = n; j >= 0; j--) { int sum = 0, cnt = 0; for (int i = n; i >= 0; i--) { if (a[i] == j) continue; if (a[i] > j) cnt++, (sum += f[j][a[i]]) %= p; else f[a[i]][j] = (sum * inv[cnt] + 1) % p; } } for (int i = 1; i <= n; i++) (ans += f[0][i]) %= p; printf("%lld", ans * inv[n] % p); return 0; }
J
假设有两个点 ,假设从 最早的时间出发都无法在 点最晚的时间前到达,那么就无法从 走到 。
否则,考虑是否能把两个点看成一个整体 。
设 为 最早到达下一个点的时间, 为最迟到达 下一个点$c.dis$ 是到下一个点的距离。
(因为可能在 点中会停留一段时间,所以要和 取个 )
(首先不能晚于 的最晚到达时间,其次到达 时不能晚于 的最晚到达时间)
这样,两个点就能合并成一个点了!接下来我们需要一个能快速合并区间信息的数据结构,于是就能想到线段树。每次修改时递归到底层更新即可。
时间复杂度 。
#include <bits/stdc++.h> using namespace std; const int N = 1 << 21; const int inf = 2e9; struct node { int x, y, dis; node(int X = 0, int Y = 0, int Dis = 0) { x = X, y = Y, dis = Dis; } } t[N], no, res; node merge(node a, node b, int c) { node p; if (a.x + c > b.y) return no; return node(min(inf, max(b.x, a.x + c + b.dis)), max(-inf, min(b.y - c - a.dis, a.y)), a.dis + b.dis + c); } int n, q; int a[N], b[N], c[N]; struct tree { void build(int p, int l, int r) { if (l == r) { t[p] = node(a[l], b[l], 0); return; } int mid = l + r >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]); } node query(int L, int R, int p, int l, int r) { if (L <= l && r <= R) return t[p]; int mid = l + r >> 1; node res; if (L <= mid) { res = query(L, R, p << 1, l, mid); if (mid < R) res = merge(res, query(L, R, p << 1 | 1, mid + 1, r), c[mid]); } else if (mid < R) res = query(L, R, p << 1 | 1, mid + 1, r); return res; } void add1(int x, int p, int l, int r) { int mid = l + r >> 1; if (x < mid) add1(x, p << 1, l, mid); if (x > mid) add1(x, p << 1 | 1, mid + 1, r); t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]); } void add2(int x, int p, int l, int r) { if (l == r) { t[p] = node(a[l], b[l]); return; } int mid = l + r >> 1; if (x <= mid) add2(x, p << 1, l, mid); else add2(x, p << 1 | 1, mid + 1, r); t[p] = merge(t[p << 1], t[p << 1 | 1], c[mid]); } } T; int main() { int x, y, op, cases; no = node(inf, -inf, 0); scanf("%d", &cases); while (cases--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= n; i++) scanf("%d", b + i); for (int i = 1; i < n; i++) scanf("%d", c + i); T.build(1, 1, n); scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%d%d", &op, &x, &y); if (op == 0) { res = T.query(x, y, 1, 1, n); if (res.y < 0) puts("No"); else puts("Yes"); } else { if (op == 1) { c[x] = y; T.add1(x, 1, 1, n); } else { scanf("%d", &op); a[x] = y, b[x] = op; T.add2(x, 1, 1, n); } } } } return 0; }
K
这里有个做法,多做几次暴力枚举两两数对,如果更优就交换。时间复杂度
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 9; int T, n, a[N]; signed main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int k = 1; k <= 3; k++) for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (sqrt(abs(a[i] - i)) + sqrt(abs(a[j] - j)) > sqrt(abs(a[i] - j)) + sqrt(abs(a[j] - i))) swap(a[i], a[j]); for (int i = 0; i < n; i++) printf("%d ", a[i]); puts(""); } return 0; }
全部评论
(0) 回帖