题解：P14518 [NFLSPC #8] APLSPC

· · 题解

这大概是我在洛谷上见到的最魔怔的题了。

题目要求你设计一份程序，使其能同时在 C++ 和 Python 的语言环境下正常运行，并且都能输出自己的源代码，并且代码中还不能包含这两个语言中的关键字，源代码长度不超过 250B。

双语代码

首先，我们得考虑什么样的代码可以同时在 C++ 和 Python 下运行，由于 C++ 和 Python 代码风格相差很大，所以我们必须使用注释。

在 C++ 中，除了常规的两种注释（// 和 /**/）外，我们还可以利用预处理器来实现注释功能，例如 #if false 和 #endif 中的部分会被 C++ 忽略。

幸运的是，在 Python 中，注释恰好是由 # 开头的，也就是说，C++ 中的预处理器会被 Python 直接忽略，这就给我们的实现带来了可能。

具体方法如下：

先把两对用 #if false 和 #endif 包裹的 '''（Python 中的多行注释）放在代码前后，这样中间的地方就可以写 C++ 代码，''' 和 #if 中间的部分就可以写 Python 代码了。

A+B Problem 的代码（话说我应该用什么语言的代码框）：

#if false
print(sum(map(int,input().split())))
"""
#endif
#include<bits/stdc++.h>
using namespace std;
int main() {
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}
#if false
"""
# 这里也可以写 Python 代码
#endif

Quine

接下来我们考虑如何让代码输出自己，在 C++ 中，我们可以利用 printf 来完成这一点。

首先，假设我们已经写出了这样的代码（其中 __builtin_printf 可以理解为 printf 的无头文件版本。注意：ISO C++ 禁止将字符串常量转换为 char*，因为字符串常量在 C++ 中是 const char* 类型，但这里我们为了缩短代码长度暂且采用这种写法）：

char*s="";main(){__builtin_printf(s);}

接下来，我们要把整个代码放入双引号中：

char*s="char*s="";main(){__builtin_printf(s);}";main(){__builtin_printf(s);}

我们发现代码中又出现了需要填充代码的双引号，这看起来是一个无限循环，但是其实 s 中就存储了代码，所以用 %s 代替 s 输出即可，另外 " 为特殊字符，需要用 %c 来输出。

稍加整理后，我们得到了能够输出自己的代码（其中 34 为 " 的 ASCII 码）：

char*s="char*s=%c%s%c;main(){__builtin_printf(s,34,s,34);}";main(){__builtin_printf(s,34,s,34);}

同理，我们也可以写出能输出自己的 Python 代码（在格式化字符串中需要使用 %% 表示 %）：

s="s=%c%s%c;print(s%%(34,s,34))";print(s%(34,s,34))

最初的尝试

再回来看这道题，由于不能使用关键字，所以我们把 char* 定义变量换成宏定义，把 #if false 换成 #ifdef a。由于这道题不忽略文件末回车，所以要在 Python 中的 print 函数中传入一个 end=''。

利用之前的方法把 C++ 和 Python 结合起来就得到了这份代码（赛时写的，646B，但是会被 hydro 的神秘 SPJ 计成 664B，57 分）：

#ifdef a
'''
#endif
#define S "#ifdef a%c'%c'%c#endif%c#define S %c%s%c%cmain(){__builtin_printf(S,10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10);}%c#ifdef a%c'%c'%cS=%c%s%c%cprint(S%%(10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10),end='')%c#endif"
main(){__builtin_printf(S,10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10);}
#ifdef a
'''
S="#ifdef a%c'%c'%c#endif%c#define S %c%s%c%cmain(){__builtin_printf(S,10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10);}%c#ifdef a%c'%c'%cS=%c%s%c%cprint(S%%(10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10),end='')%c#endif"
print(S%(10,39,10,10,34,S,34,10,10,10,39,10,34,S,34,10,10),end='')
#endif

注意 Python 中三引号的匹配优先级较高，所以字符串内的三引号要用 %c 代替一个。

小优化

我们发现我们的代码中有两个重复的字符串，我们考虑如何优化它，我们在 C++ 中不使用宏定义，而是定义一个 char* 类型的变量。不过这样会出现一个关键字，使用 #define C ch##ar，然后用 C 来代替 char 即可。

代码如下（601B，58 分）：

#ifdef a
'''
#endif
#define C ch##ar
C*
#ifdef a
'''
#endif
S="#ifdef a%c'%c'%c#endif%c#define C ch##ar%cC*%c#ifdef a%c'%c'%c#endif%cS=%c%s%c;%c#ifdef a%c'%c'%c#endif%cmain(){__builtin_printf(S,10,39,10,10,10,10,10,39,10,10,34,S,34,10,10,39,10,10,10,10,39,10,10);}%c#ifdef a%c'%c'%cprint(S%%(10,39,10,10,10,10,10,39,10,10,34,S,34,10,10,39,10,10,10,10,39,10,10),end='')%c#endif";
#ifdef a
'''
#endif
main(){__builtin_printf(S,10,39,10,10,10,10,10,39,10,10,34,S,34,10,10,39,10,10,10,10,39,10,10);}
#ifdef a
'''
print(S%(10,39,10,10,10,10,10,39,10,10,34,S,34,10,10,39,10,10,10,10,39,10,10),end='')
#endif

注意要开辟两片放 C++ 代码的地方，因为给字符串赋值的代码要能同时在两种语言下运行。

新的思路

我们发现这段代码几乎没有什么压缩空间了，但我们离目标还差得远，我们考虑换一种思路。

我们发现 C++ 中的注释 // 在 Python 下是整除符号，这样我们可以把 Python 代码藏在一行的最后，而不是用冗长的预处理器套三引号解决。再配合上宏定义，我们可以得到下面的代码（以 A+B Problem 为例）：

#define A main(){int a,b;__builtin_scanf("%d%d",&a,&b);__builtin_printf("%d",a+b);a
A=1//1;print(sum(map(int,input().split())))
#define A ;}
A

这份代码在 C++ 眼里是这样的：

main(){int a,b;__builtin_scanf("%d%d",&a,&b);__builtin_printf("%d",a+b);a=1;}

只是多了一个给变量赋值的无用操作，而在 Python 眼里是这样的：

A=1//1;print(sum(map(int,input().split())))
A

把一个变量赋值后又提到了它一下，这没有任何影响。

我们用这样一个巧妙的方式来大幅缩短了代码长度，我们离成功又近了一步。

我们结合之前写 Quine 的思路，最终得到一个 252B 的代码（会被 hydro 算成 258B，98 分，这里 Python 中的字符串名叫 A）：

#define A main(){ch##ar*S
A="#define A main(){ch##ar*S%cA=%c%s%c;1//1;print(A%%(10,34,A,34,10,10),end='')%c#define A ;__builtin_printf(S,10,34,S,34,10,10);}%cA";1//1;print(A%(10,34,A,34,10,10),end='')
#define A ;__builtin_printf(S,10,34,S,34,10,10);}
A

现在就差一点了，我们把 print 要输出的字符串放到 end= 后面，这样可以在不输出换行的情况下节省一些字符，更进一步，我们可以去掉第二个 #define A 后面的空格，这样代码长度就只有 244B 了，刚好可以在 hydro 的神秘 SPJ 下通过：

#define A main(){ch##ar*S
A="#define A main(){ch##ar*S%cA=%c%s%c;1//1;print(end=A%%(10,34,A,34,10,10))%c#define A;__builtin_printf(S,10,34,S,34,10,10);}%cA";1//1;print(end=A%(10,34,A,34,10,10))
#define A;__builtin_printf(S,10,34,S,34,10,10);}
A

后记

终于，这道题在我们的努力下成功被解决了，这道题虽然不是一道传统题，但是我觉得这道题仍然非常有价值。从预处理器与三引号的笨重结合，到用 // 对代码的极致压缩，每一步都是思维与代码的激烈碰撞。# 和 // 好像一座桥梁，将两种语言的程序连接起来。当你发现注释不再只是注释，字符串甚至可以包含自己，一份代码可以在两种语言下运行，或许会想起这个道理：能限制我们的只有想象力。