2020-2021:teams:i_dont_know_png:week_summary_15
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/14 16:38] potassium 个人训练 |
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/15 17:20] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 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 ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ | ||
| 行 68: | 行 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 ^ | ||
| + | | 通过 | | √ | | | | | ||
| + | | 补题 | | | | | | | ||
| + | ==== 学习总结 ==== | ||
| + | |||
| + | 无 | ||
| 行 135: | 行 143: | ||
| ==== 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.1597394287.txt.gz · 最后更改: 2020/08/14 16:38 由 potassium
