~

2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite A.令 $f_{u,k,0/1}$ 表示 $u$ 的子树里面有 $k$ 个叶子结点需要搜查，是否有一个另外的叶子结点需要通过修复 $u$ 的祖先结点的监控确定。 初始叶子结点: $f_{u,0,0}=a_u, f_{u,1,0}=f_{u,1,1}=f_{u,0,1}=0$。 $f_{u,k,0} = \min(\sum_{k_i} f_{v,k_i,0}, a_u + \sum_{k_i} \min(f_{v,k_i,0}, f_{v,k_i, 1}))$ $f_{u,k,1} = \min(\sum_{k_i} f_{v,k_i,0/1})$，1 最多只能有一个，不然无法确定。 $ans = \min(t_i + \min(f_{1,i,0}, f_{1,i,1}))$. 代码鸽了。 偷了个 mwh 的。 12345678910111213141516171819 ...

2023年中国大学生程序设计竞赛女生专场 A.模拟。 B.假设点在 $(a,b)$，做一条直线 $x=a$，然后查询 $(0,0)$ 到这个点的 $f(d_0)$，可以知道 $f(d)$ 在 $(x_0,0) \leq f(d_0), x0 \leq 2a$。 所以只需要二分出来第一个 $f(d) \geq f(d_0)$ 的位置即可。 对 $y=b$ 也做一次同样的操作。次数是 $2 \times \log$ C.对于一个 $1$ 为根的有向树，只需要套用模板。邻接矩阵减掉度数矩阵删掉第一行第一列。 剩下都是消元的东西了，变成一个下三角。 然后可以分块矩阵，就是把一个行列式当成一个值，直接对角线乘法就可以了。 最后是三种矩阵相乘。 具体过程在这里。 https://codeforces.com/gym/104725/attachments/download/22701/solution.pdf 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474 ...

Educational Codeforces Round 156 (Rated for Div. 2) A.x 从 1 枚举到 6，y 从 1 枚举到 6，判断 x,y,z 是否合法即可。 12345678910111213141516171819void solve() { int n; cin >> n; rep(a, 1, 6) { rep(b, a + 1, 6) { int c = n - a - b; if (c <= 0 || a % 3 == 0 || b % 3 == 0 || c % 3 == 0) { continue; } if (a == b || b == c || a == c) { continue; } cout << "YES\n"; cout << a << " " <&l ...

A.$p$ 最少要对一个人用。 也就是可以用小于等于 $n-1$ 个位置替换成小于等于 $p$ 的代价，贪心即可。 12345678910111213141516171819void solve() { int n, p; cin >> n >> p; vc<pii> a(n); rep(i, n) cin >> a[i].fi; rep(i, n) cin >> a[i].se; sort(all(a), [&](auto x, auto y) { return x.se < y.se; }); ll ans = 1ll * n * p; int rem = n - 1; for (auto [x, y] : a) { if (y < p) { ans -= 1ll * min(rem, x) * (p - y); rem = max(0, rem - x); } } cou ...

A1. 考虑将所有数字变成大于零的，可以前缀和。 考虑将所有数字变成小于零的，可以后缀和。 A2.按照 A1 的策略，倍增，分类讨论。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566void solve() { int n; cin >> n; vector<long long> a(n); vector<pair<int, int>> ans; rep (i, 0, n) cin >> a[i]; int pos = 0, neg = 0; rep (i, 0, n) if (a[i] > 0) pos += 1; rep (i, 0, n) if (a[i] < 0) neg += 1; auto print = [&]() { cout << ...

G.定义一次操作：随机选择 $i \in [1, n]$，对所有 $j \in [i, n]$，使得 $a_j = a_j + v$。 $n \leq 5000, m, v \leq 10^9$，m 为操作次数。 求 $\prod a_i$ 的期望值。 $\prod (ai+v+…)$ 每个括号里面选一个产生贡献，只有三种情况。 选择 $a_i$ 选择以前用过的 $v$，贡献系数为 $j \times v$，$j$ 为之前操作过的次数。 选择以前没有用过的 $v$，贡献系数为 $(m-j) \times i \times v$，$m - j$ 表示在没有选过的里面选一个，$i$ 表示可以操作在 $[1, i]$。 所以定义 $f_{i, j}$ 为目前长度为 $i$，使用了 $j$ 次操作的期望乘法值。 最后答案为 $\frac{\sum f_{i,j} \times n^{m-j}}{n^m}$。 12345678910111213141516171819202122232425262728293031323334const int P = 1e9 + 7;int p ...

A.答案显然是 $a_0\ \text{and}\ a_1…$。 B.贪心。 C.如果全是 $i \to n+1$，那么可以直接 $1…n+1$。 如果全是 $n+1 \to i$，那么可以直接 $n+1,1…n$。 否则考虑 $1..n+1…n$。 D.D1 可以直接能连就连 1234567891011121314vector<tuple<int, int>> edge; rep (i, 0, n) { rep (j, i, n) { if (find0(i) != find0(j) && find1(i) != find1(j)) { edge.emplace_back(i, j); p0[find0(i)] = find0(j); p1[find1(i)] = find1(j); } } } cout << (int) edge.size() << "\n"; for (int i = 0; i < ( ...