2020-2021:teams:mian:weekly_report:2020_summer_week_7_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_7_report [2020/08/28 16:59] withinlover [Withinlover] |
2020-2021:teams:mian:weekly_report:2020_summer_week_7_report [2020/08/28 22:52] (当前版本) gary |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ====== 团队训练 ====== | ====== 团队训练 ====== | ||
| + | 无 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 18: | 行 19: | ||
| ===== Gary ===== | ===== Gary ===== | ||
| + | [[http://codeforces.com/contest/1392/problem/G|CF1392G]] | ||
| + | |||
| + | * 分类：状压 | ||
| + | * 题意：给定两个串s和t，以及一个操作序列，序列中每项为交换s中的指定两位置，问使得s变成t串最小长度的连续操作序列 | ||
| + | * 解法： 不太会表述这个思路，找了一份比较详细的题解 | ||
| + | |||
| + | 记s串中1的数量为o1，t串中1的数量为o2， | ||
| + | |||
| + | 二者公共的1的数量为same，二者不相同的位数为x，相似度 | ||
| + | |||
| + | 则，o1+o2-2*same=x=y-k，为了最大化y，则最大化same， | ||
| + | |||
| + | dp[0][state]表示s串换成state这个状态最左端的操作下标 | ||
| + | |||
| + | dp[1][state]表示t串换成state这个状态最右端的操作下标 | ||
| + | |||
| + | 如果r-l>=m，说明[l+1,r]这段操作可行， | ||
| + | |||
| + | 但实际二者的state可能并不完全一致，所以sosdp枚举子集 | ||
| + | |||
| + | 倒序枚举子集并下放，找到state相同的满足r-l>=m的状态 | ||
| + | |||
| + | 其中state中1的个数被认为是最大公共1的个数，统计即可 | ||
| + | |||
| + | * 评论：学了一手倒着推出交换前的序列 | ||
| ====== 个人训练 ====== | ====== 个人训练 ====== | ||
| 行 48: | 行 74: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | [[https://atcoder.jp/contests/abc176|ABC176]] | + | 摸了 |
| ==== 题目 ==== | ==== 题目 ==== | ||
| - | ABC176 A,B,C,D,E | + | 被迫摸了（ |
| ===== Gary ===== | ===== Gary ===== | ||
2020-2021/teams/mian/weekly_report/2020_summer_week_7_report.1598605151.txt.gz · 最后更改: 2020/08/28 16:59 由 withinlover
