2025-01
https://codeforces.com/contest/888/problem/D 题目大意 问至多有 $k \ (1 \le k \le 4)$ 个位置不对的 $n \ (4 \le n \le 1000)$ 长的排列有多少。 简要题解 因为 $k$ 很小，所以我们直接把 $1 \sim 4$ 的错位排列全写出来，然后直接选位置就可以了。 复杂度 $T$：$O(n)$ $S$：$O(1
…
https://codeforces.com/contest/888/problem/C 题目大意 给一个小写字母的字符串 $S \ (|S| \le 10^5)$。定义 $k-Dominant$ 为对于某字符 $c$，所有 $len \ge k$ 长的子序列都含有至少一个 $c$。问对于串 $S$ 最小的 $k$ 是多少。 简要题解 因为每类字符是独立的，因此我们分开考虑即可。
…
https://codeforces.com/contest/888/problem/B 题目大意 给出机器人 $n \ (n \le 100)$ 长的操作序列。操作序列包含 UDLR 四种字母，分别表示其向四个方向移动一个单位，机器人可能只执行了部分指令，已知它在初始及结束都在 $(0, 0)$ 位置，问其最多执行了多少指令。 简要题解 这是一
…
https://codeforces.com/contest/808/problem/E 题目大意 给出 $n \ (n \le 10^5)$ 个物品和总容积为 $m \ (m \le 3 \times 10^5)$ 的背包。n 个物品的体积和价值分别为 $w_i \ (1 \le w_i \le 3)$ 和 $c_i \ (1 \le c_i \le 10^9)$。 问可以装入背包的（不超过 $m$ 的）最大价值。 简要题解 显然这是一个 $01$ 背包问题
…
https://codeforces.com/contest/808/problem/D 题目大意 给出 $n \ (n \le 10^5)$ 长的数组，其中元素 $1 \le a_i \le 10^9$ 问是否可以将其中某任意元素移动到其他任意位置，之后使得数组可以分成左右和相等的两部分。 简要题解 因为不增删数字，所以如果整个数组和为奇数无解。否则最后
…
https://codeforces.com/contest/1043/problem/D 题目大意 给出 $m \ (m \le 10)$ 个 $n \ (n \le 10^5)$ 长的排列，问在所有 $m$ 个数组中都出现的连续子数组有多少个。 简要题解 所有 $1$ 长的显然都符合条件。 对于 $2$ 及以上长度的，其必然在第一个数组中出现。对于 $2$ 长，显然我们只需关注所
…
https://codeforces.com/contest/2055/problem/d 题目大意 给出 $n \ (n \le 2 \times 10^5)$ 长的序列 $a_i$，给出 $k, l \ (1 \le k \le l)$。序列满足 $0 \le a_1 \le a_1 \le \cdots \le a_n \le l$。 起初 $x = 0$，当存在某 $x - k < a_i <= x$ 时，$x$ 会立即变换到 $a_i + k$。任意时刻，a_i 可以以每
…
https://codeforces.com/contest/2055/problem/C 题目大意 题目给出一个 $n \times m \ ( 2 \le n, m \le 1000 )$ 的矩阵，给出一条起点为 $(0, 0)$ 终点为 $(n - 1, m - 1)$ 的由向右向下走出的路径。这条路径由 $n + m - 2$ 个字母 $DR$ 构成的串组成。$D$ 表示向下，$R$ 表示向右。题目给出的矩
…
https://codeforces.com/contest/2055/problem/B 题目大意 给出 $n \ (n \le 2 \times 10^5)$ 长的两个数组 $a$ 和 $b$。$0 \le a_i, b_i \le 10^9$。 可以执行如下操作若干次： 将 $a_i$ 加 $1$，将除了 $a_i$ 以外的 $a$ 中元素减 $1$。 问是否可以对于所有的 $i$ 有 $a_i \ge b_i$。 简要题解 注意到，
…
https://leetcode.com/problems/count-non-decreasing-subarrays-after-k-operations/description/ 题目大意 给出 $n \ (n \le 10^5)$ 长的数组 $a$，其中 $1 \le a_i \le 10^9$，给出数字 $k \ (1 \le k \le 10^9)$。问有多少子数组，可以通过不超过 $k$ 次给单个位置 $+1$ 的操作，使得该子数组单调不减。 简要题解 容易发现，对于区间
…
https://codeforces.com/contest/1202/problem/B 题目大意 给出一个 $0 \sim 9$ 字符组成的序列 $S \ (1 \le |S| \le 2 \times 10^6)$ 且 $S$ 总以 $0$ 开始，这个序列是由 $x, y \ (0 \le x, y \le 9)$ 由以下规则生成出来的。 最初数字 $a$ 为 $0$。输出这个数 随机的从 $x, y$ 中选出一个数加到 $a$ 上并输出 $a$ 的个位
…
https://codeforces.com/contest/1202/problem/D 题目大意 构造一个包含 $1, 3, 7$ 的字符串 $S \ (|S| \le 10^5)$ 使得其中 $1337$ 子序列的个数为 $n \ (1 \le n \le 10^9)$ 个。 简要题解 观察： 如果 $n$ 更小，我们可以直接 $133$ 然后加上 $n$ 个 $7$。或者 $1$ 是同理的。 如果用 $111333777$ 这样的结构，那么结果是 $n_1 n7 C(n3,
…
https://codeforces.com/contest/1202/problem/C 题目大意 给出一个 $WSAD$ 操作序列 $S \ (|S| \le 2 \times 10^5)$，其中 $W$ 为 $x = x - 1$ $A$ 为 $y = y - 1$ $S$ 为 $x = x + 1$ $D$ 为 $y = y + 1$ 可以在任意位置加入最多一个字符，使得机器人运行这个序列而不移出边界所需的矩形框面积最小
…
https://codeforces.com/contest/1913/problem/C 题目大意 给出 $m \ (m \le 10^5)$ 次操作，每次操作为之下两种之一： 给出 $x \ (0 \le x \le 29)$ 将 $2 ^ x$ 加入可重集。 给出 $y \ (0 \le x \le 10^9)$，问是否可以选出一些可重集中的元素使其和为 $y$。 简要题解 因为 $x$ 很小所以数组 $cnt$
…
https://codeforces.com/contest/1913/problem/D 题目大意 给出一个 $n \ (1 \le n \le 3 \times 10^5)$ 排列 $p$。可以做如下操作任意次： 选出一个区间 $[l, r]$ 将其中除了最小元素以外的元素全部删掉。 问结果数组共有多少种。结果对 $998244353$ 取模。 简要题解 观察： 注意到 $1$ 永远删不掉。 考虑 $2$
…
https://codeforces.com/contest/1251/problem/A 题目大意 给出一个小写字母组成的字符串 $S \ (|S| \le 500)$。这是一个测试键盘的打字产生的序列，当一个字母对应的键是坏的时，会连续插入两个对应的字符。问从测试序列能推出那些字符确定是好的，字典序输出。 简要
…
https://codeforces.com/contest/1202/problem/A 题目大意 给出两个代表数字的二进制串 $A$ 和 $B$，没有前导零且 $|A|, |B| \le 10^5$。规定 $f(X)$ 为串 $X$ 对应的数字的值，有 $1 \le f(B) \le f(A)$。问取正整数 $k$，使得 $f(A) + f(B) \dot 2 ^ k$ 对应数字字符串的逆序字典序最小。问这
…
https://codeforces.com/contest/1251/problem/B 题目大意 给出 $n \ (\le 50)$ 个 $01$ 串，每个串 $s_i \ (|s_i| \le 50)$。可以任意交换任意两个串之间的一对字符，问最多能组成多少个回文串。 简要题解 我们最多可以得到 $n$ 个回文，我们尝试尽量达成这件事。 考虑所有串总长 $s = \sum s_i$ 的
…
https://codeforces.com/contest/1251/problem/C 题目大意 给出一个数字字符组成的字符串 $S \ (|S| \le 3 \times 10 ^ 5)$，允许任意次交换相邻的奇偶性不同的字符，问最后的得出的可以包含前导零的最小数字是多少。 简要题解 这题挺典，首先同种奇偶性的字符的相对关系是无法
…
https://codeforces.com/contest/1251/problem/D 题目大意 给出奇数 $n \ (< 2 \times 10^5)$ 个人的薪资范围，其中第 $i$ 个人的范围为 $[l_i, r_i] (1 \le l_i \le r_i \le 10^9)$，以及薪资和的上限 $\sum l_i \le s \le 2 \times 10^{14}$。问当所有人的薪资 $x_i$ 符合自己的范围，且和不超过 $s$ 时，中位数
…