第一届TK杯题解

31 Dec 2020

为保护受害企业，赛名做匿名处理。只有程序设计竞赛类型的题目哈，和语言特性有关的题都略了。题目是根据回忆还原的，并且在不影响题意的情况下做了点简化。

T1（程序填空）

#include<iostream>
#include<string.h>
using namespace std;
void reverse(char*s,char*t){
    if(________){
        char tmp=*s;
        *s=*t;
        *t=tmp;
        ________;
    }
}
void reverse(char*s){
    ________;
}
int main(){
    char str[200];
    cin>>str;
    reverse(str);
    cout<<________;
    return 0;
}

这个程序就是让你递归地完成字符串反转嘛…

递归是要有终点的，反转字符串的递归条件是「前面的指针s和后面的指针t还没相遇」。第一空填s<t。考场上我nc写了s!=t导致和 rank #1 失之交臂，后面会讲。

第二个空是完成继续递归地调用这个函数。让s指针前进，t指针后退，填reverse(s+1,t-1)。

函数reverse(char*s)是为了让人偷懒才写出来的，里面直接转调用reverse(char*s,char*t)这个函数。关于第三空，有一个很重要的提示，那就是头文件string.h，我们要找到字符串的末尾指针，所以填reverse(s,s+strlen(s)-1)。

第四空填str。

思考一下对于字符串长度 $n=4$ 时 $<s,t>$ 对的情况： $<0,3> ~\rightarrow~ <1,2> ~\rightarrow~ <2,1> ~\rightarrow~ \color{FF0000}{<3,0> ~\rightarrow~ <4,-1> ~\rightarrow~ …}$

$<4,-1>$ 越界，并继续无止境地调用，最后爆栈。显然，对于偶数长度的字符串，s和t根本碰不到一块儿，所以第一空填s<t。

T2（结果填空）

数 625 比较神奇，因为它的平方的后 3 位数是它本身。还有另一个 3 位数也是如此。请你找出这个数。

枚举 100~999 的数，符合 $i\times i \mod 1000=i$ 就输出。答案是 376。

#include<iostream>
using namespace std;
int main(){
    for(int i=100;i<=999;++i)
        if(i*i%1000==i)
            cout<<i<<endl;
    return 0;
}

T3

规定用这种方式来表示一个形如 $X \times Y=Z$ 的算式：相同的字母表示相同的数字 ($1-9$)，不同的字母表示不同的数字，（我补充的：则 $123+111=234$ 可由 $abc+aaa=bcd$ 表示）现在给你字符串S=”dce*ba=acdb”，保证各数字最高位不为 $0$，问 $S$ 能表示的算式有哪些。（和考场上数据不一致）

考场上这题的题面很怪，我听到有人嘀咕“你说的这是中文吗”，我也不知道我猜的题意对不对。

原本的题面没有明确指出 $S$ 就是这个字符串，一开始我还以为 $S$ 是要输入的，那难度就上好几个阶梯。顺着这个思路边想边敲（对每个相同字符的索引枚举 $1-9$ 来构造数字），发现敲不出，遂放弃，最后对着这个字符串敲了个暴力算法，祈祷题目简单些…

#include<cstdio>
int main(){
    for(int a=1;a<=9;++a){
        for(int b=1;b<=9;++b){
            if(b==a)continue;  //不同字母表示不同数字，下同
            for(int c=1;c<=9;++c){
                if(c==a||c==b)continue;
                for(int d=1;d<=9;++d){
                    if(d==a||d==b||d==c)continue;
                    for(int e=1;e<=9;++e){
                        if(e==a||e==b||e==c||e==d)continue;
                        //va,vb,vc就是这几个字母组成的数字
                        int va=d*100+c*10+e;
                        int vb=b*10+a;
                        int vc=a*1000+c*100+b*10+d;
                        if(va*vb==vc)printf("%d*%d=%d\n",va,vb,vc);
                    }
                }
            }
        }
    }
    return 0;
}

T4

找出 $\left[1000,2000\right]$ 范围内千位、百位数字之和等于十位、个位数字之和的所有数字。

最后一题按题意枚举。

#include<cstdio>
int main(){
    for(int i=1000;i<=2000;++i){
        // 拿到4个数位上的数字
        int d3=i/1000;
        int d2=i/100%10; //百位
        int d1=i/10%10;  //十位
        int d0=i%10;     //个位
        // 可以试着在数字中间画一条杠来思考
        // 比如 45678/100%10
        // 45678/100 => 456|78 => 456 杠杠右边是小数，舍弃
        // 456%10    => 45|6   => 6  杠杠左边被模掉了，舍弃
        if(d3+d2==d1+d0)printf("%d\n",i);
    }
    return 0;
}

最后吐槽一下这比赛，不仅题目很水，考场规矩也水。我旁边的人对着 T4 百度了半天，监考路过也不管一下。奉劝赛方耗子尾汁…