Atcoder abc301 复盘（更新中）

跳转比赛链接

A - Overall Winner

简述：
高桥和青木下了 \(N\) 盘棋。给你一个长度为 \(N\) 的字符串 \(S\)，表示这两盘棋的结果。如果 \(S\) 的 \(i\) 个字符是 t，那么高桥赢得了 \(i\) 局；如果 \(S\) 的 \(i\) 个字符是 A，那么青木赢得了这局。
高桥和青木之间的胜负关系是谁赢的局数多于谁。如果两人的胜局数相同，则先达到胜局数的一方为总冠军。找出总冠军：高桥或青木。

思路：不会有人红题不会吧？字符串处理，依次遍历即可。要注意胜负相等的情况。

AC 代码

B - Fill the Gaps

简述：
我们有一个长度为 \(N\) 的序列，由正整数 \(A=(A_1,\ldots,A_N)\) 组成。任何相邻的两个项都有不同的值。
让我们按以下步骤在这个数列中插入一些数字。

1. 如果 \(A\) 中每一对相邻项的绝对差值都是 \(1\)，则终止程序。
2. 假设 \(A_i, A_{i+1}\) 是最接近 \(A\) 开头的一对相邻项，其绝对差不是 \(1\)。
   - 如果是\(A_i < A_{i+1}\)，则在\(A_i\)和\(A_{i+1}\)之间插入\(A_i+1,A_i+2,\ldots,A_{i+1}-1\)。
   - 如果是\(A_i > A_{i+1}\)，则在\(A_i\)和\(A_{i+1}\)之间插入\(A_i-1,A_i-2,\ldots,A_{i+1}+1\)。
3. 返回步骤 1。

程序结束时打印序列。

思路：依次遍历处理，如遇绝对值差大于 \(1\)，循环插入即可。

AC 代码

C - AtCoder Cards

简述：

问题陈述

AtCoder 公司流行一种单人纸牌游戏。游戏中的每张牌上都写有一个小写英文字母或符号 @。每种牌都有很多张。游戏过程如下

1. 将相同数量的纸牌排成两行。
2. 将每张带@的牌换成以下其中一张牌：a、t、c、o、d、e、r。
3. 如果两排牌重合，您就赢了。否则，您输。

要赢得这个游戏，您需要进行以下作弊。

• 在步骤 1 之后，无论何时都可以自由地重新排列一行中的纸牌。
  给你两个字符串 \(S\) 和 \(T\)，分别代表步骤 1 之后的两行。判断在允许作弊的情况下是否有可能获胜。

思路：记录两个字符串中不同字符出现的数量（包括字符 @）。判断：如果字符不为 a、t、c、o、d、e、r 中的一个，失败；如果剩余 @ 不够来替换，失败。

AC 代码

D - Bitmask

简述：
给你一个整数 \(N\) 和一个由 0、1 和 ? 组成的字符串 \(S\)。假设 \(T\) 是将 \(S\) 中的每个 ? 替换为 0 或 1 并将结果解释为二进制整数后得到的值的集合。例如，如果 \(S=\) ?0?，则有 \(T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace\)。
打印 \(T\) 中小于或等于 \(N\) 的最大值（十进制整数）。如果 \(T\) 中没有小于或等于 \(N\) 的值，则打印 -1。

思路：由于 \(2^n > 2^{n-1}+...+2^1\)，所以肯定优先选择更高位的，之后依次向低位枚举即可。

AC 代码

E - Pac-Takahashi

简述：

问题陈述

我们有一个行数为 \(H\) 列数为 \(W\) 的网格。让 \((i,j)\) 表示从上往下第 \(i\) 行，从左往上第 \(j\) 列的方格。网格中的每个方格都是以下几种方格之一：起点方格、目标方格、空方格、墙壁方格和糖果方格。\((i,j)\) 用字符 \(A_{i,j}\) 表示，如果 \(A_{i,j}=\) S ，则 \((i,j)\) 为起始方格；如果 \(A_{i,j}=\)G，则\(A_{i,j}=\)为目标方格，\(A_{i,j}=\). 为空方格，\(A_{i,j}=\)# 时为墙方格，\(A_{i,j}=\)o 时为糖果方格。在这里，可以保证正好有一个起点方格、正好有一个目标方格和 最多 \(18\) 个糖果方格。
高桥现在位于起点方格。他可以重复移动到垂直或水平相邻的非墙方格。他希望最多移动 \(T\) 步到达目标方格。判断这是否可能。如果可能，找出他在到达目标方格的途中最多可以到达的糖果方格数，他必须在目标方格完成。每个糖果方格只计算一次，即使它被访问了多次。

思路：

AC 代码：