A
发现随着时间的增加,凸包的每个顶点都是沿着角平分线移动。当两个相邻的顶点相交时,整个凸包的形状就会改变。
每次找到最近发生变化的顶点,可以通过距离计算出移动的时间。同样就能求出其他所有点移动距离从而求得新的凸包。
对于凸包形状不变的一段时间,面积是关于时间的一个二次函数,求出这个二次函数输出答案即可。
#include <bits/stdc++.h> #define P pair<double,int> #define fi first #define se second using namespace std; const int N = 1e5 + 9; const double eps = 1e-8; int n, m; double ans[N]; struct node { double x, y; node() {} node(double a, double b) { x = a, y = b; } node operator+(const node &a)const { return node(x + a.x, y + a.y); } node operator-(const node &a)const { return node(x - a.x, y - a.y); } double operator*(const node &a)const { return x * a.y - y * a.x; } node operator*(const double &a)const { return (node) { x *a, y *a }; } node operator/(const double &a)const { return (node) { x / a, y / a }; } double len() { return sqrt(x * x + y * y); } } p[N]; struct Line { node a, b; Line swap() { return (Line) { b, a }; } double getarea() { return a * b; } double len() { return (a - b).len(); } } L[N]; P q[N]; vector<int>v; node getinp(Line x, Line y) { node a = x.a - y.a, b = x.a - x.b, c = y.b - y.a; double t = -(c * a) / (c * b); return node(x.a.x + b.x * t, x.a.y + b.y * t); } Line getabd(Line l1, Line l2) { swap(l2.a, l2.b); node x = getinp(l1, l2); node a = x; node b = x + ((l1.b - l1.a) / l1.len() + (l2.b - l2.a) / l2.len()); return (Line) { a, b }; } double getdist(node a, Line b) { node c = b.b - b.a; if (abs(c.x) <= eps) return abs(a.x - b.a.x); double A = c.y / c.x; double C = b.a.y - b.a.x * A; double B = -1.0; return abs((A * a.x + B * a.y + C) / sqrt(A * A + B * B)); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y), v.push_back(i); p[n + 1] = p[1]; for (int i = 1; i <= n; ++i) L[i] = (Line) { p[i], p[i + 1] }; scanf("%d", &m); for (int i = 1; i <= m; ++i) scanf("%lf", &q[i].fi), q[i].se = i; sort(q + 1, q + m + 1); int l = 1; while ((int)v.size() > 2) { int s = (int)v.size(); int pos = 0; double S = 0; double t = 1e6; double A = 0, B = 0, C = 0; for (int i = 0; i < s; ++i) { Line pre = L[v[(i - 1 + s) % s]], suf = L[v[(i + 1) % s]], now = L[v[i]]; Line now1 = (Line) { getinp(pre, now.swap()), getinp(now, suf.swap()) }; S += now1.getarea(); Line line1 = getabd(now, pre); Line line2 = getabd(suf, now); node inp = getinp(line1, line2); double tt = getdist(inp, now); node a = now1.a - inp, b = now1.b - inp; double S1 = a * b / 2.0; A += S1; B += -2.0 / tt * S1; C += 1.0 / tt / tt * S1; if (tt < t) pos = i, t = tt; } S /= 2.0; for (; l <= m && (abs(q[l].fi - t) <= eps || q[l].fi <= t); ++l) ans[q[l].se] = S + (q[l].fi * B + q[l].fi * q[l].fi * C); v.erase(v.begin() + pos); } for (int i = 1; i <= m; ++i) printf("%.10f\n", ans[i]); return 0; }
B
若 ,把概率看成边权,直接矩阵树定理求解。时间复杂度
用 表示第 条边在时间 的概率,用 代替 ,每个 形如 的形式,然后带入到原来的行列式 里。
根据行列式的一些基本操作,可以把行列式 看成 ,其中 只由 组成, 只由 组成。
把 变换成单位矩阵,即满足 ,同时 也应该做相同变换。(因为本质同一个行列式拆分成两个),得到 。现在考虑如何求解
这个形式等价于求 的特征多项式。一般解法就是化为上海森堡矩阵在 时间内求出多项式,然后乘回 就变成答案关于 ,即 的多项式。
每一项单独等比数列求和得到答案,最终复杂度 。注意, 答案为 。
#include <bits/stdc++.h> using namespace std; const int N = 6e2 + 9; const int p = 998244353; int a[N][N], b[N][N]; int n, m, t, A; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % p; x = 1ll * x * x % p; base >>= 1; } return res; } void gauss(int n) { for (int i = 1; i <= n; i++) { if (a[i + 1][i] == 0) { bool flag = 0; for (int j = i + 2; j <= n; j++) { if (a[j][i] != 0) { for (int k = i ; k <= n; k++) swap(a[i + 1][k], a[j][k]); for (int k = i ; k <= n; k++) swap(a[k][i + 1], a[k][j]); flag = 1; break; } } if (!flag) continue; } int t = inv(a[i + 1][i]), tmp; for (int j = i + 2; j <= n; j++) { tmp = 1ll * t * a[j][i] % p; for (int k = i ; k <= n; k++) a[j][k] = (a[j][k] - 1ll * tmp * a[i + 1][k] % p + p) % p; for (int k = 1 ; k <= n; k++) a[k][i + 1] = (a[k][i + 1] + 1ll * tmp * a[k][j]) % p; } } } void poly(int n) { int tmp, t; b[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) { if (j) b[i][j] = (0ll + p - b[i - 1][j - 1] + 1ll * b[i - 1][j] * a[i][i] % p) % p; else b[i][j] = 1ll * b[i - 1][j] * a[i][i] % p; } t = p - a[i][i - 1]; for (int j = i - 1; j >= 1; j--) { tmp = 1ll * t % p * a[j][i] % p; for (int k = 0; k <= n; k++) b[i][k] = (b[i][k] + 1ll * tmp * b[j - 1][k]) % p; t = 1ll * t * (p - a[j][j - 1]) % p; } } } int B[N][N], K[N][N], C = 1; void Inv(int n) { int tmp; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) K[i][j + n] = B[i][j]; for (int i = 1; i < n; i++) { if (K[i][i] == 0) { for (int j = i + 1; j <= n; j++) { if (K[j][i]) { swap(K[j], K[i]); C = -C; break; } } } C = 1ll * K[i][i] * C % p; tmp = inv(K[i][i]); for (int j = i + 1; j <= n + n; j++) K[i][j] = 1ll * tmp * K[i][j] % p; for (int k = 1; k <= n; k++) { if (i == k) continue; tmp = K[k][i]; for (int j = 1; j <= n + n; j++) K[k][j] = (K[k][j] - 1ll * tmp * K[i][j]) % p; } } } int fa[N]; int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); } int main() { n = read(), m = read(), t = read(), A = read(); if (n == 1 || m == 0) { puts("0"); return 0; } for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= m; i++) { int x, y, a, b, P, Q; x = read(), y = read(); fa[get(x)] = get(y); a = read(), b = read(); P = 1ll * a * inv(b) % p; a = read(), b = read(); Q = 1ll * a * inv(b) % p; K[x][y] = (0ll + K[x][y] + p - P + Q) % p; K[y][x] = (0ll + K[y][x] + p - P + Q) % p; K[y][y] = (0ll + K[y][y] + p + P - Q) % p; K[x][x] = (0ll + K[x][x] + p + P - Q) % p; B[x][y] = (B[x][y] + p - Q) % p; B[y][x] = (B[y][x] + p - Q) % p; B[x][x] = (B[x][x] + Q) % p; B[y][y] = (B[y][y] + Q) % p; } for (int i = 1; i <= n; i++) if (get(i) != get(1)) { puts("0"); return 0; } Inv(n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = K[i][j + n]; gauss(n - 1); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = -a[i][j]; poly(n - 1); int x = 1, X = 1, ans = 0; A = inv(A); for (int i = 0; i <= n; i++) { if (x == 1) X = t; else X = 1ll * (inv(x, t) - 1) * inv(x - 1) % p; ans = (ans + 1ll * X * b[n - 1][i]) % p; x = 1ll * x * A % p; } if (~n & 1) C = -C; ans = 1ll * ans * C % p; ans = (ans + p) % p; printf("%d\n", ans); return 0; }
C
结论是,输出所有的 。其中设答案数量为 。
有递推式 ,考虑把答案分成两类:
- ,那么有 ,和 ,其中后者方案数为 。
- ,那么有 ,和 ,其中后者方案数为
所以总共增加的方案数为 种,满足递推式。相应的,就可以求出通项公式:
$$
化简即可发现满足要求。
#include <bits/stdc++.h> using namespace std; int n, m, x, y, z; int main() { int i, j; cin >> n; int k; m = (n * (n - 1) / 2.0 - n) / 3.0 + 1; cout << m << endl; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { k = n - i - j; if (k <= 0) k += n; if (k > j) printf("%d %d %d\n", i, j, k); } return 0; }
D
设 为转到 的概率, 表示从 变成 的期望次数, 表示转动一次能使 变大的概率。那么根据这一次转盘是否有效能得到以下式子:
$\mathcal O(n^2)$ 的。观察转移式发现只有可能从小往大转移,是有方向的。
若枚举一个分界线 ,我们想快速用 去贡献 。因为是异或卷积的形式,可以用 加速。于是在外面套一层 分治,每次用区间右边去贡献区间左边。时间复杂度 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = (1 << 16) + 5; const int p = 1000000007; int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % p; x = 1ll * x * x % p; base >>= 1; } return res; } void fwt(int *a, int *b, int n, int flag = 0) { for (int i = 0; i < n; ++i) b[i] = a[i]; for (int i = 0; (1 << i) < n; ++i) { int t = 1 << i; for (int j = 0; j < n; j += t << 1) { int *f = b + j, *g = b + j + t; for (int k = 0; k < t; ++k) { int s = g[k]; g[k] = (f[k] - s + p) % p; f[k] = (f[k] + s) % p; } } } if (flag) { int iv = inv(n); for (int i = 0; i < n; ++i) b[i] = 1ll * b[i] * iv % p; } } int f[N], g[N], a[N], b[N], c[N]; void solve(int l, int r) { if (l == r) { if (g[l]) f[l] = 1ll * (f[l] + 1) * inv(g[l]) % p; return; } int mid = (l + r) / 2; solve(mid + 1, r); int t = l ^ (mid + 1); fwt(a + t, b, mid + 1 - l); fwt(f + mid + 1, c, mid + 1 - l); for (int i = 0; i < mid + 1 - l; ++i) c[i] = 1ll * c[i] * b[i] % p; fwt(c, c, mid + 1 - l, 1); for (int i = l; i <= mid; ++i) f[i] = (f[i] + c[i - l]) % p, g[i] = (g[i] + b[0]) % p; solve(l, mid); } int T, n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> T; while (T--) { cin >> n; int sum = 0; for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i], f[i] = g[i] = 0; sum = inv(sum); for (int i = 0; i < n; ++i) a[i] = 1ll * sum * a[i] % p; solve(0, n - 1); cout << f[0] << endl; } return 0; }
E
首先有一个操作分块的做法。把每 个操作分成一段。每次整段操作完了后,重新求出 序,对于每种颜色分别开一个数组,每次进去二分子树区间查找答案。至于散块,每次暴力 即可。时间复杂度 。实现精细的话,能卡过。
考虑另一个比较正常一点的做法,子树操作转化为序列操作。但是因为有动态加叶子,所以需要一个能动态维护子树的数据结构。直接用 ,平衡树维护括号序即可,当然也可以是 。
每次新插入一个叶子,让他一定是父亲的第一个儿子。这样他的管辖范围的右端点一定是下一个兄弟,或者是父亲的右端点。插在后面的话还要更改前一个兄弟,前一个兄弟的儿子.......的右端点,比较麻烦。
维护真正的 肯定是不现实的,但是只需要知道 的相对大小关系。有一个想法是:点 插入到 之间时,令 。要卡也非常容易,同一个位置一直插入,很快就寄掉了。
我们需要选择一些时候暴力重构 ,以保证正确性。于是考虑替罪羊树。因为节点数为 ,重构因子为 的树,高度不超过 ,只要保证这个值小于 即可。然后对于每一个颜色开一个平衡树,差分维护答案。时间复杂度 ,空间复杂度 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 5e5 + 9; const double alpha = 0.7; int T, n, m, op, u, c, ans; struct scapegoat_tree { int rt, cnt, idx, id, fa, d; int ls[N], rs[N], sz[N], t[N], nt[N], ed[N]; ll l[N], r[N]; void reset() { rt = sz[1] = idx = 1; l[1] = ls[1] = rs[1] = nt[1] = ed[1] = 0; r[1] = l[0] = r[0] = 1e18; } void pushup(int u) { sz[u] = sz[ls[u]] + sz[rs[u]] + 1; } bool ok(int u) { return max(sz[ls[u]], sz[rs[u]]) >= sz[u] * alpha; } void dfs(int u) { if (ls[u]) dfs(ls[u]); t[++cnt] = u; if (rs[u]) dfs(rs[u]); } int build(int L, int R, ll x, ll y) { if (L > R) return 0; int mid = (L + R) >> 1, u = t[mid]; ll mid2 = (x + y) >> 1; l[u] = x, r[u] = y; ls[u] = build(L, mid - 1, x, mid2); rs[u] = build(mid + 1, R, mid2, y); pushup(u); return u; } void rebuild(int &u) { cnt = 0; dfs(u); u = build(1, cnt, l[u], r[u]); } void ins_(int &u, ll x, ll y, int Fa, int D) { if (!u) { sz[u = ++idx] = 1; ls[u] = rs[u] = 0; l[u] = x, r[u] = y; return; } ins_(ls[u], x, (x + y) >> 1, u, 0); pushup(u); if (ok(u)) id = u, fa = Fa, d = D; } void inss(int u, int x, int Fa, int D) { if (u == x) { ins_(rs[u], (l[u] + r[u]) >> 1, r[u], u, 1); pushup(u); if (ok(u)) id = u, fa = Fa, d = D; return; } if (l[x] + r[x] < l[u] + r[u]) inss(ls[u], x, u, 0); else inss(rs[u], x, u, 1); pushup(u); if (ok(u)) id = u, fa = Fa, d = D; } void ins(int u) { id = fa = d = 0; inss(rt, u, 0, 0); if (id) { if (id == rt) rebuild(rt); else if (d == 0) rebuild(ls[fa]); else rebuild(rs[fa]); } nt[idx] = ed[idx] = nt[u]; nt[u] = idx; } } T1; struct fhq_treap { int rt[N], ls[N], rs[N], sz[N], rd[N], idx, t[N], x, y, z; void pushup(int u) { sz[u] = sz[ls[u]] + sz[rs[u]] + 1; } void split(int u, int x, int &l, int &r) { if (!u) { l = r = 0; return; } if (T1.l[u] + T1.r[u] < T1.l[x] + T1.r[x]) l = u, split(rs[u], x, rs[u], r); else r = u, split(ls[u], x, l, ls[u]); pushup(u); } int merge(int u, int v) { if (!u || !v) return u ^ v; if (rd[u] < rd[v]) rs[u] = merge(rs[u], v); else ls[v] = merge(u, ls[v]), u = v; pushup(u); return u; } void ins(int c) { t[++idx] = c; ls[idx] = rs[idx] = 0; sz[idx] = 1; rd[idx] = rand(); split(rt[c], idx, x, y); rt[c] = merge(merge(x, idx), y); } int query(int c, int u) { split(rt[c], u, x, y); split(y, T1.ed[u], y, z); int res = sz[y]; rt[c] = merge(merge(x, y), z); return res; } void clear() { for (int i = 1; i <= idx; ++i) rt[t[i]] = 0; idx = 0; } } T2; int main() { srand(114514123); scanf("%d", &T); while (T--) { scanf("%d%d", &c, &m); T1.reset(), T2.ins(c); ans = 0; while (m--) { scanf("%d%d%d", &op, &u, &c); op ^= ans, u ^= ans, c ^= ans; if (op == 1) T1.ins(u), T2.ins(c); else printf("%d\n", ans = T2.query(c, u)); } T2.clear(); } return 0; }
F
有一个下界就是,总时间除以盘子数量上取整。设这个时间为 。
当 的时候, 把所有牛排尽可能多地塞进第一个盘子里,如果有一块塞不下了,就把它拆成两份,然后继续往第二个盘子里塞。所有烤盘按照塞进去的顺序开始烤就能到达这个下界。
当 的时候,显然是无法满足烤的时间最大的那块肉的,因为分在不同的烤盘里,时间会有重复的部分。一块牛排肯定不能在一个时间出现在两个烤盘上。只需要将时间调整为 即可。
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 9; int a[N], cnt = 1, lim = 0; int n, m; signed main() { scanf("%d%d", &n, &m); int sum = 0, t = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); t = max(t, a[i]); sum += a[i]; } t = max(t, (sum - 1) / m + 1); for (int i = 1; i <= n; i++) { if (t - lim < a[i]) { printf("2 %lld 0 %lld %lld %lld %lld\n", cnt + 1, a[i] - (t - lim), cnt, lim, t); cnt++; lim = lim + a[i] - t; } else { printf("1 %lld %lld %lld\n", cnt, lim, lim + a[i]); lim += a[i]; if (lim == t) cnt++, lim = 0; } }return 0; }
G
设 的边数为 ,分解 。
枚举一个质因子 ,统计两个数 并且 的方案数。
发现所有合法的 只需要满足 含有质数 的个数小于 。
也就是 个( 表示 的因子个数)。但是每次枚举所有的 不方便优化。不妨观察删掉上述 边构成的图。
发现居然是 个一模一样的图!那么 就有一个快速的计算方法,那就是枚举任意一个质因子 ,
$\rm min25$ 优化。
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 9; const int p = 1145140019; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } int n, f[N], g[N], d[N], w[N]; int T, pr[N], len; bool vis[N]; void init(int n = 1e5) { for (int i = 2; i <= n; ++i) { if (!vis[i]) pr[++len] = i, vis[i] = 1; for (int j = 1; j <= len; ++j) { if (pr[j] > n / i) break; vis[pr[j]*i] = 1; if (i % pr[j] == 0) break; } } } int cal() { int cnt = 0, t = sqrt(n), ml = 0; for (int i = 1; i <= n; i = n / (n / i) + 1) w[++cnt] = n / i; reverse(w + 1, w + cnt + 1); for (int i = 1; i <= cnt; ++i) g[i] = w[i] - 1; for (int i = 1; i <= len; ++i, ++ml) { int P = pr[i]; if (P > t) break; for (int j = cnt; j; --j) { int l = w[j] / P; if (l < P) break; l = l <= t ? l : cnt - n / l + 1; g[j] = (g[j] + p - g[l] + i - 1) % p; } } for (int i = 1; i <= cnt; ++i) f[i] = g[i], d[i] = (2 * f[i]) % p; for (int i = ml; i >= 1; --i) { int P = pr[i]; for (int j = cnt; j; --j) { int l = w[j] / P; if (l < P) break; for (int c = 1; l >= P; ++c, l /= P) { int pos = l <= t ? l : cnt - n / l + 1; d[j] = (d[j] + (c + 1) * (d[pos] + p - 2LL * i) % p + c + 2) % p, f[j] = (f[j] + (c + 1) * (f[pos] + p - i) % p + c * (d[pos] + p - 2ll * i) % p + c + 1) % p; } } } return f[cnt]; } signed main() { T = read(); init(); while (T--) { n = read(); printf("%lld\n", cal()); } return 0; }
H
若把互相能到达的点看成同一个点,那么不同的点只有 个。于是将整个坐标系用 大小的矩形分割开来,然后将所有矩阵重合于以 为左下角,大小为 的矩阵。若存在一个点未被覆盖,那么他就是合法答案。
一个输入的矩形最多会被分成 部分,暴力拆解,然后用扫描线做一遍矩形并即可。按照 坐标扫,维护区间最小值是否为 。时间复杂度 。
#include <bits/stdc++.h> #define y1 qweqdfrgedt using namespace std; const int N = 1e5 + 9; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } struct node { int L, R; }; struct Seg { #define ls p<<1 #define rs p<<1|1 int mn[N << 2], tag[N << 2], L, R, W; void push_up(int p) { mn[p] = min(mn[ls], mn[rs]); } void push_down(int p) { if (tag[p]) { tag[ls] += tag[p], mn[ls] += tag[p]; tag[rs] += tag[p], mn[rs] += tag[p]; tag[p] = 0; } } void change(int p, int l, int r) { if (l >= L && r <= R) { mn[p] += W, tag[p] += W; return; } push_down(p); int mid = (l + r) >> 1; if (L <= mid) change(ls, l, mid); if (R > mid) change(rs, mid + 1, r); push_up(p); } int get(int p, int l, int r) { if (l == r) return l; int mid = (l + r) >> 1; push_down(p); if (!mn[ls]) return get(ls, l, mid); else return get(rs, mid + 1, r); } int query1(int n) { if (mn[1]) return -1; return get(1, 1, n) - 1; } } T; vector<node> Add[N], Del[N]; int n, d; void get(int &x) { x = (x % d + d) % d; } void push(int x1, int x2, int y1, int y2) { if (x1 >= x2 || y1 >= y2) return; Add[x1].push_back(node{y1 + 1, y2}); Del[x2].push_back(node{y1 + 1, y2}); } void add(int x1, int x2, int y1, int y2) { if (y2 - y1 >= d) { push(x1, x2, 0, d); return; } get(y1), get(y2); if (y1 > y2) { push(x1, x2, y1, d), push(x1, x2, 0, y2); } else push(x1, x2, y1, y2); } signed main() { int x1, y1, x2, y2; n = read(), d = read(); for (int i = 0; i < n; i++) { x1 = read(), y1 = read(), x2 = read(), y2 = read(); if (x2 - x1 >= d) { add(0, d, y1, y2); continue; } get(x1), get(x2); if (x1 > x2) { add(x1, d, y1, y2), add(0, x2, y1, y2); } else add(x1, x2, y1, y2); } for (int i = 0; i < d; i++) { for (auto x : Add[i]) T.L = x.L, T.R = x.R, T.W = 1, T.change(1, 1, d); for (auto x : Del[i]) T.L = x.L, T.R = x.R, T.W = -1, T.change(1, 1, d); int y = T.query1(d); if (y != -1) { printf("YES\n%d %d\n", i, y); return 0; } } puts("NO"); return 0; }
I
因为有区间并的补等于区间补的交,所以直接输出每一段未被区间覆盖的区间的补即可。
#include <bits/stdc++.h> using namespace std; const int N = 1010; pair<int, int> p[N]; int main() { int t, n, m, l, r; cin >> t; while (t--) { cin >> n >> m; for (int i = 0; i < m; i++) { cin >> p[i].first >> p[i].second; } cout << m << endl; sort(p, p + m); for (int i = 0; i < m; i++) { cout << p[i].first << " " << p[(m + i - 1) % m].second << endl; } } return 0; }
J
对于一个大小为偶数的连通块是不会操作的。
对于一个大小为奇数的连通块,想贪心只删去一个点。当这个点不是割点时,显然是可行的。否则,需要考虑删去这个点后剩下的每个连通块的答案。
显然,对于一个连通块不会同时分离出割点和非割点。否则只分离非割点是更优的选择。
考虑任意一种删去割点的方案,需要满足若删去这些被选择的割点,剩下的每个连通块大小必须是偶数(不然就不止删这些点),从而得到,选择的割点个数一定是奇数(奇+偶=奇)。
并且当选择割点数大于等于 的时候,总能选择出两个割点,满足它们之间存在一条路径不经过其他割点。同时不选择它们,会发现仍然满足剩下的每个连通块大小是偶数的条件,并且答案更优了!
所以对于一个大小为奇数的连通块,若删去割点,只会删去一个。那枚举所有割点,看删掉后剩下连通块大小是否都是偶数,然后和每个非割点的答案取最优即可。时间复杂度 。
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e6 + 9; int n, m, T, mn, idx; int dfn[N], low[N], a[N], sz[N]; vector<int>e[N]; void chmn(int &x, int y) { (x > y) &&(x = y); } int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } void dfs(int x, int fa) { sz[x] = 1; int flag = 1; dfn[x] = low[x] = ++idx; for (int to : e[x]) { if (to != fa) if (!dfn[to]) { dfs(to, x); low[x] = min(low[x], low[to]); sz[x] += sz[to]; if (low[to] >= dfn[x] && (sz[to] & 1)) flag = 0; } else chmn(low[x], dfn[to]); } if (flag) chmn(mn, a[x]); } signed main() { T = read(); while (T--) { n = read(), m = read(); int sum = 0; mn = 1e18; for (int i = 1; i <= n; i++) { a[i] = read(); sum += a[i]; e[i].clear(); dfn[i] = 0; } for (int i = 1; i <= m; i++) { int x, y; x = read(), y = read(); e[x].push_back(y); e[y].push_back(x); } if (n % 2 == 0) printf("%lld\n", sum); else { idx = 0; dfs(1, 0); printf("%lld\n", sum - mn * 2); } } }
K
首先,不考虑数据范围,有如下几个做法:
暴力树剖,维护区间左右端点选不选然后合并,时间复杂度 .
倍增,维护 往上跳 的答案。时间复杂度都是 。空间复杂度
但是考虑这题数据范围,需要一个 回答询问的算法。
对于序列上的问题,用猫树在每个区间维护所有点到中点的答案,查询时找到 的 ,即可 回答询问。
发现猫树的思想是,每次选择中点,然后递归下去,类似于 分治。那相应的,在树上就选择重心,然后递归处理子树,像点分治那样。这样询问也是 的。预处理时空复杂度都是 。
具体实现时需要 LCA 。
#include <bits/stdc++.h> #define ll long long #define PII pair<int,int> using namespace std; const int P = 998244353; const int N = 5e5 + 9; int max(int x, int y) { return x > y ? x : y; } struct Rand { unsigned int n, seed; Rand(unsigned int n, unsigned int seed) : n(n), seed(seed) {} int get(long long lastans) { seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return (seed ^ lastans) % n + 1; } }; int n, a[N], sz[N]; vector<int> e[N]; bool vis[N]; void getSize(int x, int p) { sz[x] = 1; for (int y : e[x]) { if (y == p || vis[y]) continue; getSize(y, x); sz[x] += sz[y]; } } int getrt(int x, int p, int s) { for (int y : e[x]) { if (y == p || vis[y] || sz[y] * 2 < s) continue; return getrt(y, x, s); } return x; } ll f[20][N][2], dp[N][2][2]; int fa[20][N]; void dfs(int x, int p, int d, int r) { fa[d][x] = r; f[d][x][0] = max(dp[x][0][0], dp[x][0][1]); f[d][x][1] = max(dp[x][1][0], dp[x][1][1]); for (int y : e[x]) { if (y == p || vis[y]) continue; dp[y][0][0] = max(dp[x][0][0], dp[x][0][1]); dp[y][0][1] = dp[x][0][0] + a[y]; dp[y][1][0] = max(dp[x][1][0], dp[x][1][1]); dp[y][1][1] = dp[x][1][0] + a[y]; dfs(y, x, d, r); } } void solve(int x, int d) { getSize(x, 0); x = getrt(x, 0, sz[x]); dp[x][0][0] = 0; dp[x][0][1] = dp[x][1][0] = -1e18; dp[x][1][1] = a[x]; dfs(x, 0, d, x); vis[x] = true; for (int y : e[x]) { if (vis[y]) continue; solve(y, d + 1); } } ll calc(int x, int y) { if (x == y) return a[x]; for (int i = 0; i < 20; i++) { if (fa[i + 1][x] != fa[i + 1][y]) { int p = fa[i][x]; return max(f[i][x][1] + f[i][y][1] - a[p], f[i][x][0] + f[i][y][0]); } }return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, seed; cin >> n >> m >> seed; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2, x; i <= n; i++) { cin >> x; e[x].push_back(i); e[i].push_back(x); } solve(1, 0); ll lastans = 0, ans = 0; Rand rand(n, seed); for (int i = 0; i < m; i++) { int u = rand.get(lastans); int v = rand.get(lastans); int x = rand.get(lastans); lastans = calc(u, v); ans = (ans + lastans % P * x) % P; } cout << ans << "\n"; return 0; }
全部评论
(0) 回帖