Posts

[CF] E. Mycraft Sand Sort - Codeforces Round 1005 (Div. 2)

https://codeforces.com/contest/2064/problem/E 题目大意 给出 n 长的排列 pn 长的颜色数组 c。从上到下,从 i=1npi 个颜色为 ci 的左侧对齐横向排列,之后让其按照重力规则下落,问有多少个不同的排列和颜色方案的二元组,可以得到和题目给出的排列颜色

[CF] C. Vasya And The Mushrooms - Educational Codeforces Round 48 (Rated for Div. 2)

https://codeforces.com/contest/1016/problem/C 题目大意 给出一个 2×n 的矩阵,矩阵上每个位置有一个数字,代表每秒会多出 ai,j 的价值。第 0s 从左上角出发,每次到达一个格子的时刻取到当前的价值,每一秒要强制走到某一个相邻的格子(四联通),问不重复的走完所

[CF] B. Segment Occurrences - Educational Codeforces Round 48 (Rated for Div. 2)

https://codeforces.com/contest/1016/problem/B 题目大意 给出 n 长小写字符串 sm 长小写字符串 t。给出 q 组询问,每组询问给出 li,ri,问 s[li,ri] 子串中 t 出现了几次。 1n,m1000,1q105。 简要题解 只要把所有匹配位置的尾巴标记为 1,这样

[CF] B. Variety is Discouraged - Codeforces Round 1005 (Div. 2)

https://codeforces.com/contest/2064/problem/B 题目大意 给出 n 长的不含 0 的数组 a。定义一个数组的权值为其长度减去不重复元素个数。 可以最多删除数组中连续的一个非空子段。问怎样删可以使得权值最大。不删最好时返回 0,否则返回删除的区间端点。多个

[CF] C. Remove the Ends - Codeforces Round 1005 (Div. 2)

https://codeforces.com/contest/2064/problem/C 题目大意 给出 n 长的不含 0 的数组 a。每次可以选择当前一个正数 ai 将其加到答案,并将数组的 i 结束的前缀删掉,或者选择某个负数 aiai 加到答案,并将 i 开始的后缀删掉。问可以得到的最大答案是多少。 $1 \le n \le

[CF] D. Eating - Codeforces Round 1005 (Div. 2)

https://codeforces.com/contest/2064/problem/D 题目大意 给出一个 n 长的数组 a,和 q 个独立询问(每次询问结束恢复 a)。对于某个询问,给出 x,然后如果 x 不小于 a 最后的元素 alast 则把 x 变为 x xoralast 并删掉 alast,问这个操作能进行几次

[CF] C. Brutality - Educational Codeforces Round 59 (Rated for Div. 2)

https://codeforces.com/contest/1107/problem/C 题目大意 给出 n 长的小写字符的串 S 和数组 a。给出某个 k,需要删掉字符串中的某些字符,使得最终串连续的相同字符个数不会超过 k。问最后保留下的字符的下标对应的 ai 的和最大是多少。 $1 \le k \le n \le 2 \times

[CF] D. Compression - Educational Codeforces Round 59 (Rated for Div. 2)

https://codeforces.com/contest/1107/problem/D 题目大意 给出一个 n×n01 矩阵 A。规定 BA 的一个 x 压缩矩阵,如果 x|n 以及 A[i][j]=B[ix][jx]1-indexed)。 4n5200,且 4|nA 按照每行每 4 位压缩成一个十六

[CF] E. Vasya and Binary String - Educational Codeforces Round 59 (Rated for Div. 2)

https://codeforces.com/contest/1107/problem/E 题目大意 给出一个 n 长的 01S 和数组 a。每次操作可以从中删除一个连续的,相同字符的段,并把剩余的段按顺序连起来。每次删掉 len 长的段的收益为 alen,问最大收益是多少。 1n100。$1

[CF] A. Object Identification - Codeforces Round 1004 (Div. 1)

https://codeforces.com/contest/2066/problem/A 题目大意 给出 n 长的数组 x 和某个隐藏的确定的数组 y。保证 xiyi,i(xi,yi)(xj,yj),ij 。对于每组数据,背后有一个隐藏的对象是以下两种之一: Obj A: 一个 n 个点的有向图当且仅当存在有向边 (xi,yi) Obj B: n 个点在二

[CF] B. Minimization - Codeforces Round 317 [AimFund Thanks-Round] (Div. 1)

https://codeforces.com/contest/571/problem/B 题目大意 给出 n 长的数组 a,及某数 k,可以任意调整 a 中元素位置,需要最小化 nki=1|a[i]a[i+k]| 。 问这个最小值是多少。 2n3×1051min(5000,n1)109a[i]109

[CF] D. Cubes - Codeforces Round 295 (Div. 2)

https://codeforces.com/contest/520/problem/D 题目大意 给出 n 个立方体(其实可能叫正方形更好,因为其实只需要考虑 2 维),考虑 OX 是地面,OY 是向上的方向。每个立方体用 (x,y) 表示其位置。定义某个立方体是稳定的当且仅当: 立方体在地面上(x=0) 其

[CF] H. Bro Thinks He's Him - Codeforces Round 1003 (Div. 4)

https://codeforces.com/contest/2065/problem/H 题目大意 给出一个 01 字符串 sq 次询问,每次询问将 vi 位置的字符翻转(询问不独立),之后询问这个串由下述函数算出的值是多少。 f(S) 表示 S 由多少个连续的相同字符的段,比如 0011000100,11,000,1 这样的 4 段。 g(S) 表示对于 S

[CF] F. Topforces Strikes Back - Codeforces Round 570 (Div. 3)

https://codeforces.com/contest/1183/problem/F 题目大意 给出 n 个数最多选出其中 3 个,使得选出的数两两之间不是整数倍,问选出的和最大是多少。 1n2×1052ai2×105。 简要题解 复杂度 TO() SO() 代码实现

[CF] C. Good String - Educational Codeforces Round 92 (Rated for Div. 2)

https://codeforces.com/contest/1389/problem/C 题目大意 给出字符串 S 问最少删掉其中多少个字符,可以使得它向左循环移动一位和向右循环移动一位的串相同。 2|S|2×105 简要题解 观察: 2 长的串一定行 同一个字符的串一定行 两种字符交替的偶数长的串一定行 其实这

[CF] B. Array Walk - Educational Codeforces Round 92 (Rated for Div. 2)

https://codeforces.com/contest/1389/problem/B 题目大意 给出 n 长的数组 a,可以用下述操作走 k 步,其中最多 z 步向左,问最大可以取到的权值。 每次操作可以进行两种中的一种: 向右走。现在在 xx<n,权值增加 a[x+1] 之后走到 x+1。 向左走。现在在 x

[CF] A. LCM Problem - Educational Codeforces Round 92 (Rated for Div. 2)

https://codeforces.com/contest/1389/problem/A 题目大意 给出 l,r 求任意 x,y 使得 lx<yrllcm(x,y)r。无解输出 ‘-1 -1’。 1l<r109。 简要题解 考虑较小的 xlcm 一定比它大,而比他大的最小的 lcm(x,y)=2x

[CF] D. AB-string - Educational Codeforces Round 74 (Rated for Div. 2)

https://codeforces.com/contest/1238/problem/D 题目大意 给出 n 长的只包含 ‘AB’ 的字符串 S。 定义一个字符串是好的:字符串中所有字符都可以是某个(不同字符不用是同一个)长度至少为 2 的回文串的一部分。 问 S 有多少个好的子串。 |S|3×105。 简要题解 观

[CF] C. Customer Service - Codeforces Round 1002 (Div. 2)

https://codeforces.com/contest/2059/problem/C 题目大意 给出 nn 长的数组 ai。进行如下操作 n 轮,在第 i 轮,选择某个 j,使得 aj,k=0 (ki)。即把某选择的行的开始一段小于 i 的元素刷成 0n 轮进行完之后设 bi=ai,j,则问可以任选

[CF] B. Cost of the Array - Codeforces Round 1002 (Div. 2)

https://codeforces.com/contest/2059/problem/B 题目大意 给出 n 长的数组 a。给出偶数 k,要求将 a 分为连续的 k 个非空子段。将第偶数段(1-based)按照原来的顺序链接起来并在结尾追加一个 1。定义这个新数组 b 的分值为,最小的下标 i 使得