蓝桥杯题型

蓝桥杯题型分类

模拟

艺术与篮球（日期问题）

#include <bits/stdc++.h>
using namespace std;map<char,int>myMap;
int basketball,calligraphy;//日期是否合法模板
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date)
{int year=date/10000,month=date%10000/100,day=date%100;if(!month||month>=13||!day)return false;if(month!=2&&day>months[month])return false;if(month==2){int leap=(year%100!=0&&year%4==0)||year%400==0;if(day>28+leap)return false;}return true;
}int main() 
{// 插入数字与笔画数myMap['0'] = 13;myMap['1'] = 1;myMap['2'] = 2;myMap['3'] = 3;myMap['4'] = 5;myMap['5'] = 4;myMap['6'] = 4;myMap['7'] = 2;myMap['8'] = 2;myMap['9'] = 2;// 遍历日期范围，从2000年1月1日到2024年4月13日for(int i=20000101;i<=20240413;i++){if(check(i)){string s=to_string(i);int num=0;for(auto j:s){num+=myMap[j];}if(num>50){basketball++;}}}cout<<basketball;return 0;
}

时间显示（时间问题）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() 
{ll x;cin >> x;// 计算小时、分钟、秒数ll hh = (x / 3600000) % 24;  // 小时数，取 24 小时制ll mm = (x / 60000) % 60;     // 分钟数，取 60 分钟ll ss = (x / 1000) % 60;      // 秒数，取 60 秒// 输出时间格式printf("%02lld:%02lld:%02lld", hh, mm, ss);return 0;
}

跑步计划（日期问题）

#include <bits/stdc++.h>
using namespace std;int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  // 每个月的天数// 检查数字是否包含1
bool check(int x) {while (x) {if (x % 10 == 1) {return true;  // 如果数字中包含1，返回true}x /= 10;  // 去除最后一位}return false;  // 如果没有1，返回false
}int main() {int ans = 0;  // 总跑步的千米数int week = 6;  // 2023年1月1日是星期天，所以初始化为6（星期天）// 遍历每个月for (int i = 1; i <= 12; i++) {// 遍历每个月的每一天for (int j = 1; j <= months[i]; j++) {week = (week % 7) + 1;  // 更新星期几，确保在1到7之间循环（星期天为7）// 如果日期、月份或星期几包含1，跑5千米if (check(i) || check(j) || check(week)) {ans += 5;} else {ans += 1;  // 否则跑1千米}}}cout << ans;  // 输出小蓝总共跑的千米数return 0;
}

偶串(字符）

使用 Map 或者 unordered_map。
遍历字符串中的每个字符。对每个字符，检查它是否已经在你的数据结构中。如果是，增加它的计数。

#include <iostream>
#include <unordered_map>
using namespace std;int main() {string str;cin >> str;  // 输入字符串unordered_map<char, int> char_count;  // 用哈希表存储每个字符的出现次数// 遍历字符串并统计每个字符的出现次数for (char c : str) {char_count[c]++;}// 检查是否每个字符出现次数为偶数bool is_even = true;for (auto& pair : char_count) {if (pair.second % 2 != 0) {  // 如果出现次数是奇数is_even = false;break;}}// 输出结果if (is_even) {cout << "YES" << endl;} else {cout << "NO" << endl;}return 0;
}

创建一个大小为26的整数数组（假设为 cnt），用于存储每个小写字母的出现次数。数组的索引 
0−25 分别对应字母 a-z。
遍历字符串的每一个字符（假设为 c）：
将字符 c 转为其 ASCII 值。
通过计算 c - 'a' 来得到一个从 0
0 到 25 的索引，这个索引对应于字符 c。
使用这个索引来增加 cnt 数组中对应元素的值。
遍历结束后，cnt 数组中的每个元素就存储了对应字母在字符串中的出现次数。

#include <iostream>
#include <vector>using namespace std;int main()
{string s;vector<int> cnt(26);cin >> s;for (auto c : s){cnt[c - 'a']++;}for (int i = 0; i < 26; ++i){if (cnt[i] % 2){cout << "NO" << '\n';return 0;}}cout << "YES" << '\n';return 0;
}

最长子序列（字符）

#include <iostream>
#include <string>
using namespace std;int main() {string s, t;int num = 0;cin >> s >> t;for (char ch : t) {// 查找当前字符ch在s中的位置size_t pos = s.find(ch);if (pos == string::npos) {// 如果找不到字符，直接输出已找到的匹配数并结束程序cout << num;return 0;} else {// 如果找到了字符，更新字符串s并增加计数num++;s = s.substr(pos + 1);  // 从pos+1开始截取s}}// 输出最终匹配的字符数cout << num;return 0;
}

字母数（进制转换）

#include <bits/stdc++.h>
using namespace std;using ll=long long;
int a[1000];
char ch[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };bool solve(int x)//十进制转换为16进制
{string ans;while(x){if(ch[x%16]>='A'){ans+=ch[x%16];x/=16;}else{return false;}}reverse(ans.begin(),ans.end());return true;
}
int main() 
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int i=2022;while(true){i++;if( solve(i)){cout<<i;return 0;}}return 0;
}

6个0（进制转换）

#include <bits/stdc++.h>
using namespace std;bool check(int x)
{// 检查最低的 5 位是否都为 0for(int i = 0; i < 5; i++){if(((x >> i) & 1) != 0) // 如果第 i 位不为 0，返回 false{return false;}}return true;
}int main() 
{int x = 2022; // 从 2022 开始查找while(true){x++; // 从 2023 开始检查if(check(x)) // 如果 x 的最低 5 位全为 0{cout << x;return 0;}}return 0;
}

优秀的拆分（位运算）

• 输入输出样例
  示例 1
  输入

6

输出

4 2

示例 2
输入

7

输出

-1

7的二进制数为（0111），6的二进制数为（0110），可以发现7的二进制位的最低位（第0位）为1，值为
$2^0$ ,所以只要最低位为1，就不是优秀的拆分。我的从最高位开始遍历，只要第i位为1，我们就输出 1<<i ,即为$2^i$

#include <bits/stdc++.h>
using namespace std;int main() {int num;cin >> num;// 如果最低位为 1，输出 -1if (((num >> 0) & 1) == 1) {cout << -1 << endl;return 0;}// 从最高位开始遍历，检查每一位for (int i = 30; i >= 0; i--) {// 如果当前位为 1，输出 2^iif (((num >> i) & 1) == 1) {cout << (1 << i) << " ";}}return 0;
}

幸运数字的个数(预计算）

样例输入
6
1 10
1 16
1 17
10 100
100 1000
1000 10000

样例输出
10
15
16
11
13
14

说明
对于所有评测数据：

$1\le T\le 10^5,1\le l_i\le r_i\le 10^{12}。$

要用到的思想是先“离线”预计算所有可能的幸运数字，再用二分查找快速计算每个查询区间内的幸运数字数量。具体做法如下：

先枚举所有“十六进制中由同一字符重复”的数字，排除超过 10^12 的值，并将这些数字存储到一个数组并排序；
对每次给定的范围 [l, r]，使用二分查找定位区间上下界，从而快速统计落在该区间内的幸运数字个数。

#include <bits/stdc++.h>
using namespace std;static const long long MAX_VAL = 1000000000000LL; // 1e12// 预先生成所有在 [1, 1e12] 范围内 "十六进制由同一数字重复" 的幸运数字
// 注意：digit 取值范围是 [0..15]，长度取值范围适当即可（1~16足够覆盖1e12）
vector<long long> generateLuckyNumbers() {vector<long long> luckyNums;// 十六进制最大可用字符：0~f (共16个)for (int digit = 0; digit < 16; ++digit) {for (int length = 1; length <= 16; ++length) {// 构建长度为 length 的重复字符// 例如若 digit = 12 (十六进制 c)，length = 4，则是"cccc"// 然后转为十进制，判断是否 <= 1e12// digit 转成对应的16进制字符char hexDigit;if (digit < 10) {hexDigit = char(digit + '0');} else {hexDigit = char(digit - 10 + 'a');}// 构建重复串string hexStr(length, hexDigit);// 转成十进制// stoll(hexStr, nullptr, 16) 有可能超范围，用更安全方式// 这里用 64位整型计算long long num = 0;for (char c : hexStr) {// digitVal 可以用 c - '0' 或 c - 'a' + 10// 但我们已经知道是同一个字符int val;if (isdigit(c))val = c - '0';elseval = c - 'a' + 10;num = num * 16 + val;// 若已经超过范围就中断if (num > MAX_VAL) break;}if (num > 0 && num <= MAX_VAL) {luckyNums.push_back(num);}}}// 去重并排序sort(luckyNums.begin(), luckyNums.end());luckyNums.erase(unique(luckyNums.begin(), luckyNums.end()), luckyNums.end());return luckyNums;
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);// 预先生成所有可能的幸运数字static vector<long long> luckyNumbers = generateLuckyNumbers();int T;cin >> T;while (T--) {long long l, r;cin >> l >> r;// 在 luckyNumbers 中，用二分查找统计区间 [l, r] 内的元素个数auto leftIt = lower_bound(luckyNumbers.begin(), luckyNumbers.end(), l);auto rightIt = upper_bound(luckyNumbers.begin(), luckyNumbers.end(), r);cout << (rightIt - leftIt) << "\n";}return 0;
}

二分

123

传送门

1. 小区间的构成

假设数列的构成是如下形式：

• 第 1 个区间包含 1 个元素（1）。
• 第 2 个区间包含 2 个元素（1 2）。
• 第 3 个区间包含 3 个元素（1 2 3）。
• 第 4 个区间包含 4 个元素（1 2 3 4）。
• …

第 i 个小区间包含 i 个元素。我们将这些小区间连起来形成整个数列。

2. 数组 a[j] 的定义

数组 a[j] 表示前 j 个小区间的总元素数，同时也能表示每个小区间的和。例如：

• a[1] = 1 （表示前 1 个小区间有 1 个元素）
• a[2] = 1 + 2 = 3 （表示前 2 个小区间共有 3 个元素）
• a[3] = 1 + 2 + 3 = 6 （表示前 3 个小区间共有 6 个元素）
• a[4] = 1 + 2 + 3 + 4 = 10 （表示前 4 个小区间共有 10 个元素）

注意，数组 a[j] 是单调递增的，因为每个小区间的元素个数都在增加。

关键点：k = i - a[j]

• 数列中的位置 i 是在第 j+1 个区间中的某个元素。
• 前 j 个区间包含了 a[j] 个元素，也就是说，第 j+1 个区间的第一个元素出现在位置 a[j] + 1。

因此，位置 i 在第 j+1 个区间的具体位置是：

• 第 j+1 个区间的第 k 个元素：k 就是位置 i 相对于第 j+1 个区间开始位置的偏移量。

由于前 j 个区间包含了 a[j] 个元素，第 j+1 个区间从位置 a[j] + 1 开始。所以位置 i 在第 j+1 个区间中的具体位置是：

k = i - a[j]

#include <iostream>
using namespace std;
using ll=long long;
const int N=1414215;ll a[N],s[N];ll persum(ll i)
{ll l=0,r=N;while(l<r){ll mid=(l+r+1)>>1;if(a[mid]<i)l=mid;else r=mid-1;}return  s[l]+a[i-a[l]];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i=1;i<N;i++){a[i]=a[i-1]+i;s[i]=s[i-1]+a[i];}int t;cin>>t;while(t--){ll l,r;cin>>l>>r;cout<<persum(r)-persum(l-1)<<endl;}return 0;
}