Posts
https://codeforces.com/contest/2064/problem/E 题目大意 给出 n 长的排列 p 和 n 长的颜色数组 c。从上到下,从 i=1∼n 将 pi 个颜色为 ci 的左侧对齐横向排列,之后让其按照重力规则下落,问有多少个不同的排列和颜色方案的二元组,可以得到和题目给出的排列颜色
https://codeforces.com/contest/1016/problem/C 题目大意 给出一个 2×n 的矩阵,矩阵上每个位置有一个数字,代表每秒会多出 ai,j 的价值。第 0s 从左上角出发,每次到达一个格子的时刻取到当前的价值,每一秒要强制走到某一个相邻的格子(四联通),问不重复的走完所
https://codeforces.com/contest/1016/problem/B 题目大意 给出 n 长小写字符串 s 和 m 长小写字符串 t。给出 q 组询问,每组询问给出 li,ri,问 s[li,ri] 子串中 t 出现了几次。 1≤n,m≤1000,1≤q≤105。 简要题解 只要把所有匹配位置的尾巴标记为 1,这样
https://codeforces.com/contest/2064/problem/B 题目大意 给出 n 长的不含 0 的数组 a。定义一个数组的权值为其长度减去不重复元素个数。 可以最多删除数组中连续的一个非空子段。问怎样删可以使得权值最大。不删最好时返回 0,否则返回删除的区间端点。多个
https://codeforces.com/contest/2064/problem/C 题目大意 给出 n 长的不含 0 的数组 a。每次可以选择当前一个正数 ai 将其加到答案,并将数组的 i 结束的前缀删掉,或者选择某个负数 ai 将 −ai 加到答案,并将 i 开始的后缀删掉。问可以得到的最大答案是多少。 $1 \le n \le
https://codeforces.com/contest/2064/problem/D 题目大意 给出一个 n 长的数组 a,和 q 个独立询问(每次询问结束恢复 a)。对于某个询问,给出 x,然后如果 x 不小于 a 最后的元素 alast 则把 x 变为 x xoralast 并删掉 alast,问这个操作能进行几次
https://codeforces.com/contest/1107/problem/C 题目大意 给出 n 长的小写字符的串 S 和数组 a。给出某个 k,需要删掉字符串中的某些字符,使得最终串连续的相同字符个数不会超过 k。问最后保留下的字符的下标对应的 ai 的和最大是多少。 $1 \le k \le n \le 2 \times
https://codeforces.com/contest/1107/problem/D 题目大意 给出一个 n×n 的 01 矩阵 A。规定 B 为 A 的一个 x 压缩矩阵,如果 x|n 以及 A[i][j]=B[⌈ix⌉][⌈jx⌉](1-indexed)。 4≤n≤5200,且 4|n。 A 按照每行每 4 位压缩成一个十六
https://codeforces.com/contest/1107/problem/E 题目大意 给出一个 n 长的 01 串 S 和数组 a。每次操作可以从中删除一个连续的,相同字符的段,并把剩余的段按顺序连起来。每次删掉 len 长的段的收益为 alen,问最大收益是多少。 1≤n≤100。$1
https://codeforces.com/contest/2066/problem/A 题目大意 给出 n 长的数组 x 和某个隐藏的确定的数组 y。保证 xi≠yi,∀i 且 (xi,yi)≠(xj,yj),∀i≠j 。对于每组数据,背后有一个隐藏的对象是以下两种之一: Obj A: 一个 n 个点的有向图当且仅当存在有向边 (xi,yi) Obj B: n 个点在二
https://codeforces.com/contest/571/problem/B 题目大意 给出 n 长的数组 a,及某数 k,可以任意调整 a 中元素位置,需要最小化 n−k∑i=1|a[i]−a[i+k]| 。 问这个最小值是多少。 2≤n≤3×105。1≤min(5000,n−1)。−109≤a[i]≤109
https://codeforces.com/contest/520/problem/D 题目大意 给出 n 个立方体(其实可能叫正方形更好,因为其实只需要考虑 2 维),考虑 OX 是地面,OY 是向上的方向。每个立方体用 (x,y) 表示其位置。定义某个立方体是稳定的当且仅当: 立方体在地面上(x=0) 其
https://codeforces.com/contest/2065/problem/H 题目大意 给出一个 01 字符串 s 和 q 次询问,每次询问将 vi 位置的字符翻转(询问不独立),之后询问这个串由下述函数算出的值是多少。 f(S) 表示 S 由多少个连续的相同字符的段,比如 00110001 有 00,11,000,1 这样的 4 段。 g(S) 表示对于 S 的
https://codeforces.com/contest/1183/problem/F 题目大意 给出 n 个数最多选出其中 3 个,使得选出的数两两之间不是整数倍,问选出的和最大是多少。 1≤n≤2×105。2≤ai≤2×105。 简要题解 复杂度 T:O() S:O() 代码实现
https://codeforces.com/contest/1389/problem/C 题目大意 给出字符串 S 问最少删掉其中多少个字符,可以使得它向左循环移动一位和向右循环移动一位的串相同。 2≤|S|≤2×105 简要题解 观察: 2 长的串一定行 同一个字符的串一定行 两种字符交替的偶数长的串一定行 其实这
https://codeforces.com/contest/1389/problem/B 题目大意 给出 n 长的数组 a,可以用下述操作走 k 步,其中最多 z 步向左,问最大可以取到的权值。 每次操作可以进行两种中的一种: 向右走。现在在 x 且 x<n,权值增加 a[x+1] 之后走到 x+1。 向左走。现在在 x
https://codeforces.com/contest/1389/problem/A 题目大意 给出 l,r 求任意 x,y 使得 l≤x<y≤r,l≤lcm(x,y)≤r。无解输出 ‘-1 -1’。 1≤l<r≤109。 简要题解 考虑较小的 x,lcm 一定比它大,而比他大的最小的 lcm(x,y)=2x。
https://codeforces.com/contest/1238/problem/D 题目大意 给出 n 长的只包含 ‘AB’ 的字符串 S。 定义一个字符串是好的:字符串中所有字符都可以是某个(不同字符不用是同一个)长度至少为 2 的回文串的一部分。 问 S 有多少个好的子串。 |S|≤3×105。 简要题解 观
https://codeforces.com/contest/2059/problem/C 题目大意 给出 n 个 n 长的数组 ai。进行如下操作 n 轮,在第 i 轮,选择某个 j,使得 aj,k=0 (k≤i)。即把某选择的行的开始一段小于 i 的元素刷成 0。 n 轮进行完之后设 bi=∑ai,j,则问可以任选
https://codeforces.com/contest/2059/problem/B 题目大意 给出 n 长的数组 a。给出偶数 k,要求将 a 分为连续的 k 个非空子段。将第偶数段(1-based)按照原来的顺序链接起来并在结尾追加一个 1。定义这个新数组 b 的分值为,最小的下标 i 使得