2020牛客暑期多校训练营（第九场） task:7/8/12, rank:32/1041

2020牛客暑期多校训练营（第十场） task:3/3/10, rank:140/986

2019 Multi-University Training Contest 1

AGC047C

• 分类：数论，卷积
• 题意：给一堆数，求两两乘积模某质数 p 的和。
• 做法：把数用原根的幂表示，然后当多项式卷起来。
• 评论：比较经典的转化。

CF1372 E

• 分类：区间DP
• 题意：给定一个n*m的网格，每一行都分为若干组，每组中可以选一个位置填1，求每列1的数量的平方的最大值。
• 做法：区间DP，$dp[l][r]$ 表示仅使用完全包含于 $[l, r]$ 的组可以达到的最大值。暴力转移。
• 评论：dp很容易想到，但是这个仅使用完全包含于 $[l, r]$ 的组这一限制不好想。

HDU6583

• 分类：SAM，DP
• 题意：给定字符串 每次可以添加一个字符花费P 也可以复制前面一段花费Q 求最小构成该串的代价
• 解法：考虑dp过程 f(i)＝Min{f(i-1)+P,f(i-j)+Q(j满足i-j到i这一段串在之前出现过)} 考虑如何求出最大的j 可以对原串构建SAM 记录每个节点匹配的位置 如果这个位置不能满足就跳到parent节点继续匹配 全部跳的过程复杂度是O(串长)
• 评论：sam上的操作不太熟悉 写了半天才调出来 hdu上还爆栈了

__builtin

AGC047

SRM305A, AGC047A, AGC047B, AGC047C, AGC047E1

无

无

CF1372 E

Codeforces Round #663 (Div. 2)

AtCoder Grand Contest 047

AtCoder Grand Contest 047 A,B,C

Codeforces Round #663 (Div. 2) A,B,C,D,E

Codeforces Round #662 (Div. 2) C,D,E1,E2