2020-2021:teams:i_dont_know_png:week_summary_15
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/13 16:23] nikkukun add nikkukun & future plan |
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/15 17:20] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ^ 比赛时间 ^ 比赛名称 ^ | ^ 比赛时间 ^ 比赛名称 ^ | ||
| - | | 2020.08.08 | [[multi2020-nowcoder-9 | 2020 Nowcoder Multi-University Training Contest 9]] | | + | | 2020.08.08 | [[multi2020-nowcoder-9|2020 Nowcoder Multi-University Training Contest 9]] | |
| - | | 2020.08.10 | [[multi2020-nowcoder-10 | 2020 Nowcoder Multi-University Training Contest 10]] | | + | | 2020.08.10 | [[multi2020-nowcoder-10|2020 Nowcoder Multi-University Training Contest 10]] | |
| 行 27: | 行 27: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **yukicoder contest 260 (Typical Game Contest)** | + | **2020.08.07 yukicoder contest 260 (Typical Game Contest)** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| | 通过 | √ | | | | | | | | 通过 | √ | | | | | | | ||
| - | | 补题 | | | | | | | | + | | 补题 | | √ | √ | √ | √ | | |
| - | 比较有做的价值的专题场，全都是玩游戏。部分个人觉得有价值的题目解析[[.:nikkukun:yukicoder-contest-260 | 见此]]。 | + | 比较有做的价值的专题场，全都是玩游戏。部分个人觉得有价值的题目解析[[.:nikkukun:yukicoder-contest-260|见此]]。 |
| - | **AtCoder Grand Contest 047** | + | **2020.08.09 AtCoder Grand Contest 047** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| | 通过 | √ | √ | √ | | | | | | 通过 | √ | √ | √ | | | | | ||
| - | | 补题 | | | | | | | | + | | 补题 | | | | √ | | | |
| - | **Codeforces Round #664 (Div. 1)** | + | **2020.08.12 Codeforces Round #664 (Div. 1)** |
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ |
| - | | 通过 | √ | | × | | | | | + | | 通过 | √ | | × | | | |
| - | | 补题 | | √ | √ | | | | | + | | 补题 | | √ | √ | √ | | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | === 路径覆盖问题 === | ||
| + | |||
| + | 考虑一些路径覆盖问题，如果可以转化为“一开始有很多路径，每合并一个节点上的两个路径可以优化答案”的形式，那么可以按节点考虑合并，可能会有想不到的效果。 | ||
| + | |||
| + | * **例子 1**（[[https://ac.nowcoder.com/acm/contest/5675/C|2020牛客暑期多校训练营（第十场）C - Decrement on the Tree]]）：给一棵有正边权的树，每次可以选一条路径整体权值 $-1$，用最小代价让边权全为 $0$。可以令初始答案为每个边覆盖 $w$ 条边，考虑节点上的合并减小答案。 | ||
| + | |||
| + | * **例子 2**（[[https://codeforces.com/contest/1394/problem/D|CF 1394D - Boboniu and Jianghu]]）：给一个点有权值和高度的树，定义好的路径是一条路上节点权值非降的路，选一些路径覆盖所有边，最小化每条路径上的点权和之和。做法是让一开始所有边都是单独的一条路径，然后每个节点内再尝试自己合并。当然合并过程是用到了 DP，但是这个思想是相同的。 | ||
| + | |||
| + | === 数学 === | ||
| + | |||
| + | 点乘和叉乘对于加法都满足分配律。 | ||
| 行 57: | 行 68: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | **2020.08.09 AtCoder Grand Contest 047** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| - | | 通过 | √ | | | | | | | + | | 通过 | √ | √ | | | | | |
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| - | ==== 学习总结 ==== | + | **2020.08.12 Codeforces Round #664 (Div. 1)** |
| + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ | ||
| + | | 通过 | | √ | | | | | ||
| + | | 补题 | | | | | | | ||
| + | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 75: | 行 93: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | [[.:potassium:sosdp | SOS DP 复习 ]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 正如 [[ https://www.hackerearth.com/zh/practice/algorithms/dynamic-programming/bit-masking/practice-problems/algorithm/special-pairs-7/ | Special Pairs]] 解法中的处理方法一样，当直接处理 $a_i \text{&} a_j=0$ 的按位不易处理时，可考虑 $a_j$ 必为 $\text{~}a_i$ 的子集，这样就可以转化成 SOSDP 进行处理了。 | ||
| 行 97: | 行 114: | ||
| ==== nikkukun ==== | ==== nikkukun ==== | ||
| - | [[https://atcoder.jp/contests/agc047/tasks/agc047_c | AGC 047 C - Product Modulo]] | + | [[https://atcoder.jp/contests/agc047/tasks/agc047_c|AGC 047 C - Product Modulo]] |
| * **题意**：已知 $P = 200\ 003$ 是质数。给 $n \leq 2 \times 10^5$ 的数列 $a_1, a_2, \ldots, a_n$，值域在 $[0, P)$，求 $\sum _{i=1}^n \sum _{j = i+1}^n (a_i \cdot a_j \bmod P)$。注意结果不需要对 $P$ 取模。 | * **题意**：已知 $P = 200\ 003$ 是质数。给 $n \leq 2 \times 10^5$ 的数列 $a_1, a_2, \ldots, a_n$，值域在 $[0, P)$，求 $\sum _{i=1}^n \sum _{j = i+1}^n (a_i \cdot a_j \bmod P)$。注意结果不需要对 $P$ 取模。 | ||
| - | * **题解**： | + | |
| - | * 如果存在一种卷积操作使得 $[x^n]H(x) = \sum _{i \cdot j = n} [x^i]F(x) \cdot [x^j]G(x)$，那么上面的问题就可以把每个数出现次数的多项式直接卷积做了。可以发现对数性质满足 $\log a + \log b = \log ab$，如果能将指数部分先映射到对数，普通卷积完再还原回来，那么就能实现上述卷积。 | + | * **题解**：如果存在一种卷积操作使得 $[x^n]H(x) = \sum _{i \cdot j = n} [x^i]F(x) \cdot [x^j]G(x)$，那么上面的问题就可以把每个数出现次数的多项式直接卷积做了。可以发现对数性质满足 $\log a + \log b = \log ab$，如果能将指数部分先映射到对数，普通卷积完再还原回来，那么就能实现上述卷积。 |
| - | * 经过测试发现 $2$ 是 $P$ 的一个原根，因此可以用 $\log_2(x)$ 进行映射。由于是指数上的运算，原根的循环节是 $\varphi(P) = P - 1$ 而不是 $P$，故做完多项式之后指数超出 $P - 1$ 的部分应当模一下 $P - 1$。 | + | |
| - | * 系数并不是很大，直接 FFT 精度也是足够的。 | + | * 经过测试发现 $2$ 是 $P$ 的一个原根，因此可以用 $\log_2(x)$ 进行映射。由于是指数上的运算，原根的循环节是 $\varphi(P) = P - 1$ 而不是 $P$，故做完多项式之后指数超出 $P - 1$ 的部分应当模一下 $P - 1$。 |
| + | |||
| + | * 系数并不是很大，直接 FFT 精度也是足够的。 | ||
| * **备注**：利用原根性质操作的妙妙题，即使赛场上想出来了也还是觉得很妙。 | * **备注**：利用原根性质操作的妙妙题，即使赛场上想出来了也还是觉得很妙。 | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6858|2020 Multi-University Training Contest 8 D - Discover of Cycles]] | ||
| + | |||
| + | * **题意**：给你一个 $3 \times 10^5$ 点边的无向图，$3 \times 10^5$ 次询问由 $[l, r]$ 编号的边构成的图中是否有环，强制在线。 | ||
| + | |||
| + | * **题解**：对每个左端点 $l$ 找最大右端点 $r$，使得 $[l, r]$ 边构成的图无环。可以注意到 $r$ 是单调不减的，因此用 LCT 维护 $[l, r]$ 构成的森林，每次移动 $r$ 就是查询连通性或加边，移动 $r$ 就是删边。 | ||
| + | |||
| + | * **备注**：如果一直想着如何维护区间内的环会越想越复杂，那么只要维护的东西结构比较简单就行了。类似的思想还有 CF 1394B，如果只考虑如何维护强连通分量，就会难以发现整个图实际是很多小环的性质。 | ||
| + | |||
| + | [[https://yukicoder.me/problems/no/1145|Yukicoder P1145 - Sum of Powers]] | ||
| + | |||
| + | * **题意**：给定 $a_1, a_2, \ldots, a_n$，对 $K = 1, 2, \ldots, n$ 求 $\sum _{i=1}^n a_i^K$ 模 $998\ 244\ 353$。 | ||
| + | * **题解**：注意到 $\sum _{i=1}^n a_i^K = [x^K]\sum _{i=1}^n (1 + a_i x + a_i^2 x^2+ \cdots) = [x^K]\sum _{i=1}^n \dfrac 1{1 - a_ix}$，然后后面的东西在二分树上 FFT 合并分子分母即可。 | ||
| + | * **备注**：看上去不像卷积的东西也可能用到多项式。 | ||
| + | |||
| ==== qxforever ==== | ==== qxforever ==== | ||
| - | [[题目链接 | 题目名称]] | + | [[https://codeforces.com/contest/1144/problem/G|CF 1144G]] |
| - | * **题意**： | + | * **题意**：给一个长度为 $n$ 的序列，问能否分成两个子序列，一个递增一个递减，$n,a_i\le 2\times 10^5$ |
| - | * **题解**： | + | * **题解**：设 $dp_{i,0}$ 表示到 $i$ 递增序列的末尾值，$dp_{i,1}$ 表示到 $i$ 递减序列的末尾值。转移是比较容易的。 |
| - | * **备注**： | + | * **备注**：算是经典以及常见的一种 dp 状态设计，但是第一次见到还是很难想到。 |
| ==== Potassium ==== | ==== Potassium ==== | ||
| - | [[题目链接 | 题目名称]] | + | [[https://codeforces.com/problemset/problem/1329/D|CF1329D Dreamoon Likes Strings]] |
| + | |||
| + | * **题意**：给一个字符串 $s(|s|\le 2e5)$，每次操作可以删除一段连续的、没有相邻两项相等的子串，求变为空串最少操作次数的方案。 | ||
| + | |||
| + | * **题解**：由于直接处理比较麻烦，考虑特殊处理连续相同字母进而转化问题。类似差分的过程，将 $s$ 相邻两项相同合并为一个字符，拼接成 $s'$ （如 $abbcccdaa$ 合并为 $bcca$），则对 $s'$ 进行两种操作（删除某个字符或删除相邻两个不同字符）到空后，一次删除操作即可将原串清零。故考虑如何进行这两种操作。 | ||
| + | |||
| + | * 这是一个经典问题，考虑字符 $c$，设 $c$ 的出现次数为 $cnt_c$ ，$S=\sum_i cnt_i$，则如果对于某个 $c$， $cnt_c>S-cnt_c$ 可将所有 $c$ 以外的字符与 $c$ 匹配后剩余 $c$ 进行删除；否则任意删除相邻两项直至出现上述情况。 | ||
| + | |||
| + | * **备注**：对字符串也可以进行这样类似差分的操作。 | ||
| + | |||
| - | * **题意**： | ||
| - | * **题解**： | ||
| - | * **备注**： | ||
2020-2021/teams/i_dont_know_png/week_summary_15.1597306983.txt.gz · 最后更改: 2020/08/13 16:23 由 nikkukun
