Training records

22/11/01

Problem - 1746D - Codeforces *1900 math

Problem - E1 - Codeforces *1500 math

Problem - E2 - Codeforces *1900 math

Problem - D1 - Codeforces *1400 greedy

Problem - D2 - Codeforces *2000 dp

22/11/02

Problem - D2 - Codeforces *2400 brute force

Problem - G1 - Codeforces *1900 trees

Problem - G2 - Codeforces *2000 trees

22/11/07

• 近期的做题重心放在补题上，增加作题难度，适当比赛训练

Problem - E - Codeforces *math, combinatorics

• 括号数数题

G - Count Sequences (atcoder.jp) *math, combinatorics

• 题意：$n$ 个数的序列 $a$，$0 \le a_1 \le a_2 \le ... \le a_n \le m$ ，且相邻两个数 %3 的余数不同。

• Sol ：首先将 $a$ 转化成 b ，令 $b_i = a_i - a_{i -1}$ （差分）

  对于 $i>1$ ，%3 的余数 只可能为 1 或 2

  我们继续转换，令$ {b_i = x_i + 3*y_i}$ ，其中 $x_i$ 是 %3 的余数。

  则有 $\sum_{}{y_i} \le \left \lfloor \frac{M-\sum{}{x_i}}{3} \right \rfloor $

  对于 $\sum{}{y_i} = t$ 的方案，即将 $t$ 个小球放进 $n$ 个袋子，袋子可为空的方案数：$C_{n+t-1}^{n-1} $

  而对于 $\sum{}{y_i} \le t$ 的方案，即 $C_{n+t}^{n}$

  这样，我们枚举所有 $x_i$ 中 $1$ 的数量，就可以得出 $t$

  特判一下当 $x_0 = 0$ 时，枚举剩余 $n-1$ 个位置中 $1$ 的数量。（分两种情况计算即可）

F - Many Many Paths (atcoder.jp) *math, combinatorics

22/11/08

2022 CCPC 威海

Problem - E - Codeforces *2900, math, combinatorics

• 题意：（转化后）从(0,0) 走到 (n,m) 的路径上，选出一些点构成点集，求本质不同的点集大小和。

• Sol：Codeforces Round #832 (Div. 2) E - FxorG - 博客园 (cnblogs.com)

神一般的计数trick。虽然解法应该有很多，只能说对于各种计数的策略会的太少了。

如果直接枚举点集，一个点集可能被多条不同的路径覆盖。想办法让它在所有的路径中只有一种合法的被计算一次。

我们首先钦定两个点之间是先向上再向右走，拐点是指向右再向上的点，这样我们确定了拐点之后，就确定了一条路径，且当拐点不同的时候路径一定不同。

这样对于一条路径，我们钦定拐点都选，其他点随便选。这样贡献就统计完了

Problem - C - Codeforces 简单题

Problem - D - Codeforces *1600 简单数学题

22/11/09

Problem - D - Codeforces *2100 tree, game, bit

• 题意：一个数，每人轮流取点，每次取的点必须和之前的相邻，且不能取已经选过的，且满足 $u\oplus v \le min(u,v)$，重新对节点编号，使得先手必胜的点最多。

• Sol：首先可以看出，两个相邻的点最高位不同就不能走。若一个点相邻的所有点最高位都与该点不同，就是一个必胜点。

  考虑将最高位不同的点分成不同的数集，如$n=9$ 时有：{1}, {2, 3}, {4, 5, 6, 7}, {8, 9}。

  对树做二分图染色，分成两个集合，若不同集合的点不能互相到达，则就是最优解。

  显然我们可以将拆分出来各位的数集，二进制拼成二分图较小的一边。

Problem - D - Codeforces *2000, 交互, 二分

Problem - D - Codeforces *2300 期望

• 状态数少所以存在循环，对于一个循环期望递推，发现可以消元。

Problem - E - Codeforces *2300 数学，贪心

• 题意：若一个序列中，元素的平均值是 $avg$ ，比 $avg$ 小的元素个数 大于等于 比 avg 大的元素个数，则称序列是好的。

  删去一些元素，使得该序列的所有子序列都是好的。

• Sol：由于是子序列，所以顺序不重要了。对于一个序列，如果从中任选三个数都满足是好的，则整个序列就是好的。

  对于 $a < b < c$，如果是好的，需满足 $c \ge 2b - a$ ，若加入一个数 $d$ 仍是好的，则需满足：

  $d \ge 2b - a $ 且 $d \ge 2c - a$ 且 $d \ge 2c - b$

  显然上述三个条件中只需要满足 $d \ge 2c-a$ 即可。

  我们枚举删除后最小的元素 $a$，则 $b$ 是大于 $a$ 的第一个数，$c$ 是大于等于 $2b-a$ 的第一个数，$d$ 是......

  在map中二分查找即可。由于每次找下一个数，整个序列的$max-min$扩大了一倍，所以复杂度$O(nlog(10^9))$

Problem - H - Codeforces *2400 暴力，置换环

• 题意：一个排列 $p_i$，两种操作：

  1、对 $x$ 进行 $k$ 次 $x=p_x$ 操作。

  2、$swap(p_x, p_y)$

• Sol：先处理操作$1$，令 $a_x$ 表示对 $x$ 进行 $Q$ 次操作，$Q \approx \sqrt{n} $ 。复杂度 $O(n \sqrt{n})$ ，令 $r_{p_x} = x$ （暴力分块）

  对于操作2，我们首先直接swap处理 $p_x,p_y$ 和 $r_{p_x},r_{p_y}$ ，对于 $a$ 数组，受影响的只有 $x$ 前面的 Q个 和 $y$ 前面 的 Q个，这一部分分别 $O(Q)$ 暴力处理即可。

Problem - E - Codeforces *2300 games, 贪心

• 题意：对于一个序列，每次可以选择相邻两个位置 -1，如果若干次操作能变成全0，就是一段好序列。求有多少个好的子序列。

• Sol：假设对于一段序列 $[l, r]$ ，从 $l$ 开始减，则有：

  $a_{l+1} - a_l \ge 0$

  $a_{l+2} - a_{l+1} + a_l \ge 0$

  $a_{l+3} - a_{l+2} + a_{l+1}-a_l \ge 0$

  $......$

  且对于最后一项需要满足 $...... = 0$ ，也就是整段区间的奇数位前缀和 = 偶数位前缀和。

  我们令 $c_x = \sum_{i=1}^{x}{(-1)^{i+1}a_i}$

  对于 $[l,r]$ 来说也就是：$c_r - c_{l-1} = 0$ ，即 $c_r = c_{l-1}$ 可以丢进一个map里来统计。

  对于另一个条件：奇数位置需要满足 ：$c_i - c_j \ge 0$，对于偶数位置则是：$-(c_i - c_j) \ge 0$ ，也就是对于map中的所有数都需要满足，奇数位置检查末尾元素，偶数位置检查头元素就可以了。