杂题

https://codeforces.com/contest/2066/problem/A 题目大意 给出 $n$ 长的数组 $x$ 和某个隐藏的确定的数组 $y$。保证 $x_i \neq y_i, \forall i$ 且 $(x_i, y_i) \neq (x_j, y_j), \forall i \neq j$ 。对于每组数据，背后有一个隐藏的对象是以下两种之一： Obj A: 一个 $n$ 个点的有向图当且仅当存在有向边 $(x_i, y_i)$ Obj B: $n$ 个点在二 …

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

https://codeforces.com/contest/1156/problem/A 题目大意 给出 $n$ 个图形的序列 $a$。图形依次向里内接。 1 代表圆形 2 代表底和高相等的等腰三角形，并且底平行于 $x$ 轴，高位于底的 $y$ 轴正方向 3 代表正方形，四边平行于坐标轴 保证序列里相邻图形不会相同，问图形间的 …

https://codeforces.com/contest/1902/problem/D 题目大意 给出某 LRUD 组成的 $n \ (\le 2 \times 10^5)$ 的操作序列 $S$ 以及 $q \ (\le 2 \times 10^5)$ 个询问。询问之间彼此独立。每次问，将原始操作序列 $[l, r]$ 的这一段反转后，整个操作序列以 $(0, 0)$ 为起点会不会通过 $(x, y)$。（$S$ 翻转 $[l, r]$ 之后的序 …

https://codeforces.com/contest/2061/problem/B 题目大意 给出 $n \ (4 \le n \le 2 \times 10^5)$ 条边（$1 \le a_i \le 10^8$）。问是否存在一种选法可以选出四条边，组成一个等腰梯形。正方形或长方形也可以，但不能退化。 简要题解 可以想象，大概就是要枚举一些东西。 法1 赛时写 …

https://codeforces.com/contest/2060/problem/B 题目大意 给出 $n$ 个长为 $m$ 的数组，这些数组中的元素为 $[0, nm - 1]$，每个各出现一次。 问是否存在 $n$ 长的排列 $p$ 使得，依次从 $p_1, p_2, p_3 …$ 数组中取出比刚才大的数，重复直到任一数组无法取出元素。使得最终取出的序列为 $[0, nm …

https://codeforces.com/contest/1922/problem/A 题目大意 给出三个小写字母串 $a, b, c \ (1 \le |a| = |b| = |c| \le 20)$。问是否存在某模式串 $p$ 是 $a, b$ 的匹配但不是 $c$ 的匹配。当一个串的所有位置都是匹配时是匹配，否则不是匹配。匹配规则为如果 $p[i]$ 为小写字母则 $p[i] = t[i]$ 为匹配 …

https://codeforces.com/contest/2056/problem/B 题目大意 给出一个 $n (n \le 1000)$ 长的未知排列和已知的 $n$ 个点的图，如果在排列中 $1 \le i < j \le n$ 且 $p_i < p_j$，则图上有一条 $<p_i, p_j>$ 的无向边。邻接矩阵的形式给出图，问排列是什么。 简要题解 直接看 $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/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/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://codeforces.com/contest/911/problem/B 题目大意 给出 $n, a, b \ (1 \le a, b \le 100, 2 \le n \le a + b)$。 要把 $a$ 块某种蛋糕和 $b$ 块另一种蛋糕分给 $n$ 个人。所有蛋糕必须都分出，而每个人只能收到某一种蛋糕，问收到最少块数的最大值是多少。 简要题解 因为 $a, b$ 都很小， …