2020牛客暑期多校训练营（第五场） task:5/5/11, rank:71 / 1145

2020牛客暑期多校训练营（第六场） task:5/6/11, rank:95 / 1120

2020/07/30 CF Mashup Training　　task:16/16/26

CF555C

• 分类：平衡树 / 线段树
• 题意：给一个 $n\times n$ 尺寸的上三角方格。有 $q$ 个操作。每次操作选择一个副对角线上的格子，指定一个方向，从副对角线上的格子开始对这个方向上的格子全部染色，直至碰见边界，或者遇见在之前的查询中染过色的格子为止。对每个操作需要输出在该次操作中被染色的格子数。$1\le n\le 10^9, 1\le q\le 2\times 10^5$
• 解法：平衡树维护斜线区间对应的图形形状 / 离散化后用线段树维护每行和每列的限制
• 评论：平衡树的做法比较自然好想

CF543 Div1 D

• 分类：换根dp
• 题意：树上黑白染色，要求所有点到根的路径上至多只有一个黑边。对于每个点，求出以它为根节点时的方案数
• 解法：如果只有一个根，可以考虑 $O(n)$ 的dp：$dp[x] = \prod(dp[son[x]]+1)$，将树根移动时仅会影响两个点的dp数组，可以 $O(1)$的计算出新根的答案。所以dp完了再遍历一次就得到答案了。
• 评论：有一个坑点是 $dp[son[x]] + 1$ 在模意义下可能为 $0$，然后你换根的时候如果用逆元去做除法就GG了。正确的处理方法应该是预处理出前缀和后缀的乘积加速计算。

CF543 Div1 C

• 分类：状压dp
• 题意：n个长m的串，$(1\le n,m \le 20)$修改每一个位置的串需要$v_{i,j}$的代价，问最小的代价使得每个串只要有一位满足它与其余串的该位都不相同
• 解法：状压表示已经处理过的串，枚举状态每次只更改最小的没有被处理的串，对于该串，枚举每一位，要么更改这一位的字母，要么更改所有串这一位上与它字母相同的串并且保留更改代价最小的，这样的贪心可以使总代价最小
• 评论：n,m比较小，以为是网络流，建了好多边也没跑对，dp的思路是比较明显的

无

M-SOLUTIONS Programming Contest 2020

SRM 788

Educational Codeforces Round 92 (Rated for Div. 2)

SRM788d2A, SRM788d2B, SRM788d2C, SRM301B, SRM302A, SRM302B, SRM303A

CF551D, CF552C, CF552D, CF552E, CF555C, CF555D

CF1389A, CF1389B, CF1389C, CF1389D, CF1389E

无

M-SOLUTIONS Programming Contest 2020

SRM 788

Codeforces Round #660 (Div. 2)

Codeforces 660 div2 A,B,C,D

CF543D CF550D CF550E CF551C CF555B

广义后缀自动机(还没看完)

M-SOLUTIONS Programming Contest 2020

SRM 788

Codeforces Round #660 (Div. 2)

SRM788 div1 A, SRM788 div1 B

cf 660div2 A,B,C,D