2020-2021:teams:mian:weekly_report:2020_summer_week_7_report
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_7_report [2020/08/23 13:33] grapelemonade 创建 |
2020-2021:teams:mian:weekly_report:2020_summer_week_7_report [2020/08/28 22:52] (当前版本) gary |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020 Summer Week 6 Report ====== | + | ====== 2020 Summer Week 7 Report ====== |
| ====== 团队训练 ====== | ====== 团队训练 ====== | ||
| + | 无 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ===== Pantw ===== | ===== Pantw ===== | ||
| + | CFedu91G | ||
| + | |||
| + | * 分类：调和分析，结论题 | ||
| + | * 题意：一堆元素排成环，选 k 个打标记。行走时任意选取起点，顺时针行走，碰到标记即停止，获得权值为经过的元素的和，不包括最后一个。你可以重排元素顺序，任选标记位置，要求最小化期望权值，求该期望。 | ||
| + | * 做法：直接尽量在环上均分打标记，然后贪心的把大的放在接近标记的位置。观察下解的结构，可以直接枚举每段元素，前缀和即可。 | ||
| + | * 评论：结论比较好猜 | ||
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| + | |||
| + | 肝小学期去了（ | ||
| ===== 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的个数，统计即可 | ||
| + | |||
| + | * 评论：学了一手倒着推出交换前的序列 | ||
| ====== 个人训练 ====== | ====== 个人训练 ====== | ||
| 行 17: | 行 51: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | AtCoder Beginner Contest 176 | ||
| + | |||
| + | Educational Codeforces Round 94 (Rated for Div. 2) | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | TCO Round 2 (A, B) (1, 2, 3) | ||
| + | |||
| + | ABC175F, ABC176 (D, E, F) | ||
| + | |||
| + | CFedu91 (F, G), CFedu92F, CF664C, CFedu94 (C, D) | ||
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| + | |||
| + | 肝小学期去了， 摸了摸了 | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 摸了 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 摸了 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 被迫摸了（ | ||
| ===== Gary ===== | ===== Gary ===== | ||
| 行 34: | 行 83: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | [[http://codeforces.com/contest/1400|Educational Codeforces Round 94 ]] | ||
| + | |||
| + | [[https://atcoder.jp/contests/abc176|ABC176]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | Codeforces Global Round 10 A,C,D,E,F,G,H | ||
| + | |||
| + | ABC176 A,B,C,D,E | ||
| + | |||
2020-2021/teams/mian/weekly_report/2020_summer_week_7_report.1598160814.txt.gz · 最后更改: 2020/08/23 13:33 由 grapelemonade
