Codeforce Global Round 7[CF1326]
Codeforce Global Round 7总结。
Problem A
23333…
Problem B
直接递推即可。
Problem C
题意
给定一个长度为 $n$ 的排列 $a_n$。要求将这个序列分成互不相交的 $k$ 段。记第 $p$ 段的左端点和右端点分别为 $l_p,r_p$。要求最大化 $\sum_{i=1}^k\max_{j=l_i}^{r_i}{a_j}$。
输出最大化的值和可以最大化该值的方案数。方案数对 $998244353$ 取模。
$n\leq 2\times 10^5$
题解
最大化的值显然是 $\sum_{i=n-k+1}^ni$。
也就是说，每一段中肯定包含且仅包含一个这 $k$ 个点中的其中一个。
然后乘法原理。
时间复杂度 $O(n)$。
Problem D
题意
在一个字符串中，选一个前缀和后缀，满足其拼接起来是回文串，输出一个长度不超过 $n$ 的最长的回文串。
$|S|\leq 10^5$。
题解
枚举前后缀当中的最小值，满足前缀的反串等于后缀。这时候变成查询以某个串结尾的最长的不超过某个值的回文串长度。PAM上倍增跳fail链即可。