本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-16 21:21:42

记录

A-E 速切，F 模拟了近一个小时遗憾缺了一点点，然后发现 G 过的人特别多，去写 G，到结束写的都是假做法。

题解

A - Welcome to AtCoder Land

string 判断即可，略过不表。

B - Ticket Counter

模拟，略过不表。

C - Popcorn

把每个摊位拥有的爆米花种类状压成一个二进制数，然后对 $n$ 个摊位枚举 $2^n$ 种选择，把所有选上的摊位的种类串或起来，如果等于 $2^m-1$ 就是合法的，取 popcount 最小的 $i$ 即可，时间复杂度 $O(2^n\times n)$

D - Souvenirs

先把 $A,B$ 分别升序排序，之后依次处理每个 $B_i$，用指针在 $A$ 上扫，每次找到第一个 $A_k\ge B_i$ 的 $A_k$ 分给 $B_i$ 即可。由于 $A,B$ 都不降，这样一定是最优的。

E - Alphabet Tiles

组合计数 dp。由于最终的串数要求本质不同，所以考虑把 $26$ 个不同字母依次插入串中，设 $f_{i,j}$ 为考虑前 $i$ 个字母时，长度为 $j$ 且本质不同的字符串数，有 $f_{0,0}=1$。

考虑转移，枚举 $k$ 为第 $i$ 个字母出现的次数即可，需要在 $j$ 个位置中选出 $k$ 个放 $i$，其余按顺序放入长度为 $j-k$ 的串，因此有 $f_{i,j}=\sum_{k=0}^{\min(j,C_i)}f_{i-1,j-k}\times \binom{j}{k}$，填表法即可，时间复杂度 $O(26k^2)$

F - Easiest Maze

很显然最短路径长度为 $n$，直接走下来即可。考虑在这条路上拓展，发现每次只能拓展 $2$ 格，因此 $k-n$ 必须为偶数才可能有解。拓展方法为每两行为一组同时向左扩展若干格，最后若多出一行（即 $n$ 为奇数时）可以从 $n-1$ 行向下两格两格扩展，所以最多扩展 $2\lfloor\frac{n(m-1)}{2}\rfloor$ 格，判断无解后模拟填写即可。

G - AtCoder Tour

发现最终的最优方案一定为走到某一格 $(x,y)$ 后一直停在这格直到结束，所以设 $f_{i,j,k}$ 表示走 $k$ 步到达 $(i,j)$ 的最大权值和，用 $f_{i,j,k}+A_{i,j}\times (K-k)$ 更新答案。由于走一个环一定不优于在环上某一点停留，所以 $k$ 取到 $HW$ 时一定已经包含最优解。时间复杂度 $H^2W^2$。