首页 书籍 蓝桥杯

# 卡片

# 题目：

小蓝有很多数字卡片，每张卡片上都必然刻有 0 ∼ 9 中的一个数字。 卡片可以用来拼凑数字，假设小蓝拥有刻有数字 1 和数字 2 的卡片各一张，那么他可以 利用这两张卡片拼凑出数字 1, 2, 12, 21 这 4 个正整数。现给定刻有数字 0, 1, . . . , 9 的卡片各 2021 张，小蓝将利用这些卡片从 1 开始连续拼凑 数字，请问他最大能拼到数字几（注意：每张卡片只能利用一次）?

# 思路：

把每个数字的个数用数组记录下来，然后枚举每个数看能不能组成并减掉使用过的数字。分析可以看出数字 1 最先消耗完，所以用 1 判断。

# 代码：

//
// Created by Doubeer on 2024/3/6.
//
#include <bits/stdc++.h>
using namespace std;
int cnt[10];
bool check(int x){ //x 表示当前枚举的数
    while(x){
        int b = x % 10; // 获取十进制下的每个数位
        if(b == 1) {
            if(cnt[1] == 0) return false;//1 最先消耗完
            cnt[1] -- ;
            }
        x /= 10; // 将十位变为个位
    }
    return true;
}
signed main(){
    for(int i = 0 ; i <= 9 ; i ++) cnt[i] = 2021;
    for(int i = 1 ; ; i ++){
        if(!check(i)) return cout << i - 1 << '\n' , 0;
    }
    return 0;
}

# 回文日期

# 题目：

给定（输入）一个 8 位数的日期，请找出（输出）该日期之后的下一个回文日期以及下 一个 ABABBABA 型回文日期。 若给定的日期为 20200202，则会有下列结果。・下一个回文日期为 20211202。・下一个 ABABBABA 型回文日期为 21211212。

# 分析：

一个一个日期判断太慢，可以只枚举年份，然后把年份反转当作月和日组成新日期，判断这个新日期是否合法即可。

# 代码：

#include <bits/stdc++.h>
using namespace std;
// 月份的日期
int date , month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
string check(int date) {
     string s = to_string(date) , t = to_string(date); // 将整型转换为字符串
     reverse(t.begin() , t.end()); // 翻转
     s += t; // 将 s 翻转后再与 s 拼接，拼接后的字符串一定会是个回文串
     int y = stoi(s.substr(0 , 4)), m = stoi(s.substr(4 , 2)), d = stoi(s.substr(6 , 2));
     if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;
     else month[2] = 28;
     if (m < 1 || m > 12 || d < 1 || d > month[m]) return "-1";
     return s;
}
string check1(int date) {
    string s = to_string(date) , t = to_string(date); // 将整型转换为字符串
    reverse(t.begin() , t.end()); // 翻转
    s += t;
    if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])
        return s;
    return "-1";
}
int main() {
   cin >> date;
   string ans1 = "";
   for (int i = date / 10000; ; i++) {
       // 没找到或者找到自身
       if (check(i) == "-1" || check(i) == to_string(date)) continue;
       if (ans1 == "") ans1 = check(i);
       if (check1(i) != "-1") return cout << ans1 << '\n' << check1(i) << '\n' , 0;
   }
   return 0;
}
# 赢球票


# 题目：


给定 n 张卡片，卡片上分别写着数字 a1, a2, . . . , an。 现将这 n 张卡片围成一个圈。 我们可以从圈上任意一个位置开始顺时针数数：1, 2, 3 . . .。 若当前数到的数字和卡片上的数字相同，则将卡片取走，并从下一张卡片所在位置重新 数数：1, 2, 3 . . .。 问我们取走的卡片上的数字之和最大可以是多少？


# 分析：


用数组保存数据，pos 表示当前位置，pos++ 模拟转圈，pos=n 时，pos 重新赋值 1。


用数组 flag 来记录卡片拿走与否，如果卡片已经被拿走，则 pos++，否则标记


# 代码：


#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, a[N], flag[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans;
    for (int i = 0; i < n; i++) {// 枚举每个位置作起点
        for (int j = 1 ; j <= n ; j ++) flag[j] = 0;
        //num 表示数的数的值，pos 表示当前位置，sum 表示以 i 为起点数数所能取走的卡片的和，cnt 表示拿走的卡片的数量
        int num = 1, pos = i, sum = 0, cnt = 0;
        while (1) {
            if (cnt == n || num > n) break;
            if (flag[pos] == 1) {// 如果该卡片已被取走，则移动到下一个位置
                if (pos == n) pos = 1;
                pos++;
                continue;
            }
            // 数的数和当前位置卡片的值相同时取走该卡片（a [pos] 表示第 pos 张卡片的值）
            if (num == a[pos]) {
                sum + a[pos];
                cnt++;
                num = 1;
                flag[pos] = 1;
                if (pos == n) pos = 1;
                else pos++;
            } else {
                // 数的数和当前位置卡片的值不相同时
                num++;
                if (pos == n) pos = 1;
                else pos++;
            }
        }
        // 模拟结束
        if (sum > ans) ans = sum;
    }
    cout << ans << '\n';
    return 0;
}
# 即约分数


# 题目：


如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。 例如 3 4 , 1 8 , 7 1 ，都是既约分数。 请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020 ）？


# 分析


辗转相除法 gcd (i,j) 求 i 和 j 的最大公约数，枚举分母和分子，然后 gcd 判断最大公约数是不是等于 1


# 代码：


#include<bits/stdc++.h>
using namespace std;
signed main()
 {
 int ans = 0;
 for(int i = 1 ; i <= 2020 ; i ++){
 for(int j = 1 ; j <= 2020 ; j ++){
 if(＿gcd(i , j) == 1) ans ++ ;
 }
}
 cout << ans << '\n';
 return 0;
}主函数结束
# 数的分解


# 题目：


把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。


# 分析：


暴力复杂度 o（n^3), 想办法降低。用数组 flag 把数是否满足条件保存起来。三个加数 a，b，c，知道 a，b 则 c = 2019-a-b，且 a<b<c


# 代码：


#include <bits/stdc++.h>
using namespace std;
bool check(int x) {
    while (x) {
        if (x % 10 == 2 || x % 10 == 4) return false;
        x /= 10;
    }
    return true;
}
bool flag[2020];
int main() {
    int ans = 0;
    for(int i = 1 ; i <= 2019 ; i ++) if(check(i)) flag[i] = 1; // 在枚举前判断一个数是否包含 2 和 4，避免在枚举过程中判
    for(int i = 1 ; i <= 2019 ; i ++)
         for(int j = i + 1 ; j < 2019 - i - j ; j ++) // i < j < 2019 - i - j
         if(flag[i] && flag[j] && flag[2019 - i - j]) // 通过 flag 判断，复杂度 O (1)
         ans ++;
     cout << ans << '\n';
     return 0;