专栏文章

论如何在键盘的大部分标点符号都坏掉的情况下实现排序

CCybher
休闲·娱乐参与者 84已保存评论 97

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
97 条
当前快照
1 份
快照标识符
@mj1oq090
此快照首次捕获于
2025/12/12 01:01
2 个月前
此快照最后确认于
2026/02/13 01:26
7 天前
查看原文
（这篇文章主要展示一些我在研究关于扣标点符号问题的一些想法，所以行文可能比较意识流，主要还是介绍一些思考过程中的小想法。另外注下划线在这篇文章不被归于标点符号，因为姑且对这个符号的定义是不能作为变量名称中的非空白字符）

起因

和机房同学闲聊的时候聊到了个奇怪的问题，就是关于排序这道题，如果把 [ 这个符号 ban 掉，该怎么写。然后我发现似乎还能使用 vector。于是我又 ban 掉了 <，他又想到了可以指针，于是我又 ban 掉了 *。考虑到替代运算符又 ban 掉了 % 和 ?。
好了我们总结下问题：假如你的键盘 [<*%? 这些符号都坏了，你现在希望通过洛谷的 P1177\text{P1177}，该怎么写。
这看起来非常困难，好像无论如何都无法定义一个数组状物，但是经过群友的激烈讨论，我们还是找到了办法：
定义 vector 可以不用尖括号！即下面的写法是合法的：
CPP
int n;
cin>>n;
vector a(n,0);
比较新版本的 C++ 竟然可以给 vector 自动推导类型！
头文件可以用双引号包裹。
输出 cout 用不了（ < 被 ban）了，printf 也不太能用（% 被 ban）了。我们可以使用比较新的 std::print，于是我们自然地完成任务：
CPP
#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++ 中哪些符号最重要的的，如果只扣掉它程序基本写不了？
首先对于 +，我们可以使用一个冷门函数:
CPP
__builtin_add_overflow(a, b,&c)
看这个函数顾名思义就是会对 a+ba+b 帮你进行越界检查，如果不越界就会把值存到 cc 里面，即这相当于:
CPP
c=a+b;
同样道理对于 - 和 *有
CPP
__builtin_sub_overflow(a, b,&c)

__builtin_mul_overflow(a, b,&c)
注：* 作为关于指针里面的含义，显然 oier 一般都不用指针，所以 ban 掉没啥问题
关于除法和取模，我们有函数
CPP
std::div(a,b)
返回一个结构体，第一项是商，第二项是余数。
但是当然以上运算都只能进行整数，浮点数还是有点问题，但是这一点点小问题肯定达不到我们说的没有它程序写不了。
下面是 =。
关于赋值，我们可以使用
CPP
std::exchange(a,b)
这个就是可以直接让 a=ba=b，函数返回 aa 原先的值。
那关于比较运算的 ==，（整数）我们可以通过
CPP
!(a^b)//还有去符号版本：not(a xor b)
来判断，< 和 > 作为比较的释义的时候显然好办，小于可以用大于表示，大于可以用小于表示，所以我们就不多阐述了。
然后关于位运算和逻辑运算，我们可以直接用 and,or,not,bitor,bitand,xor,compl\text{and,or,not,bitor,bitand,xor,compl} 等字符直接替代 $$,||,!,|,&,^,~
注：bitand,bitor\text{bitand,bitor} 即使在别的释义中也可以代替 &，|，编译器会直接替换。在 & 表示取地址的时候，不过其实也可以 std::addressof
剩下的位运算只有左移右移，这个就是乘或除以 22 的 nn 次方，然后左移难办些要判断越界什么的，总之是能搞的。
那么剩下的符号中：
# 我们可以用 %: 代替 # （这个是替代字符，早期 C++ 为了防止有些电脑的键盘没有这些字符，所以提供了替代字符）
: 用处不大，三目运算符，范围 for，switch 什么的都可以被替代，命名空间什么的 using 下就好了，杀伤力没那么强。
? 只有三目运算符用吧，问题不大。
\ 转义的话在 OI 中用的也不多，基本上很难平常做题用到。
. 很多类的成员方法调用不了了，但是正常写代码还是没问题的，访问成员可以结构化绑定，成员函数的话就没办法了，只能不用，但是杀伤力还没有那么大。
, 这个真没招了，它被 ban 了，只能忍着，将没有办法函数传参，任何有两个即以上的参数的函数全都调用不了。只能说吧，程序勉强还能写，只是很多库函数用不了，自己写函数的话，可以把所有参数压成数组就相当于参数列表了。
; 你或许一定以为这个被 ban 掉，C++ 真的就完蛋了吧，错误的，即使它被 ban，我们也可以艰难地写程序。
首先显然无法定义全局变量 ，和有返回值的函数（return 肯定有 ;)。
但是定义局部变量，我们可以直接写在函数参数里面，可以不用 ;。
对于其他的大部分语句，比如我们调用一个函数 ff，我们可以直接：
CPP
if(f(),0){}
把语句放到参数里面可以直接避免使用 ; ！
break,continue,goto\text{break,continue,goto} 等控制语句显然不是非常必要，for 被 while 代替，基本大部分要用到的语句都可以塞到条件里面，循环和判断语句可以嵌套（反正不费分号）。
最后是这几对符号：
<> 作为其他的含义我们都讲过了，剩下的含义只有传模板，避免用就好了。
"" 注意到宏定义中 #x 代表"x"。
我们就可以直接
CPP
#define str(x) #x
str(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 函数）。然而不用函数写起来非常困难，所以我们也没有进行进一步的尝试（多半也不可以）。
不行，这个思路没有出路，我们要换做法。
诶？我们上文是不是提到了视图，我们很自然就能想到同样为 C++20\text{C++20} 的另一个重要特性 ranges\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++ 语法，其乐无穷也！

评论

共 97 条评论，欢迎与作者交流。

正在加载评论...