A - Continuous 1

给定一个长度为 $n$ 的只包含0,1,?的字符串，是否只存在一种替换?的方案使得字符串仅有 $k$ 个1且所有的 1 在某一个区间 $[l,l+k-1]$内。

• 解法：

滑动窗口，判断该区间是否可为 $k$ 个 1，且其他位置都是 0。

code

B - Make Divisible

给定正整数 $A,B$，求最小的 $X+Y$ 使得 $X,Y \geq 0,(B+Y)=k(A+X),k \geq 1$。

• 解法：

可以得到式子：$Y=kA+kX-B$。

上式可转化成 $X+Y=kA+(k+1)X-B$。

容易发现当 $k$ 确定时，当$X$ 最小时，$X+Y$ 最小。

通过 $X,Y \geq 0$ 得到：$X_{min}=\max(0,\lfloor\frac{B-1}{k}\rfloor+1-A)$。

于是 $X+Y=kA+(k+1)\times \max(0,\lfloor\frac{B-1}{k}\rfloor+1-A)-B$。

这里枚举 $\lfloor\frac{B-1}{k}\rfloor$ 的值，可以除法分块，设 $w=\lfloor\frac{B-1}{k}\rfloor$，那么当 $w$ 固定时，$k$ 最小则 $X+Y$ 最小。

复杂度 $O(\sqrt B)$。

code

C - Path and Subsequence

给定 $n$ 个点，$m$ 个边的连通无向图（无自环重边,$u_i<v_i$）以及长度为 $n$ 的数组 $A$ ,长度为 $k$ 的数组 $B$ ，是否满足对于所有简单路径 $v=(v_1,v_2,...,v_p)(v_1=1,v_p=n)$，$B$ 是 $[A_{v_1},A_{v_2},...,A_{v_p}]$的子序列。

• 解法：

设 $f_i$ 为所有从 $1$ 到 $i$ 的简单路径能扩展到的 $B$ 的最小值，即$[B_1,...,B_{f_i}]$满足子序列关系。满足题目关系当且仅当 $f_n=k$。

那么对于所有边 $(u,v),v=i$：$f_v=\min(f_u+[B_{f_u+1}=A_v])$，特别的，当$f_u=k$，$f_v=\min(f_v,k)$。

基于 Dijkstra 的贪心思路，可以用堆优化做到 $O(nlogn)$ 的 $f$ 求解。

code

待更