NFLSPC #1 A题 Quine Remastered 题解

2018-12-02 00:23:50 By TRCYX
quine_n

观察题目中给出的 Quine 的标程:

#include<cstdio>
char s[]="#include<cstdio>%cchar s[]=%c%s%c;int main(){printf(s,10,34,s,34);}";int main(){printf(s,10,34,s,34);}
  • 它通过 printf 一个结构和整个程序差不多的字符串来打印程序本身
  • 引用这个字符串本身的地方用 printf 的格式串 %s 代替,并在 printf 对应位置填入自身。
  • 必须通过转义才能在字符串中直接写出来的字符(如换行符 \n、引号 \"),使用格式串 %c 搭配对应字符的编码(这里都是 ASCII 码)输出。

我们可以稍微改一改 Quine 的标程,来得到这个问题的解答。

首先我们可能希望这样:

#include<cstdio>
char s[] = /* 某个字符串 */;
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) printf(/* 用 s 打印整个程序 */);
}

缩行以后:

#include<cstdio>
char s[]=/* 某个字符串 */;int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i)printf(/* 用 s 打印整个程序 */);}

这样一来,s 大概就需要长这样:

"#include<cstdio>%cchar s[]=%c%s%c;int main(){int n;scanf(%c%c%c%c,&n);for(int i=0;i<n;++i)printf(/* 用 s 打印整个程序 */);}%c"
//                ^          ^ ^ ^                         ^ ^ ^ ^                                                          ^
//               \n          " s "                         " % d "                                 保证两次输出不粘在一起 -> \n

而对应的打印方法就是:

printf(s,10,34,s,34,34,37,100,34,10);
//        ^  ^ ^  ^  ^  ^  ^   ^  ^
//       \n  " s  "  "  %  d   " \n

然后把上文中 s 中表示打印的部分同样替换成这样,我们就可以得到:

#include<cstdio>
char s[]="#include<cstdio>%cchar s[]=%c%s%c;int main(){int n;scanf(%c%c%c%c,&n);for(int i=0;i<n;++i)printf(s,10,34,s,34,34,37,100,34,10);}%c";int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i)printf(s,10,34,s,34,34,37,100,34,10);}

这样就完成了第一个任务。

quine_rev

(这里偷点懒,直接搬选手程序了233)(会从不同思路中找一个最早的)

第二个任务需要把程序倒过来。如果直接套用之前的方法,我们必须将输出的结果先进行格式化,然后倒过来。

如果这样想,最简单的办法(需要一些 C 风格 IO 知识),是使用 sprintf,这个函数和 printf 类似,不过结果会输出到一个 char 数组,如 @smallfat 的 提交 #10016

char s[]="char s[]=%c%s%c,t[1000];int main(){sprintf(t,s,34,s,34);int len=strlen(t);while(len--)putchar(t[len]);return 0;}",t[1000];int main(){sprintf(t,s,34,s,34);int len=strlen(t);while(len--)putchar(t[len]);return 0;}

做法就是直接将格式化后的结果输出到 t 然后倒序输出。@XiaoGeNintendo 的 提交 #10209Java 中使用了类似的做法:

public class A {static String s="public class A {static String s=%c%s%c;public static void main(String[] args) {String ano=String.format(s,34,s,34);for(int i=ano.length()-1;i>=0;i--) {System.out.print(ano.charAt(i));}}}";public static void main(String[] args) {String ano=String.format(s,34,s,34);for(int i=ano.length()-1;i>=0;i--) {System.out.print(ano.charAt(i));}}}

@fafa 的 提交 #10025 运用了 C++11raw string literal,格式是 R"<delim>(<内容>)<delim>",其中 <delim> 是两个一样的字符串,中间无论写什么都会被当作字符串内容,包括换行等;然后直接用 string 的拼接构造输出:

#include<bits/stdc++.h>
const char*s=R"fafa(
void print()
{
    std::string res="#include<bits/stdc++.h>\nconst char*s=R\"faf";
    res+="a(";
    res+=s;
    res+=")fa";
    res+="fa\";";
    res+=s;
    std::reverse(res.begin(),res.end());
    std::cout<<res;
}
int main()
{
    print();
})fafa";
void print()
{
    std::string res="#include<bits/stdc++.h>\nconst char*s=R\"faf";
    res+="a(";
    res+=s;
    res+=")fa";
    res+="fa\";";
    res+=s;
    std::reverse(res.begin(),res.end());
    std::cout<<res;
}
int main()
{
    print();
}

下面三个提交的做法比较接近:@Graph_coders 的 提交 #10125 先将格式串倒序,再进行输出,而原来的 %c%s 也需要变成 c%s%

#include<bits/stdc++.h>
using namespace std;
char s[]="#include<bits/stdc++.h>c%using namespace std;c%char s[]=c%s%c%;int main(){reverse(s,s + strlen(s));printf(s,34,s,34,10,10);}";int main(){reverse(s,s + strlen(s));printf(s,34,s,34,10,10);}

@csy2005 的 提交 #10252 则是类似于这种做法的手动倒序:

#include<cstdio>
char ss[]="#include<cstdio>c%char ss[]=c%s%c%,s[]=c%s%c%;int main(){printf(s,34,ss,34,34,s,34,10);}",s[]="};)01,43,s,43,43,ss,43,s(ftnirp{)(niam tni;%c%s%c=][s,%c%s%c=][ss rahc%c>oidtsc<edulcni#";int main(){printf(s,34,ss,34,34,s,34,10);}

@superay 的 提交 #10362 是通过手写倒序构造正序:

#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;char s[]="};0 nruter;)01,01,01,43,)(rts_c.t,43,s(ftnirp;))(dne.t,)(nigeb.t(esrever{)(niam tni;s=t gnirts;%c%s%c=][s rahc;dts ecapseman gnisu%c>mhtirogla< edulcni#%c>gnirts< edulcni#%c>h.oidts< edulcni#";string t=s;int main(){reverse(t.begin(),t.end());printf(s,34,t.c_str(),34,10,10,10);return 0;}

@Zzzyt 的 提交 #10639 用的是 PythonPython 中也有类似 printf 的格式化,而且不会直接输出到 stdout,且取倒序更为方便:

s='s=%r\nprint((s%%s)[::-1])'
print((s%s)[::-1])
后记

这道题目本意是出一道有意思的代码谜题,因为代码谜题多少可以让大家从算法中解放一下思路,却不离开编程,也不是大模拟。(被 @skyline 吐槽是脑经急转弯)不过似乎大家都想不出什么好的,我就造了这道题。

本来我记得看到过一个有很有意思的回文程序(这个思路可以从 提交 #9304 中看到一点影子),不过那个程序的具体的要求和用处已经不太记得了,所以就在 Quine 的基础上弄了个水一点的版本,也就是倒序输出程序本身。我并没有指望大家都写回文程序,觉得大家各写各的,多提供思路还是很有意思的,不过对于直接 sprintf 还是有点百感交集,似乎有点过分直白了233。

考虑到如果直接这样出,可能很多人会想不出来,就放了 Quine 的例程。为了让大家熟悉这里面的逻辑,给第二个任务做铺垫,我就增加了 50 分的第一个任务。这个任务的解法和提供的程序差别真的不大。这样一来,从无到有的乐趣的确稍微减少了一点,不过送分程度就提高了,大家更难卡在不必要的地方。不过似乎还是有很多人卡住了,比如我看到有人在现场不会输出双引号等等。

另一方面 testlib 对换行的处理不尽如意,我本来是想,例如第一个任务,最后一行末没换行符,就要把相邻的两次输出粘在一起,这样更符合逻辑,但是 spj 写起来会很不美观,所以就放弃了。

(我倒是希望以后的 NFLSPC 中可以也有类似类型的题目,不过反正也不归我管了)

这个题解来得比较早,只要各位出题人不咕咕其他题的题解会慢慢给出的。

评论

avatar
skyline
我来教你at人 <span class="uoj-username" data-rating="1916">skyline</span></p>

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。