论如何在键盘的大部分标点符号都坏掉的情况下实现排序
Cybher
·
·
休闲·娱乐
（这篇文章主要展示一些我在研究关于扣标点符号问题的一些想法，所以行文可能比较意识流，主要还是介绍一些思考过程中的小想法。另外注下划线在这篇文章不被归于标点符号，因为姑且对这个符号的定义是不能作为变量名称中的非空白字符）
起因
和机房同学闲聊的时候聊到了个奇怪的问题，就是关于排序这道题，如果把 [ 这个符号 ban 掉，该怎么写。然后我发现似乎还能使用 vector。于是我又 ban 掉了 <，他又想到了可以指针，于是我又 ban 掉了 *。考虑到替代运算符又 ban 掉了 % 和 ?。
好了我们总结下问题：假如你的键盘 [<*%? 这些符号都坏了，你现在希望通过洛谷的 \text{P1177}，该怎么写。
这看起来非常困难，好像无论如何都无法定义一个数组状物，但是经过群友的激烈讨论，我们还是找到了办法：
定义 vector 可以不用尖括号！即下面的写法是合法的：
int n;
cin>>n;
vector a(n,0);
比较新版本的 C++ 竟然可以给 vector 自动推导类型！
头文件可以用双引号包裹。
输出 cout 用不了（ < 被 ban）了，printf 也不太能用（% 被 ban）了。我们可以使用比较新的 std::print，于是我们自然地完成任务：
#include"bits/stdc++.h"
using namespace std;
int main(){
int n;cin>>n;
vector a(n,0);
for(auto&x:a) cin>>x;
ranges::sort(a);
for(auto&x:a) print("{} ",x);
println();
return 0;
}
更多的思考
那我不禁想到了另一个问题：在 C++ 中哪些符号最重要的的，如果只扣掉它程序基本写不了？
首先对于 +，我们可以使用一个冷门函数:
__builtin_add_overflow(a, b,&c)
看这个函数顾名思义就是会对 a+b 帮你进行越界检查，如果不越界就会把值存到 c 里面，即这相当于:
c=a+b;
同样道理对于 - 和 *有
__builtin_sub_overflow(a, b,&c)
__builtin_mul_overflow(a, b,&c)
注：* 作为关于指针里面的含义，显然 oier 一般都不用指针，所以 ban 掉没啥问题
关于除法和取模，我们有函数
std::div(a,b)
返回一个结构体，第一项是商，第二项是余数。
但是当然以上运算都只能进行整数，浮点数还是有点问题，但是这一点点小问题肯定达不到我们说的没有它程序写不了。
下面是 =。
关于赋值，我们可以使用
std::exchange(a,b)
这个就是可以直接让 a=b，函数返回 a 原先的值。
那关于比较运算的 ==，（整数）我们可以通过
!(a^b)//还有去符号版本：not(a xor b)
来判断，< 和 > 作为比较的释义的时候显然好办，小于可以用大于表示，大于可以用小于表示，所以我们就不多阐述了。
然后关于位运算和逻辑运算，我们可以直接用 \text{and,or,not,bitor,bitand,xor,compl} 等字符直接替代 $$,||,!,|,&,^,~
注：\text{bitand,bitor} 即使在别的释义中也可以代替 &，|，编译器会直接替换。在 & 表示取地址的时候，不过其实也可以 std::addressof
剩下的位运算只有左移右移，这个就是乘或除以 2 的 n 次方，然后左移难办些要判断越界什么的，总之是能搞的。
那么剩下的符号中：
# 我们可以用 %: 代替 # （这个是替代字符，早期 C++ 为了防止有些电脑的键盘没有这些字符，所以提供了替代字符）
: 用处不大，三目运算符，范围 for，switch 什么的都可以被替代，命名空间什么的 using 下就好了，杀伤力没那么强。
? 只有三目运算符用吧，问题不大。
\ 转义的话在 OI 中用的也不多，基本上很难平常做题用到。
. 很多类的成员方法调用不了了，但是正常写代码还是没问题的，访问成员可以结构化绑定，成员函数的话就没办法了，只能不用，但是杀伤力还没有那么大。
, 这个真没招了，它被 ban 了，只能忍着，将没有办法函数传参，任何有两个即以上的参数的函数全都调用不了。只能说吧，程序勉强还能写，只是很多库函数用不了，自己写函数的话，可以把所有参数压成数组就相当于参数列表了。
; 你或许一定以为这个被 ban 掉，C++ 真的就完蛋了吧，错误的，即使它被 ban，我们也可以艰难地写程序。
首先显然无法定义全局变量 ，和有返回值的函数（return 肯定有 ;)。
但是定义局部变量，我们可以直接写在函数参数里面，可以不用 ;。
对于其他的大部分语句，比如我们调用一个函数 f，我们可以直接：
if(f(),0){}
把语句放到参数里面可以直接避免使用 ; ！
最后是这几对符号：
`<>` 作为其他的含义我们都讲过了，剩下的含义只有传模板，避免用就好了。
`""` 注意到宏定义中 #x 代表"x"。
我们就可以直接
```cpp
#define str(x) #x
```
$\text{str(x)}$ 就可以平替了。
甚至都可以：
```cpp
#include str(iostream)
```
这个是合法的！！！
`[]` 我们有替代字符 `<:` 代替 `[`，`:>` 代替`]`。
`{}` 我们有替代字符 `<%` 代替 `{`，`%>` 代替`}`。
最后 boss：`()` 这个真是什么办法都没有了，没有任何替代字符，你也没有任何办法避免，因为你需要写主函数。
所以我们可以得到结论：一个程序只有 `()` 这个字符是万万缺少不了的。
## 回到最初
经过如上的思考，我们回到标题和起因，那么实现一个排序，最少需要多少字符呢？
首先 `()` 必然不能缺少，我们可以借用替代字符，直接 `<>%:`还顺便可以把 `#{}[]` 的字符全表示出来，感觉比较值，毕竟再怎么说 `#{}` 都得有，不用转义字符也得这用三个没比使用替代字符少多少个，但是大部分功能都完蛋了，比如如果想使用库函数要不然就得跟 `std::` 用`:`，要不然就得 `using namespace std;` 然后用 `;`。所以到底还是得再来个字符。所以还不如用替代字符比较有前途。
最开始我们的想法是，定义数组这里，我们最终选用了指针，可以
```cpp
std::add_pointer_t<int>
```
定义指针，`next(p,n)`进行指针移动，然后省掉分号，最后写出以下程序（注，主函数放那个数组会RE）：
```cpp
%:include<iostream>
%:include<algorithm>
%:include<utility>
%:include<iterator>
%:define inp std::add_pointer_t<int>
void solve(int n, int i, inp a) <%
if (std::cin >> n, std::exchange(i, n)) <%%>
while (i) <%
if (std::cin >> a<:i:>) <%%>
if (__builtin_sub_overflow(i, 1, std::addressof(i))) <%%>
%>
if (std::sort(std::next(a, 1), std::next(std::next(a, 1), n), std::greater<int>()), std::exchange(i, n)) <%%>
while (i) <%
if (std::cout << a<:i:> << char(32)) <%%>
if (__builtin_sub_overflow(i, 1, std::addressof(i))) <%%>
%>
%>
int main() <%
if (solve(0, 0, (inp)malloc(400004)), 0) <%%>
%>
```
最后使用了七种特殊字符：`%:<>(),`。
感觉可能还能凹？使用了数组仍然无济于事。
我们现在着眼于把这个 `,` 是否可以省去？
`solve` 的参数可以压进一个数组里面，循环我们可以使用视图即
```cpp
for(auto i: std::views::iota(0) bitor std::views::take(n))
//相当于 for(int i=0;i<n;i++)
```
这样就省掉了原本使用 `exchange` 和 `__builtin_sub_overflow(i, 1, std::addressof(i))`因为不需要这样大费头脑去搞循环了，里面的 `,` 也成功省掉。但是问题来了，`sort` 的`,` 怎么办？
我们期间想过无数种办法，甚至想过手写 `sort`，比如我们就想到了如何写交换：
```cpp
a xor_eq b xor_eq a xor_eq b;//xor_eq 就是^=
```
所以我们似乎可以实现个冒泡排序，但是复杂度不对。
堆排，快排，归并排序，写起来都成问题，写函数的参数我们都可以压成一个数组，但是我们到现在还没有想到一个办法不用`,;`调用一个参数的 `void` 函数）。然而不用函数写起来非常困难，所以我们也没有进行进一步的尝试（多半也不可以）。
不行，这个思路没有出路，我们要换做法。
诶？我们上文是不是提到了视图，我们很自然就能想到同样为 $\text{C++20}$ 的另一个重要特性 $\text{ranges}$。
众所周知：我们排序可以使用 `std::ranges::sort(a)` 这相当于调用 `std::sort(a.begin(),a.end())`，这样我们看似必然要使用 `,` 的排序也有救了，于是我们可以写出以下程序：
```cpp
%:include<ranges>
%:include<vector>
%:include<iostream>
%:include<algorithm>
main(int n)<%
std::cin>>n;
std::vector<int> a(n);
for(auto i:std::views::iota(0) bitor std::views::take(n))std::cin>>a<:i:>;
std::ranges::sort(a);
for(auto i:a)std::cout<<i<<char(32);
%>
```
这是一个非常简洁漂亮的七种字符的排序。
然而这种做法要用 `;`。
因为 `ranges::sort` 里面传的变量只能是 `vector` 这种容器，它对静态数组也做了特化，但是定义静态数组必然要使用分号。
而 `vector` 放到函数参数里面（不能调用构造函数），想要扩容只能用 `.` 来访问成员方法。
使用 `array` 就更不行了，光定义都要用 `,`。
我们甚至想到了 `basic_string`，它可以不用 `.` 扩容，可以直接拼接比如
```cpp
a+=b
```
但是这样有绕不开别的运算符。
我们期间还想到了各种其他的奇怪诡异做法，均无济于事。
难道七种运算符真的是理论最优了吗？真的没有六种的做法了吗？
我们想了很长时间。。。。。。。
最后我们给出了回答：
有的兄弟，有的！
## 最后的正解
机房同学突发奇想，想到了一个新的定义变量的办法！初始化列表！！！
比如我们要定义一个 `vector` 可以直接：
```cpp
for(auto i:{vector<int> a(n)}){
//在这里可以直接用 i 作为长度为 n 的 vector 了
}
```
那岂不是随便做了！！！！！
但是我们发现 `std::ranges::sort` 的返回值不能转换成 `bool`。所以我们就不能：
```cpp
if(std::ranges::sort(a)){}
```
但是话又说回来了，它的返回值不是 `void` 类型，那我们就可以仿照我们最开始定义变量的那个办法，直接：
```cpp
for(auto i:{std::ranges::sort(a)}){}
```
于是这道题我们就解决了！！！
```cpp
%:include<ranges>
%:include<vector>
%:include<iostream>
%:include<algorithm>
main(int n)<%
if(std::cin>>n)<%%>
for (auto a:<%std::vector<int>(n)%>)<%
for(auto bitand i:a)if(std::cin>>i)<%%>
for(auto i:<%std::ranges::sort(a)%>)<%%>
for(auto i:a)if(std::cout<<i<<char(32))<%%>
%>
%>
```
只用了六种特殊字符！
甚至连下划线都没用。
基本上是凹不了了，不过在和群友讨论是否能凹掉尖括号的时候，发现个还蛮有意思的写法，所以就再分享一下。
头文件可以用之前双引号那里的写法。
定义 `vector` 可以不使用 `,;<>`！
大概这么写：
```cpp
for(auto i:{decltype(std::vector{0})(n)}){}
//定义了个长度为n 的 vector<int>
```
## 结语
关于扣字符的理论还有很多可以研究，比如只用这六个特殊字符的 C++ 是否图灵完备，比如是否可以再凹到五个字符（尽管排序这道题基本上是不可能的），以及其他很多研究。
感谢 u 群群友和机房同学的帮助，才有了这篇文章。
研究 C++ 语法，其乐无穷也！