Constructor Open Cup 2026 (Practice Round)

https://constructor2026.contest.codeforces.com/group/XdjJUfzFUt/contest/668785

A ~ D

模拟即可。

E

切第 $i$ 刀时，会多出 $\lfloor\frac{i}{2}\rfloor+1$ 块巧克力。答案即为 $\sum\limits_{i=0}^k \lfloor\frac{i}{2}\rfloor+1=(\lfloor\frac{k}{2}\rfloor+1)^2+(\lfloor\frac{k}{2}\rfloor+1)[k\mod 2]$。

F

dp。设 $f_{i,j}$ 为确定到十进制第 $i$ 位（从 $0$ 开始），$\mod 2^n$ 目前为 $j$ 时第 $i$ 位的取值。可以从 $f_{i,(j-2\times 10^{i})\mod 2^n}$ 和 $f_{i,(j-10^{i})\mod 2^n}$ 转移过来。最后输出方案即可。

G

容斥算出贡献为 $1,2,3,5$ 的数的个数即可。

H

一个 * 可以扩展到一个 . 当且仅当它们的距离 $\leq k$。用栈维护每个 . 左右最近的 *。

I

题意即任意选择一个长度为 $m$ 的区间，最多能与多少个给定区间的交非空。将给定的区间按左端点升序排序，枚举选择的区间的右端点，优先队列 + 双指针维护即可。

J

最大值最小，考虑二分答案。答案确定时，贪心 check 即可。

K

建有向图，如果点亮 $i$ 能被 $j$ 看到就连边 $i\rightarrow j$。缩点，每个强连通分量里只要有一个点被点亮，剩下的点都会被点亮。拓扑序在第一层的强连通分量无法被其他强连通分量里的点点亮。令第 $i$ 个强连通分量的大小为 $s_i$，入度为 $d_i$，答案即为 $\prod (2^{s_i}-[d_i=0])$。

L

确定 $x$ 在广义 fib 序列中的下标和 $x$ 之前一项的值（记作 $y$）后，就可以确定一个独一无二的广义 fib 序列。$x\leq 10^9$，$x$ 所在的下标是 $\mathcal{O}(\log x)$ 级别。枚举下标并求出每一项用 $k_0x+k_1y$ 表示的系数 $k_0,k_1$。在每一项都大于 $0$ 的限制下，合法的 $y$ 构成一个区间。每次将答案加上区间长度，当区间大小 $<1$ 时退出即可。