CF613E Puzzle Lover 题解
Description 给定一个 2×n2 \times n2×n 的矩阵，每个位置上有一个小写字母。 有一个长度为 kkk 的小写字符串 www，询问矩阵中有多少条有向路径满足以下条件： 路径上的字母连起来恰好为 www。 不多次经过同一个位置。 只能向上下左右四个方向走。 n,k≤2×103n,k \le 2 \times 10^3n,k≤2×103，答案对 109+710^9+7109
CF605E Intergalaxy Trips 题解
Description nnn 个点的有向完全图。 i→ji \to ji→j 的边每天出现的概率均为 pi,jp_{i,j}pi,j，若 i=ji = ji=j，有 pi,j=1p_{i,j} = 1pi,j=1。 每天可以选择一条存在的出边走过去或停留在原地不动。 求最优策略下从 111 到 nnn 的期望天数。 n≤103n \le 10^3n≤103。 Solution 设 f
CF585F Digits of Number Pi 题解
Description 给定长度为 nnn 的数字串 sss 和长度为 ddd 的不含前导零的数字串 x,y(x≤y)x,y(x \le y)x,y(x≤y)。 求存在长度至少为 ⌊d2⌋\left\lfloor\frac{d}{2}\right\rfloor⌊2d⌋ 的子串是 sss 的子串的数字串 t∈[x,y]t \in [x,y]t∈[x,y] 的数量。 n≤103n \le 10^3
CF578E Walking! 题解
Description 给定一个长度为 nnn 的只包含 L,R 的字符串 sss。 构造一个 nnn 排列 ppp 满足 s[pi]≠s[pi+1](1≤i<n)s[p_i] \ne s[p_{i+1}](1 \le i < n)s[pi]=s[pi+1](1≤i<n)。 最小化 ppp 中 pi>pi+1(1≤i<n)p_i > p_{i+1}(1
CF576D Flights for Regular Customers 题解
Description 给定一张 nnn 个点 mmm 条边的有向图。 一开始你在 111 号节点，你要走到 nnn 号节点去。 只有当你已经走过了至少 did_idi 条边时，你才能走第 iii 条边。 问最少要走多少条边，或判断无法到达。 n,m≤150n,m \le 150n,m≤150，di≤109d_i \le 10^9di≤109。 Solution 注意到如果直接跑最短路
CF568C New Language 题解
Description 将 a∼a+l−1\texttt{a} \sim \texttt{a} + l - 1a∼a+l−1 这 lll 个字符分成 V,C\texttt{V,C}V,C 两个集合。 你需要构造一个长度为 nnn 且满足 mmm 个限制且不小于另一个长度为 nnn 的字符串 sss 的最小字符串。 每一个限制为若字符串的第 p1p_1p1 个位置上的字符 ∈t1\in t_1
CF559E Gerald and Path 题解
Description 有 nnn 条线段。 每条线段给定其中一端的位置及长度。 求所有线段覆盖的最大长度。 n≤100n \le 100n≤100。 Solution 考虑 dp。 先按照一端的位置进行排序，设 fi,j,0/1f_{i,j,0/1}fi,j,0/1 表示前 iii 个线段，右端点最靠右的线段是 jjj 向左/右覆盖，所有线段的最大长度。 直接枚举 i+1i+1i+1
CF547D Mike and Fish 题解
Description 给定 nnn 个整点。 你要给每个点染成红色或蓝色。 要求同一水平线或垂直线上两种颜色的数量最多相差 111。 n,xi,yi≤2×105n,x_i, y_i \le 2 \times 10^5n,xi,yi≤2×105。 Solution 考虑给每条水平线和垂直线建一个点，对于每个整点就把它对应的两条线连一条边。 题目就转化为了给每条边定向，使得每个点入度和出