【比赛记录】ABC358

· · 个人记录

记录

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。