Warning: session_start(): open(/tmp/sess_e57fb36d6165a129e5caeacf0c054cc4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:i_dont_know_png:week_summary_15 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:i_dont_know_png:week_summary_15

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/14 16:50]
nikkukun
2020-2021:teams:i_dont_know_png:week_summary_15 [2020/08/15 17:20] (当前版本)
nikkukun
行 39: 行 39:
 ^  题目 ​ ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^ ^  题目 ​ ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
 |  通过 ​ |  √  |  √  |  √  |     ​| ​    ​| ​    | |  通过 ​ |  √  |  √  |  √  |     ​| ​    ​| ​    |
-|  补题 ​ |     ​| ​    ​| ​    ​| ​    ​|     ​| ​    |+|  补题 ​ |     ​| ​    ​| ​    ​| ​ ​√  ​|     ​| ​    |
  
 **2020.08.12 Codeforces Round #664 (Div. 1)** **2020.08.12 Codeforces Round #664 (Div. 1)**
行 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.1597395048.txt.gz · 最后更改: 2020/08/14 16:50 由 nikkukun