比赛顺利结束，感谢大家的参与！

Three, Not Four

记按位异或运算为 $\oplus$，它有如下性质：

1. $a\oplus a=0$
2. $a\oplus 0=a$
3. 满足交换律和结合律

因此：

• 一个数如果出现了 $4$ 次，那么 $a\oplus a\oplus a\oplus a=0$；
• 一个数如果出现了 $3$ 次，那么 $a\oplus a\oplus a=a$。

题目中，除了一个数出现了 $3$ 次，其余所有数都出现了 $4$ 次。所以把所有输入的数全部异或起来即有：

• 所有出现 $4$ 次的数都会两两抵消，最终贡献为 $0$
• 只有那个出现 $3$ 次的数会留下来

则最终结果就是答案。

参考代码

#include <stdio.h>
int main(){
    int n,x=0,a;
    scanf("%d",&n);
    while(scanf("%d",&a)==1)x^=a;
    printf("%d",x);
}

Code Golf

x;main(n){for(scanf("%d",&n);~scanf("%d",&n);x^=n);printf("%d",x);}

数学高尔夫

记号约定

题面中的记号保持不变：

• $A$ 的第 $i$ 位为 $1$，表示坐标 $i$ 处有一个球；
• $B$ 的第 $i$ 位为 $1$，表示坐标 $i+0.5$ 处有一个洞。

所有运算都只看低 $50$ 位。记

我们希望构造一个掩码 $C$，使得 $C$ 的第 $i$ 位为 $1$ 当且仅当坐标为 $i+0.5$ 处的洞最终被覆盖。答案就是

核心结论：一个洞是否被覆盖，只取决于它左边到上一个洞之间是否出现过球。

设第 $i$ 位满足 $B_i=1$，也就是这里有一个洞。记它左边最近的另一个洞位置为 $p(i)$；若不存在，就令 $p(i)=-1$。

那么这个洞被覆盖，当且仅当区间

中至少出现过一个球。

原因很直接：

• 洞左边最近的那个洞会截断更早的球，所以更左边的球不可能穿过它；
• 只要 $(p(i),i]$ 中出现一个球，它向右遇到的第一个洞就是第 $i$ 个洞。

这个结论已经足够写出一个 $O(50)$ 的扫描做法，甚至可以写进 100 byte.

参考代码 by 邵帅

a, z;
main() {
    long i, j;
    for (scanf("%ld%ld", &i, &j); j; z |= i & 1, j & z && (++a, --z), i /= 2, j /= 2)
        ;
    printf("%d", a);
}

不过事实上还能再凹。

第一步：如果 A 和 B 在某一位同时是 1，那么这个洞肯定会被覆盖。

若某一位同时满足 $A_i=B_i=1$，那么坐标 $i$ 处的小球会立刻掉进坐标 $i+0.5$ 处的洞。

所以这一类洞的掩码就是

把它们先拿掉。剩余需要处理的球是

因为 $S$ 本来就是 $A$ 的子掩码，所以这一步只是把“球和洞同位”的那些 $1$ 清掉，没有借位问题；也就是说

这样一来，$R$ 在所有洞位上都一定是 $0$。

第二步：用一次加法把剩余覆盖洞全部找出来

考虑

在低 $50$ 位内，它恰好满足：

• 非洞位置是 $1$；
• 洞位置是 $0$。

因此，如果把若干个洞的位置从左到右写成

那么在每个区间 $\bigl(h_{t-1},h_t\bigr)$ 内（约定 $h_0=-1$），$T$ 的形状一定是

也就是“一长串 $1$，最后一个洞位是 $0$”。

现在把 $R$ 加到 $T$ 上。

为什么这会恰好标出被覆盖的洞

固定考察某个洞 $h_t$。

• 若区间 $(h_{t-1},h_t)$ 内没有球，那么 $R$ 在这段里全是 $0$，显然不会向 $h_t$ 产生进位，所以和的第 $h_t$ 位仍然是 $0$。
• 若区间 $(h_{t-1},h_t)$ 内至少有一个球，取其中最靠右的一个位置 $j$。由于 $j+1,j+2,\dots,h_t-1$ 都不是洞，所以 $T$ 在这些位置上全是 $1$。于是从第 $j$ 位加上的这一个 $1$ 会沿着这一整段连续的 $1$ 一路进位，最终把第 $h_t$ 位顶成 $1$。

更重要的是，不同洞之间互不干扰。因为每个洞位在 $T$ 里本来就是 $0$，进位一旦到达某个洞位，就会在这里停下，不会继续穿过这个洞再影响右边的下一段。

所以

恰好是这样一类洞的掩码：

第三步：合并公式

把前两部分合起来：

代入 $S=A\mathbin{\&}B$ 与 $R=A-(A\mathbin{\&}B)$，得到

于是答案可以写成

这就是题面记号下最直接的 code golf 版表达式。

参考代码（c）

原代码如下：

long a, b;
main() {
    scanf("%lld%lld", &b, &a);
    printf("%d", __builtin_popcountll(a & b | b + ~a - (a & b) & a));
}

注意它在读入时故意把变量名反过来了：

• 代码里的 a 实际对应题面中的 $B$；
• 代码里的 b 实际对应题面中的 $A$。

所以把它翻译回题面记号后，主体正是

这里的 ~B 指的是机器字长下的按位取反。由于题目只关心低 $50$ 位，而 $B<2^{50}$，所以低 $50$ 位上的 ~B 就等价于前面写的 $M-B$。C 版因此可以直接偷成一个更短的 ~B。

另外，原式子省掉了括号，但按运算符优先级它实际等价于

__builtin_popcountll((a & b) | ((b + ~a - (a & b)) & a))

参考代码（python）

原代码如下：

b,a=map(int,input().split());print(bin(a&b|(((1<<50)-1-a+b-(a&b))&a)).count('1'))

它做的事和 C 版完全一样，只是 Python 的整数不是固定宽度，直接写 ~B 会变成带无限前导 $1$ 的负数，不方便直接拿去和 bin() 配合。

所以 Python 版把 ~B 显式改写成了低 $50$ 位补码

翻译回题面记号，就是

print(bin((A&B)|((((1<<50)-1-B+A-(A&B))&B))).count('1'))

自然拼读法

题目给了 11 条字符串替换规则，要求我们严格按照编号顺序执行。第 $i+1$ 条规则看到的是前 $i$ 条规则处理后的结果，而不是原串。

如果按普通做法来写，这其实是一道直接模拟题：顺着规则做 11 次处理即可，数据范围也不大。

但是这道题的特殊之处在于需要 code golf。也就是说，我们关心的不只是“做对”，还关心“怎么写得更短”。

观察题目中的 11 条规则会发现，它们几乎都可以理解成同一件事：

这正好就是正则表达式最擅长做的事情。因此，codegolf 的方向应该是把 11 条规则翻译成 11 组左右的正则替换，再按顺序连起来执行。

为什么正则替换适合这道题

正则替换适合本题，主要有两个原因。

1. 题目本来就是“按顺序做替换”。

   无论是 Python 的 re.sub，还是 C++ 的 regex_replace，都很适合完成“把所有匹配到的地方替换成另一个串”这件事。

2. 题目中的很多条件，本来就是正则擅长表达的。

   例如：

   • 后面跟着 e/i/y；
   • 后面不是 h；
   • 后面跟着若干个和自己相同的字符。

   这些条件用普通字符串处理也能写，但用正则通常更短。

正则表达式基础速成

这一节不是完整的正则教程，只介绍本题真正会用到的几个语法。每个语法点我们都先看一个很小的例子，再看它如何服务于本题。

普通字符：写什么，就匹配什么

如果一个字符没有特殊含义，那它就表示“匹配它自己”。

例如：

• wh 能匹配字符串 wh；
• 把 wh 替换成 w，就会把 which 的开头从 wh 变成 w；
• wh 不能匹配 ch。

因此，像第 3 条规则 wh -> w、第 9 条规则 ch -> c 这种“纯字面替换”，几乎可以直接翻译成正则。

字符类：这一位可以是若干种字符之一

[eiy] 表示“这一位可以是 e、i、y 之一”。

例如：

• [eiy] 能匹配 e；
• [eiy] 能匹配 y；
• [eiy] 不能匹配 a。

所以，如果我们想表达“某个字符后面跟着 e/i/y 之一”，字符类就会很方便。

否定字符类：匹配不在集合里的字符

[^aeiou] 表示“匹配一个不是 a/e/i/o/u 的字符”。

例如：

• [^aeiou] 能匹配 b；
• [^aeiou] 能匹配 x；
• [^aeiou] 不能匹配 a。

这在第 8 条规则里很重要，因为题目把辅音定义成“不是元音的字母”。

分组与反向引用

圆括号 () 可以把一部分模式打包成一组。

例如，(ab) 会把 ab 当成第 1 组。

如果后面写 \1，意思就是“再来一遍第 1 组刚刚匹配到的内容”。

小例子：

• (ab)\1 能匹配 abab；
• (ab)\1 不能匹配 abac；
• 如果把它替换成 \1，那么 abab 就会变成 ab。

本题第 8 条规则要压缩“连续相同的辅音”，就会用到这个思想。

量词 +：前面的东西至少出现一次

+ 表示“前面的东西至少出现 1 次”。

例如：

• a+ 能匹配 a；
• a+ 能匹配 aaaa；
• a+ 不能匹配空串。

当它和 \1 组合时，就能表示“后面连续跟着若干个和前面一样的东西”。

前瞻：看后面，但不把后面的字符吃掉

(?=...) 叫做前瞻。它的作用是：

例如，c(?=e) 的意思是：

所以：

• c(?=e) 在 ce 中能匹配到那个 c；
• c(?=e) 在 ca 中匹配不到；
• 它真正匹配到的内容仍然只有 c，不是 ce。

这一点非常重要，因为题目第 1 条和第 4 条都要判断“后一个字符是什么”，但替换时只想改当前这个字母本身。

负前瞻：后面不能是某种模式

(?!...) 叫做负前瞻。它和前瞻相反，表示：

例如，c(?!h) 表示：

于是：

• c(?!h) 在 ca 中可以匹配到 c；
• c(?!h) 在 ch 中不能匹配到 c。

这正好对应题目第 1 条里“不属于 ch 的 c”。

按规则翻译成正则

下面我们把题目的 11 条规则一条条翻译成正则替换。无论是 Python 还是 C++，替换都是“全局进行”的：一条规则会把当前串里所有符合条件的位置都改掉，然后再进入下一条规则。

第 1 条：处理不属于 ch 的 c

题目要求：

• 如果这个 c 后面是 e/i/y，就变成 s；
• 否则变成 k；
• 但如果它属于 ch，就先不要动，因为 ch 要留到第 9 条规则再处理。

所以 best.py / best.cpp 把这件事拆成了两步：

c(?=[eiy]) -> s
c(?!h)     -> k

第一条先把后面跟着 e/i/y 的 c 变成 s。第二条再把剩下那些“不属于 ch 的 c”变成 k。

例如：

• ce 中的 c 会先被第一条变成 s；
• ca 中的 c 不满足第一条，但满足第二条，所以会变成 k；
• ch 中的 c 不满足第二条，所以会保留下来，等第 9 条再处理。

这里可以顺便比较一个更常规的匹配思路：先用 ch、c(?=[eiy])、c 这样的分类模式去覆盖三种情况，甚至把它们并成 ch|c(?=[eiy])|c 这样一个总模式，再在代码里判断这次到底匹配到了哪一类。

这样写当然也能做，而且思路很自然；但 code golf 更关心的是短。与其写一个更长的统一匹配，再额外分类，不如直接拆成两次简单替换，总代价反而更低。

第 2 条：x -> ks

这一条最直接：

x -> ks

没有条件，也不需要额外技巧。

第 3 条：wh -> w

同样是直接字面匹配：

wh -> w

第 4 条：g 在 e/i/y 前变成 j

这一条和第 1 条很像，对应：

g(?=[eiy]) -> j

意思是：如果某个 g 的后一个字符属于 e/i/y，就把这个 g 变成 j。

例如：

• ge 中的 g 会变成 j；
• ga 中的 g 不会被这一条影响。

第 5 条：y -> i

y -> i

第 6 条：ee -> i

ee -> i

第 7 条：oo -> u

oo -> u

第 8 条：连续相同的辅音只保留一个

这是全文最值得仔细看的一个正则。

Python 版本写的是：

([^aeiou])\1+ -> \1

先解释左边：

• [^aeiou] 表示“不是元音 a/e/i/o/u 的一个字符”；
• 外层括号把它记成第 1 组；
• \1+ 表示后面还跟着至少一个“和第 1 组完全相同的字符”。

所以整个模式的意思就是：

替换成 \1 后，就只保留第一个。

例如：

• ll 会变成 l；
• ssss 会变成 s；
• book 中的 oo 不会受它影响，因为 o 是元音。

这里可以比较一个更“正常”的正则写法：如果不追求极短，很多人会直接把辅音列出来，写成类似 ([bcdfghjklmnpqrstvwxyz])\1+ 的形式。这样更直观，但字符数明显更长。对 code golf 来说，直接写“不是元音”通常更省，所以 [^aeiou] 更有优势。

再来看空格问题。题目要求规则不能跨空格生效，Python 版本却没有显式排除空格，这会不会出问题？

答案是：不会。

因为 \1+ 要求后面紧跟着若干个与前面完全相同的字符。若前面匹配到的是空格，那么后面必须还是空格，才会形成一次完整匹配。但题目保证输入中没有连续两个空格，而且所有替换规则也不会产生新的空格，所以 Python 版虽然没有把空格写进排除列表，依然是安全的。

C++ 版本写成：

([^aeiou ])\\1+ -> $1

它选择把空格显式排除掉，写得更稳妥一点。与此同时，Python 版省掉了这个空格字符，正好也体现了 code golf 思路：能依赖题面保证省字符，就尽量省。

这里还要注意两种语言的写法差异：

• 在 Python 正则里，反向引用写成 \1；
• 在 C++ 源码字符串里，要把一个反斜杠写成两个反斜杠，所以源码里看到的是 \\1；
• C++ 的替换串写成 $1，这只是标准库接口的格式要求。

第 9 条：ch -> c

ch -> c

这也是为什么第 1 条不能太早处理 ch 中的 c。

第 10 条：sh -> y

sh -> y

第 11 条：th -> x

th -> x

为什么必须按这个顺序执行

这道题不能把 11 条规则打乱。

例如，which 里开头的 wh 必须先在第 3 条被替换成 w，后面的 ch 再在第 9 条被替换成 c。如果顺序错了，结果就会不同。

再比如 cheese：开头的 ch 在第 1 条不能被误处理，要先保留到第 9 条；而中间的 ee 又要在第 6 条先变成 i。顺序一旦改变，最后就不一定得到样例里的 cise。

所以，无论是 Python 还是 C++，本质上都是在做同一件事：按顺序执行一串正则替换。

参考代码（py）

先看代码：

import re
s=input()
for p in r'c(?=[eiy]) s;c(?!h) k;x ks;wh w;g(?=[eiy]) j;y i;ee i;oo u;([^aeiou])\1+ \1;ch c;sh y;th x'.split(';'):s=re.sub(*p.split(),s)
print(s)

它的核心思想很简单：把“模式 替换串”这两样东西按顺序塞进一个大字符串里，再用分号切开，最后循环调用 re.sub。

例如：

c(?=[eiy]) s

表示模式是 c(?=[eiy])，替换串是 s。

对整个大字符串做 split(';') 之后，就会得到 12 段；每一段再做 split()，就得到给 re.sub 用的两个参数。这里之所以是 12 段，是因为题目的第 1 条规则被拆成了两次替换。

如果不考虑 code golf，更常规的写法通常会是：

rules = [
    (r'c(?=[eiy])', 's'),
    (r'c(?!h)', 'k'),
    ...
]

这种写法更清楚，但括号、逗号、引号、列表名都会额外占字符。在 code golf 场景下，把所有规则压成一个大字符串显然更短。

另外，re.sub(pattern, repl, s) 会把当前字符串里所有匹配 pattern 的位置都替换掉，然后返回新字符串。循环不断覆盖 s，就实现了“按顺序依次执行所有规则”。

参考代码（c++）

再看 C++ 版本：

#include <bits/stdc++.h>
using namespace std;
int i;
int main() {
    string s, a[] = { "c(?=[eiy])",      "s",  "c(?!h)", "k", "x",  "ks", "wh", "w",
                      "g(?=[eiy])",      "j",  "y",      "i", "ee", "i",  "oo", "u",
                      "([^aeiou ])\\1+", "$1", "ch",     "c", "sh", "y",  "th", "x" };
    getline(cin, s);
    for (; i < 24; i += 2) s = regex_replace(s, regex(a[i]), a[i + 1]);
    cout << s;
}

它和 Python 版本本质相同，只是实现方式不同：

• 用数组 a[] 交替存放“模式、替换串、模式、替换串”；
• 循环里每次拿 a[i] 和 a[i+1] 配成一组；
• 用 regex_replace 顺序执行 12 次替换。

这里有两个细节值得注意。

1. C++ 版在第 8 条里写了 ([^aeiou ])\\1+。

   其中 \\1 只是字符串转义后的写法，真正交给正则引擎后，含义仍然是反向引用 \1。

2. C++ 的替换串写成 $1，而 Python 版本写成 \1。

   这是两个语言库的接口差异，不影响本题的核心思想。

如果不考虑 code golf，更常规的 C++ 写法也许会是：

vector<pair<string,string>> rules = {
    {"c(?=[eiy])", "s"},
    {"c(?!h)", "k"},
    ...
};

这显然更易读，但也更长。最优解选择数组加步长为 2 的循环，目的还是同一个：省字符。

元音消失术

朴素做法

1. 预先存下这 10 条原句
2. 对每条原句做一次同样的变换：把所有元音都替换成 e
3. 将变换后的结果与输入比较
4. 找到匹配的那条，输出原句

由于候选句只有 10 条，这样做已经足够通过。

Code Golf

注意到长度浪费主要在于我们存储了原句。但信息大部分本来就存储在输入的字符串变量中，故考虑编码“输入相比原句改变了什么”。

假设我要修复某条 quote，有一个指针 $p$ 指向字符串的开头。那么操作就有移动指针，以及将指针指向的位置修改为某个字符。故将操作编码为一个字符串：

由于给定的 quotes 满足相邻两个元音距离不会 $>15$，故 std 这样实现编码器:

• 每个字符包含两布操作，移动和修改。
• 利用 char 的低四位存储指针移动偏移量 $d$，其中 $d\in [0,15]$
• 利用 char 的高四位存储“修改为 aiou 的哪一种”。

此外，为了让输入的 quote 能够找到对应的操作序列编码，std 采用前四个字母视作一个 int 之后 $/ 9\bmod 16$ 的方法来映射到一个 $[0,15]$ 内的数（需满足是单射）。

以下是一份 encoder 的实现。

注：如果出现相邻元音距离 $>15$ 的情况，一种可能的实现为 19 至 22 行，输出字符 0x6f 表示只移位 15 位，不作修改。二进制下为 0110 1111 比正常的操作最大值 0011 1111 还要大，此时解码器中多加一层判断是否只移位即可。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int i, l, p, q, d, v, j;
  char s[4096], *x;
  const char *t = "aiou";

  if(argc < 1) return 1;

  while(fgets(s, sizeof(s), stdin)) {
    l = strlen(s);
    putchar('\"');
    for(i = 0, p = 0; i < l; i++) {
      if((x = strchr(t, s[i]))) {
        q = p;
        p = i;
        for(d = p - q; d > 15; d -= 15) {
          fprintf(stderr, "delta >15, adding padding\n");
          putchar(0x6f);
        }
        v = x - t + 2;
        j = (v << 4) | d;
        fprintf(stderr, "found '%c' at pos %d, delta %d = %X ('%c')\n", s[i], i, d, (int)j, j);
        if(strchr("\\\"", j))
          printf("\\%c", j);
        else
          putchar(j);
      }
    }
    puts("\"");
  }

  return 0;
}

以下是解码器（提交的代码）代码格式化后的实现，在进行删除空格等操作后可以做到 376B 长度。

*a[] = { "0%#%G3$ST'",
         "AB%G4$BQ82&E$F3FT$HT\"T4(%DHC",
         0,
         0,
         "AQ#6A3D%2IWD5$GQDQ\"B'",
         "0DQH1ECE\"D\"#C&DQBG#C$DDQ%)DQE+D#&DQ6",
         "EC\"%DQ#5E2#S!F#33A%",
         "\"3*[\"$#.E5U6C\"S'['#.E5U6C\"S\"",
         0,
         "0CG+Q4EDE65ED$S!E3\"F#$BQ",
         0,
         0,
         0,
         "5DQ&D3$ED",
         "0$+4EE3&D3&2$E#6KE$+E3",
         "AAFQ4\"%&EIQ\"&&F" };
p;
char s[9];
main(char* t) {
    gets(s);
    for (t = a[*(int*)s / 9 % 16]; p += *t & 15, *t; t++) s[p] = "aiou"[*t / 16 - 2];
    puts(s);
}

方块堆放

这是一份可能的实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> a(n, vector<int>(m));
    int H = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            H = max(H, a[i][j]);
        }
    }
    if (H == 0) {
        return 0;
    }
    const vector<string> cube = {
        "..+-+",
        "./ /|",
        "+-+ +",
        "| |/.",
        "+-+.."
    };
    const int height = 2 * (H + n - 1) + 3;
    const int width  = 2 * (m + n - 1) + 3;
    vector<string> canvas(height, string(width, '.'));
    for (int i = 0; i < n; ++i) {               // back -> front
        for (int j = 0; j < m; ++j) {           // left -> right
            for (int k = 1; k <= a[i][j]; ++k) { // bottom -> top
                int row = 2 * (H - k + i);
                int col = 2 * (j + (n - 1 - i));
                for (int r = 0; r < 5; ++r) {
                    for (int c = 0; c < 5; ++c) {
                        char ch = cube[r][c];
                        if (ch != '.') {
                            canvas[row + r][col + c] = ch;
                        }
                    }
                }
            }
        }
    }
    for (string &line : canvas) {
        for (char &ch : line) {
            if (ch == '.') ch = ' ';
        }
        while (!line.empty() && line.back() == ' ') {
            line.pop_back();
        }
    }
    while (!canvas.empty() && canvas.back().empty()) {
        canvas.pop_back();
    }
    for (int i = 0; i < (int)canvas.size(); ++i) {
        cout << canvas[i] << '\n';
    }
    return 0;
}