1998-NOIP-普及组：复赛真题及解析

题目

说明：点击题目名称即可跳转原题链接 🙂

三连击

思路

1. 可以用 i 枚举最小的数，范围易知是 (123 ~ 987/3)，由此可以知道 2 * i 和 3 * i，然后对枚举得到的 i，2 * i，3 * i 进行个十百位拆位标记。
2. 扫描标记数组，根据题意，必须 1 ~ 9 中每个数字都被标记成出现过才是满足条件的，因此一旦出现一个数未出现过，可得出不满足，break 结束判断。
3. 输出标记数组检验后满足条件的数字组合。
4. 时间复杂度：O(1), 空间复杂度：O(1)。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
        for(int i = 123; i <= 987 / 3; i++){ // i: 枚举最小的 3 位数
                bool a[10] = {0}, f = 1; // f: 假设满足条件 
                for(int j = i; j <= 3 * i; j += i){ // j: 枚举 i, 2 * i, 3 * i，并拆位标记 
                        a[j % 10] = a[j / 10 % 10] = a[j / 100] = 1; 
                }
                for(int j = 1; j <= 9; j++){
                        if(!a[j]){ // 只要有一个数没出现过 
                                f = 0; // 就不满足条件 
                                break; // 结束判断 
                        }
                } 
                if(f){
                        printf("%d %d %d\n", i, 2 * i, 3 * i);
                }
        }
        return 0;
} 

阶乘之和

思路

1. int 范围内能求解的最大阶乘为 12！(479001600)，long long 范围内能求解的最大阶乘为 20！(2432902008176640000)，而本题要求解最大到 50！和，只能用高精度乘法和加法模拟计算过程。
2. 分别用两个数组存储中间过程答案，数组 a 记录 i！，数组 b 记录截至 i 的阶乘和。
3. 从 2 开始枚举每一个要乘的数依次与 (i-1)! 的每一位进行高精度 * 低精度，乘完后处理进位。获得 i! 更新完 a[] 后，再将 a[] 与 b[] 进行高精度加法更新 b[] 中阶乘和答案。
4. 从高位到低位输出 b[]。

代码

#include <bits/stdc++.h>
using namespace std;

int n, len, a[100], b[100]; // a[]: 阶乘  b[]: 阶乘和 
int main(){
        cin >> n;
        a[1] = b[1] = 1; // 初始化最低位为 1
        len = 1; // 初始化答案长度为 1 
        for(int i = 2; i <= n; i++){ // i: 从 2 开始枚举每一个要乘的数 
                for(int j = 1; j <= len; j++){ // j: 遍历 a[] 的每一位 
                        a[j] *= i; // 高精度 * 低精度 
                }
                for(int j = 1; j <= len; j++){ // 处理进位 
                        a[j + 1] += a[j] / 10;
                        a[j] %= 10; 
                }
                while(a[len + 1]){ // 处理最高位进位 
                        len++;
                        a[len + 1] = a[len] / 10;
                        a[len] %= 10;
                } 
                for(int j = 1; j <= len; j++){ // 累加 i! 到 b[] 
                        b[j] += a[j];
                        b[j + 1] += b[j] / 10; // 处理进位 
                        b[j] %= 10; 
                }        
        }
        for(int i = len; i >= 1; i--){ // 从高位到低位输出 
                cout << b[i];
        }
        return 0;
} 

幂次方

思路

1. 从高位到低位找 n 的二进制表示中为 1 的那些位，可以用 n & (1 << i) 判断第 i 位情况，n 最大 20000，二进制下不超过 15 位，移位 i 的范围为 14 ~ 0。
2. 对于找到的二进制下为 1 的第 i 位，需要根据 i 的值判断输出：
   1. 若 i 为 0，输出是 “2(0)”;
   2. 若 i 为 1，输出是 “2”;
   3. 若 i 为其它大于 1 的数，说明还可以将 i 转二进制表示，递归调用 f(i)，求其表达值，这之前加上 “2(“，之后加上 “)”；
3. 如果后面还有二进制下为 1 的位没表示完，则 x 减掉当前位权重后还会大于 0，拼接 “+” 连接后续输出内容。

代码

#include <bits/stdc++.h>
using namespace std;

int n;
void f(int x){
        for(int i = 14; i >= 0; i--){ // 从高位到低位找二进制下的 1 
                if(x & (1 << i)){ // 该位为 1 
                        x -= (1 << i); // 减掉该位权重  
                        if(!i){ // 若 i 为 0，输出 2(0)
                                printf("2(0)");
                        }
                        else if(i == 1){ // i 为 1 直接输出 2 
                                printf("2");
                        }
                        else{ // i 为大于 1 的值，递归表示 i 
                                printf("2(");
                                f(i); // 找 i 的值二进制下的表示 
                                printf(")");
                        }
                        if(x){ // 还没表示完，+ 拼接下一位 
                                printf("+");
                        }        
                }
        }
}

int main(){
        cin >> n;
        f(n);
        return 0;
}