Warning: session_start(): open(/tmp/sess_a0f7c5afe4d83ccd78956e1f87cc64a3, 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/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020 Summer Week 7 Report ======
====== 团队训练 ======
无
====== 本周推荐 ======
===== Pantw =====
CFedu91G
* 分类:调和分析,结论题
* 题意:一堆元素排成环,选 k 个打标记。行走时任意选取起点,顺时针行走,碰到标记即停止,获得权值为经过的元素的和,不包括最后一个。你可以重排元素顺序,任选标记位置,要求最小化期望权值,求该期望。
* 做法:直接尽量在环上均分打标记,然后贪心的把大的放在接近标记的位置。观察下解的结构,可以直接枚举每段元素,前缀和即可。
* 评论:结论比较好猜
===== Withinlover =====
肝小学期去了(
===== 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的个数,统计即可
* 评论:学了一手倒着推出交换前的序列
====== 个人训练 ======
===== Pantw =====
==== 专题 ====
无
==== 比赛 ====
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 =====
肝小学期去了, 摸了摸了
==== 专题 ====
摸了
==== 比赛 ====
摸了
==== 题目 ====
被迫摸了(
===== Gary =====
==== 专题 ====
==== 比赛 ====
[[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