2024C++信息素养大赛-智能算法应用挑战赛_复赛真题（广东省）题目+参考答案和详细解析

1.翻转数相乘

【题目描述】

假设一个n位数，如a1a2a3...an，其中a1是这个数的第i位上的数字，,且这个n位数不是每个位都相等的数字，例如不是2222或类似。如果,有一个整数x，并且1<x<10,使得a1a2a3...an*x=an…a2a1，求x，其中a1和an不能为0，如果x无解，则输出0，如果有多个x，则从小到大输出,所有x的解，中间用空格隔开。例如：一个5位数，ABCDE*?=EDCBA其中A、B、C、D、E是个位整数，ABCDE和EDCBA是一个万位数，求符合这个等式的乘数。

【输入格式】输入1个数，表示要求解的n位数。

【输出格式】输出表示所有可能的乘数，并按照从小到大排列，用回车隔开。

【样例输入】（测试数据不包含本样例）

6

【样例输出】

4

9

#include <bits/stdc++.h>
using namespace std;
 
// 将一个数字字符串反转
string reverseString(const string &str) {
    string reversedStr = str;            // 复制输入字符串
    reverse(reversedStr.begin(), reversedStr.end()); // 反转字符串
    return reversedStr;                  // 返回反转后的字符串
}
 
// 将一个数字字符串乘以一个整数
string multiplyStringByInt(const string &num, int x) {
    string result;                       // 存储乘积结果
    int carry = 0;                       // 进位
    // 从最低位开始逐位相乘
    for (int i = num.size() - 1; i >= 0; --i) {
        int product = (num[i] - '0') * x + carry; // 当前位与 x 相乘，加上进位
        result.push_back((product % 10) + '0');   // 保存当前位的结果
        carry = product / 10;                     // 更新进位
    }
    // 处理剩余的进位
    while (carry) {
        result.push_back((carry % 10) + '0');
        carry /= 10;
    }
    reverse(result.begin(), result.end());        // 反转结果字符串
    return result;                                // 返回乘积结果
}
 
// 计算 10 的 n 次幂
int powerOfTen(int n) {
    int result = 1;                     // 初始化结果为 1
    for (int i = 0; i < n; ++i) {
        result *= 10;                   // 连乘 n 次 10
    }
    return result;                      // 返回 10 的 n 次幂
}
 
// 检查某个 x 是否满足条件
bool isValid(int n, int x) {
    int start = powerOfTen(n - 1);      // n 位数的起始值（最低 n 位数）
    int end = powerOfTen(n);            // n 位数的终止值（超出 n 位数的最小值）
 
    // 枚举所有 n 位数
    for (int i = start; i < end; ++i) {
        string original = to_string(i); // 将数字转换为字符串
        string reversed = reverseString(original); // 反转字符串
        string product = multiplyStringByInt(original, x); // 计算乘积
        // 检查乘积是否等于反转后的字符串
        if (product == reversed) {
            return true;                // 如果相等，返回 true
        }
    }
    return false;                       // 如果没有满足条件的 x，返回 false
}
 
int main() {
    int n;                              // 输入的 n 位数的位数
    cin >> n;                           // 读取输入
    vector<int> solutions;              // 存储所有符合条件的 x
 
    // 枚举所有可能的 x（从 2 到 9）
    for (int x = 2; x < 10; ++x) {
        if (isValid(n, x)) {            // 检查 x 是否符合条件
            solutions.push_back(x);     // 如果符合，加入结果集
        }
    }
 
    // 输出结果
    if (solutions.empty()) {            // 如果没有符合条件的 x
        cout << 0 << endl;              // 输出 0
    } else {
        for (size_t i = 0; i < solutions.size(); ++i) { // 遍历结果集
            cout << solutions[i] << endl; // 输出每一个符合条件的 x
        }
    }
 
    return 0;                           // 程序结束
}

2.吉利号码

[题目描述]

中国人喜欢图吉利，包括吉利数字，例如数字8或者数字6,尤其是连着的数字更加喜欢，比如手机号码，汽车车牌，房间号码等等。有需求就会有市场，吉利数字的号码，往往意味着更贵的价格。请你根据以下规则，编写一个程序，根据规则给一个号码设置相应的价格。

具体规则如下:

1.正常号码是100元。

2. 含有:6,8任何一个数字，每出现一次加50元，例如4326,6875,9918都符合加分标准。其中，6875被加2个50元，就相当于加100元。

3.如果出现升序或者降序的情况，不管升序还是降序，号码涨价3倍。例如:5678,4321都要贵3倍。注意:例如5567,4331等有相同元素的号码不算降序、升序。

4.如果出现三个相同数字情况，都涨6倍。例如:4888,6665,7777都满足加分的标准。注意:7777因为满足这条标准两次，所以这条规则给它涨两个6倍，也就是12倍。

5.如果符合AABB或者ABAB模式的，价格涨一倍。例如:2255,3939,7777都符合这个模式，所以都会涨价。注意:7777因为满足这条标准两次，所以这条标准给它涨2倍，同时7777也是连号，也会在之前连号的基础上继续涨价。

请编写程序按照所有规则，求一个号码的最终价格!要求程序从标准输入接收数据，在标准输出上输出结果。

[输入格式]

输入共1行，输入一个四位正整数，就是待计算的号码。

[输出格式]

输出共1行，一个整数，表示这个号码对应的销售价格。

[样例输入](测试数据不包含本样例)

6543

[样例输出]

450

#include<bits/stdc++.h>
 
using namespace std;
 
// 计算号码的销售价格
int calculatePrice(int number) {
    string numStr = to_string(number); // 将数字转换为字符串方便处理
    int price = 100; // 初始价格为100元
 
    // 规则2：含有6或8的数字，每个加50元
    for (char digit : numStr) {
        if (digit == '6' || digit == '8') {
            price += 50;
        }
    }
 
    // 规则3：升序或降序，价格涨3倍
    bool ascending = is_sorted(numStr.begin(), numStr.end());
    bool descending = is_sorted(numStr.rbegin(), numStr.rend());
    if (ascending || descending) {
        price *= 3;
    }
 
    // 规则4：三个相同的数字，价格涨6倍
    if (numStr[0] == numStr[1] && numStr[1] == numStr[2]) {
        price *= 6;
    } else if (numStr[1] == numStr[2] && numStr[2] == numStr[3]) {
        price *= 6;
    }
 
    // 规则5：AABB或ABAB模式，价格涨1倍
    if ((numStr[0] == numStr[1] && numStr[2] == numStr[3]) ||
        (numStr[0] == numStr[2] && numStr[1] == numStr[3])) {
        price *= 2;
    }
 
    return price;
}
 
int main() {
    int number;
    cin >> number; // 输入待计算的号码
    int finalPrice = calculatePrice(number); // 计算号码的最终价格
    cout << finalPrice << endl; // 输出最终价格
 
    return 0;
}

3.将整数换成分数

[题目描述]

一个小于100万的正整数n，尝试把n变成带分数形式，也就是 n=a+b/c,其 中a,b,c是三个正整数，并且数字1~9(不含0)在a、b、c中，必须出现，且只能出现一次。例如:100=3+69258/714,其中1到9这9个数字全都出现了，并且只出现一次。当然，100还等于82+3546/197,也就是说将100变成带分数形式，会有两种组合方式。事实上100,可以写成11种1到9组成整数加上分数的形式。

请编写一个程序，根据一个输入N，程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部可能性。不要求输出每个表示，只输出有多少种表示法!

[输入格式]

输入一行，表示要分解的正整数。

[输出格式]

输出一行，表示有多少分法。

【样例输入](测试数据不包含本样例)

100

[样例输出]

11

#include<bits/stdc++.h>
 
using namespace std;
 
// 判断三个整数的组合是否包含1到9且每个数字只出现一次
bool isValidCombination(int a, int b, int c) {
    string str = to_string(a) + to_string(b) + to_string(c);
    if (str.size() != 9) return false;  // 长度必须正好为9
    unordered_set<char> digits(str.begin(), str.end());
    return digits.size() == 9 && digits.find('0') == digits.end();  // 不包含0且包含所有数字1-9
}
 
int main() {
    int n;
    cin >> n;
    int count = 0;
 
    // 枚举所有可能的a，b，c
    // 枚举所有可能的c
    for (int c = 1; c <= 98765; ++c) {
        // 枚举所有可能的a
        for (int a = 1; a < n; ++a) {
            // 计算 b 的值
            int b = (n - a) * c;
            
            // 检查是否符合数字组合条件
            if (b > 0 && isValidCombination(a, b, c)) {
                count++;
            }
        }
    }
 
    cout << count << endl;
    return 0;
}

4.战胜白蚁

[题目描述]

小明因为很长时间没有回家，发现他家被白蚁给入侵了，白蚁特别喜欢啃食木头，因此他家的地板就遭殃了。小明要抢救被白蚁破坏的木地板，每个木地板由于白蚁的数量不同，每个地板进行维修的时间也不同，同时要争取及时修理越好，否则超过某个时间，这块地板就会被严重破坏掉。小明只能一块一块的清理白蚁，不能并行操作，也就是不能同时修多块地板。

请编写一个程序，根据每个地板的修理时间和如果不修理就会被白蚁完全损毁的 时间，进行一个最合理的排序，使得可以抢救最多的木板。输入是木板的数目，以及每个木板的维修时间和被破坏的时间，输出是能抢救的最多木板的数量。

[输入格式]

第一行是一个整数N(N小于50000),接下来N行每行两个整数T1,T2描述一个要修理的木板:修理这个木板需要T1秒，如果在T2秒之内还没有修理完成，这个木板就报废了。

[输出格式]

输出一个整数S，表示最多可以抢修S个木板。

[样例输入](测试数据不包含本样例)

4

100 200

200 1300

1000 1250

2000 3200

【样例输出]

3

#include <bits/stdc++.h>
using namespace std;
 
// 定义木板结构体
struct Board {
    int T1; // 修理时间
    int T2; // 被破坏时间
};
 
// 比较函数，按照 T2 升序排序
bool compare(Board& b1, Board& b2) {
    return b1.T2 < b2.T2;
}
 
int rescueBoards(int N, vector<Board>& boards) {
    // 按照 T2 升序排序
    sort(boards.begin(), boards.end(), compare);
    
    int rescuedCount = 0;
    int currentTime = 0;
    
    for (int i = 0; i < N; ++i) {
        if (currentTime + boards[i].T1 <= boards[i].T2) {
            rescuedCount++;
            currentTime += boards[i].T1;
        }
    }
    
    return rescuedCount;
}
 
int main() {
    int N;
    cin >> N;
    
    vector<Board> boards(N);
    for (int i = 0; i < N; ++i) {
        cin >> boards[i].T1 >> boards[i].T2;
    }
    
    int result = rescueBoards(N, boards);
    cout << result << endl;
    
    return 0;
}