~

A.G.H.I.略。 J.找到 $k(k+1)$ 的不同质因数个数。 K.L.

A.给出集合 $a_i…a_j, 1 \leq i \leq j \leq n$ 的 and 值构成的集合 $b$，构造一个 $k \leq 5n$ 且满足条件的序列。 考虑合法条件一定是 $a_i$ 都是 $\min{b}$ 的超集，否则全局不符合条件。 所以构造 $b_0, b_i$ 交替即可。 12345678910111213141516171819202122232425void solve() { int n; cin >> n; vi a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(all(a)); bool ok = true; for (int i = 0; i < n; i++) { if ((a[i] & a[0]) == a[0]) { } else { ok = false; break; } } if ...

多测，$T \leq 100, M \leq 100, N \leq 100$ 给出 $M$ 个 $N$ 维空间中的点，满足两两之间距离为 1。 最多能再加入多少个点，使得仍然满足两两之间距离为 1，输出方案。 解决第一个问题，考虑归纳一下，在一维的时候，可以是一个直线，然后每加一维都可以多一个点。所以答案是 $M-N+1$。 然后考虑目前有 $C$ 个点，随机出来一个 $N$ 维点和这 $C$ 个点很大概率线性无关。所以我们可以容易的找到这个点。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061using ar = valarray<double>;double dot(const ar &x, const ar &y) { double res = 0; rep(i, sz(x)) res += 1. * x[i] * y[i]; return res; ...

Codeforces Round 901 (Div. 1) A.考虑奇偶性，贪心就可以。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include <bits/stdc++.h>#ifndef LOCAL#define debug(...) 42#else#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#endif#define rep1(a) for (int i = 0; i < a; i++)#define rep2(i, a) for (int i = 0; i < a; i++)#define rep3 ...

A.模拟题。 B. 如果全部相等，输出 0 如果最小值为 1，那么一定不可能，输出 -1 剩下的情况必定有解，考虑每次用所有大于最小值的数字除掉最小值，最多不会超过 log 次。 C.给一个字符串 $s$，排列成一个字符串 $t$，令 $t_{max} = \max{t, rev(t)}$。 输出最小的 $t_{max}$。 经过转化题意：求 $s$ 排列字典序最小的，且反转后的字典序小于等于本身的字符串。 考虑构造，显然可以从小枚举到大枚举 $s$ 的所有字符。 假设当前枚举到 $x$，若 $x$ 还剩下至少两个，则前缀后缀都加上 $x$。 若除 $x$ 还剩下另一种字符 $y$，先加上$\frac{cnt_y}{2}$ 个 $y$ 再加上 $x$ 再加上 $\frac{cnt_y}{2}$ 个 $y$。 否则按顺序随意添加即可。 123456789101112131415161718192021222324252627282930313233343536373839404142void run_case() { string s; cin >> ...

选择一个 $i$，replace $a_i$ with $\lceil \frac{a_i}{2} \rceil$ 选择一个 $i$，replace $a_i$ with $\max(a_i - b, 0)$ 每个 $i$ 最多进行一次相同的操作。 sol1https://codeforces.com/contest/1799/submission/218644087 随机下标之后在期望选择数量附近 $dp$（这样正确率有保证），复杂度是 $O(K^2N)$，K 为在附近取多少个。 sol2https://codeforces.com/contest/1799/submission/221053633 考虑三分同时两种操作的个数，这个显然是一个凸函数。 可以采用 $agc018c$ 的 L-convex 的做法来做。 https://web.archive.org/web/20220813122625/https://opt-cp.com/agc018c-lconvex/ 1234567891011121314151617181920212223242526272829303132 ...

2022-2023 Winter Petrozavodsk Camp, Day 2: GP of ainta https://codeforces.com/gym/104427/attachments/download/20525/230201-tutorial.pdf A. Reversing只有周围同色的，才可能是被改过的，答案就是 $2^C$，C 是和周围颜色相同的点的个数。 B. Lawyers如果一个边不存在反向边，直接选即可，然后可以顺手选了剩下白给的点。 接下来就只有若干个全是双向边的连通块，然后看这个连通块里面的点数 $c$ 和 边数 $e$ 是否满足 $c \times 2 \leq e$。 C. One, Two, Three$O(N^2)$ 做法，考虑前 $i$ 个 1 肯定是 $(1,2,3)$，后面的都是 $(3,2,1)$，所以可以枚举 $i$。 $O(N)$ 做法:霍尔定理。 https://codeforces.com/gym/104427/attachments/download/20525/230201-tutorial.pdf D. Lonely ...

2021-2022 ACM-ICPC Latin American Regional Programming Contest

The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong) A. TreeScript先跑较小的子树，但是要留下 $p_i$，最后跑 $dp$ 值最大的子树 $v1$。 $dp_{u} = \max {dp_{v_1}, dp_{v_2}+1}$。 B. BigPicture被染色的必然是一个连通块。 对于每个没有被染色的连通块，恰好有一个格子的右边和下面都被染色。 所以前缀和计算即可，复杂度 $O(nm)$ C. PaintingGrid如果 NM 都是奇数，那么无解。 如果 $N > 2^M$ 或者 $M > 2^N$，那么无解（鸽笼原理）。 如果存在一个解。 首先可以先构造前 $\log m$ 行，$a_{i,j}$ 表示 $j$ 有没有 $2^i$ 这一位，然后放入一个取反列，这样可以满足黑白 1/2。 这样就可以保证每列不同，后面随意构造（也要放入取反列）就可以了。（只要满足行不相同） 如果 $n$ 是 ...

edu 打烂了。 A.检查 $w_1$。 B.12345678910111213141516void solve() { int N; cin >> N; vector<int> A(N); vector<int> B(N); for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < N; i++) { cin >> B[i]; } long long ans = 1ll * *min_element(A.begin(), A.end()) * N + accumulate(B.begin(), B.end(), 0LL); long long ans2 = 1ll * *min_element(B.begin(), B.end()) * N + accumulate(A.begin(), A.end(), 0LL); cout << min(an ...