2024第十五届蓝桥杯 C/C++B组 题解
3. 好数
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ) 上的数字是奇数，偶数位 (十位、千位、十万位) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
样例
24
输出
7
思路1：暴力求解
使用check函数对每个数字每一位进行检查
#include <stdio.h>
int count;
// 暴力揭发
int check(int x)
{
int current = x % 10, currentwei = 1;
while (x > 0)
{
x = x / 10;
if (current % 2 != currentwei % 2)
{
return 0;
}
currentwei++;
current = x % 10;
}
return 1;
}
int n;
int main()
{
int count = 0;
scanf("%d", &n);
for (size_t i = 1; i <= n; i++)
{
if (check(i))
{
count++;
}
}
printf("%d", count);
return 0;
}
思路2：排列组合
对于两位数xx可知如果N为1000那么使用排列组合就可以了
组合为5*5(包含01、03、05这种)
但是这样对于一般情况非常不利。
比如N为9851所以代码实现起来感觉还是比较复杂的。
思路3：三维数组记忆化（也有点三维DP的感觉）
记忆化核心：
memo_cache[pos][tight_int][started_int]
记忆化搜索，避免重复计算。
- 第一维 pos
当前处理的数字位的位置。
(从高位到低位，0表示处理最高位，pos是0开始，而非1开始。也就是说最大值-1表示个位) - 第二维 tight
表示当前数字是否严格受限于
N的对应位。 - 第三维 is_num_started
表示数字是否已经开始构建（是否已经遇到非零数字、或者尝试把当前位修改位非0数）。
- num_str
将输入的数字
N转换为字符串，方便逐位处理。 - length_num
数字
N的位数。（用于检查递归是否应该结束）
递归函数 详细解释
dp(pos, tight, is_num_started)含义：返回在pos位及其更低位
N中数字大小限制下，总共的好数数量
- 递归终止条件:
pos == length_num的时候表明已经递归到个位的下一位，应该返回。is_num_started ? 1 : 0;要求这个数不能全是前导0。- 满足前2个条件，表示已经搜索出了一个合法的
好数，返回1。
- 检查是否已经计算过（利用记忆化）
- 把bool转为int
- 检查
memo_cache[pos][tight_int][started_int];是否为-1，不是，则直接返回之前计算过的结果。
- 没有计算过 ,则对当前位的数字和更低位的数字进行尝试。
- 计算当前位允许的最大数字 和 从个位开始数这是哪一位（用于判断当前位是奇数位还是偶数位）
int limit = tight ? (num_str[pos] - '0') : 9; long long total = 0;// 用于判断奇数位还是偶数位- 遍历当前所有可能的数字并且向低位探索。
for (int d = 0; d <= limit; d++)
循环变量d对于当前位尝试放入数字d。放入后检查：
当前d是否满足当前位奇偶约束如果满足则递归搜索更低的一位。
// 最后的求解过程类似于：
00231（题目给定的N）
|最高位（假设尝试1）
v
00100
|最高位（尝试更低位）
v
001(十位：尝试0~9)(个位：0~9)
|最高位（尝试更低位）
v
00123 （符合条件，返回数量1）
#include <bits/stdc++.h>
using namespace std;
// TODO理解DP
// 使用 memo[pos][tight][is_num_started] 进行记忆化
long long memo_cache[20][2][2];
string num_str;
int length_num;
// 递归函数定义
long long dp(int pos, bool tight, bool is_num_started) {
// 递归终止条件
if (pos == length_num) {
return is_num_started ? 1 : 0;
}
// 检查是否已经计算过
int tight_int = tight ? 1 : 0;
int started_int = is_num_started ? 1 : 0;
if (memo_cache[pos][tight_int][started_int] != -1) {
return memo_cache[pos][tight_int][started_int];
}
// 计算当前位的最大数字
int limit = tight ? (num_str[pos] - '0') : 9;
long long total = 0;
// 计算 digit_pos (位置从右边开始，个位为1)
int digit_pos = length_num - pos;
// 遍历所有可能的数字
for (int d = 0; d <= limit; d++) {
bool next_tight = tight && (d == (num_str[pos] - '0'));
bool next_started = is_num_started || (d != 0);
if (!next_started) {
// 还未开始构建数字，可以选择跳过当前位
total += dp(pos + 1, next_tight, next_started);
}
else {
// 根据当前位的奇偶性限制数字
if (digit_pos % 2 == 1) {
// 奇数位，数字必须是奇数
if (d % 2 == 1) {
total += dp(pos + 1, next_tight, next_started);
}
}
else {
// 偶数位，数字必须是偶数
if (d % 2 == 0) {
total += dp(pos + 1, next_tight, next_started);
}
}
}
}
// 存储结果到 memo
memo_cache[pos][tight_int][started_int] = total;
return total;
}
long long count_good_numbers(long long N) {
// 将 N 转换为字符串
num_str = to_string(N);
length_num = num_str.size();
// 初始化 memo 数组为 -1（表示未计算）
memset(memo_cache, -1, sizeof(memo_cache));
// 开始递归，从第0位，tight为真，尚未开始构建数字
return dp(0, true, false);
}
int main() {
// 示例输入
long long N;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
// 计算并输出“好数”数量
long long result = count_good_numbers(N);
cout<< result << endl;
return 0;
}
4. R格式
TODO
5. 宝石组合
题目如下：
公式化简
看到S的公式这么对称完美，首先想到能不能化简
使用a*b=GCD(a，b)*LCM(a，b)。可把最后的精美程度
S化简为S=gcd(a,b,c)
求解
要求：
求最大S = gcd(a, b, c)优先选择按照H值升序排列后字典序最小的方案。
那么最大gcd该怎么求呢。
仔细审题发现Hi<=1e5说明gcd<=1e5，这暗示我们可以直接枚举gcd找到最大的那个。
这里有个问题，为了求出最大的gcd我们得把每个gcd for gcd in H(N)[::-1]和每个数相除当出现有三个数能除尽的时候说明我们找到了最大gcd。但是为了快速找到gcd的整数倍是否存在对应的数。考虑把使用频率数组（就是hash的思想）每个数作为下标，这样就能随机读取了。
步骤：
- 读取宝石，按照H值升序排列得出数组
H(N) - 取出排序好后的
H(N)的最大值 - 构建频率数组。
max_gcd初始化为1，count初始化为0- 循环遍历
g设置为max(H(N))，逐渐递减。 - 把
g和每个数相除。 - count==3的时候赋值
g给max_gcd，break - 重复4~6
- 再拿max_gcd从大往小去除每个数，除尽就输出。输出3个数。
6. 数字接龙
题目如下：
这道题似乎就是DFS
就直接给简单的官方题解得了
#include<bits/stdc++.h>
using namespace std;
int n, k;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
vector<vector<int>> g(12, vector<int>(12, -1));
vector<vector<bool>> st(12, vector<bool>(12, 1));
bool edge[12][12][12][12]; // edge[x][y][i][j] 表示有一条从 (x,y) -> (i,j) 的边
bool dfs(int x, int y, string sum, int step)
{
if(step == n * n && x == n && y == n)
{
cout<<sum<<endl;
return true; // 遇到答案就输出，然后立刻返回
}
for(int i = 0; i < 8; i++) // 由于按顺序遍历，所以确保了答案一定是按照字典序排布的
{
int tx = x + dx[i], ty = y + dy[i];
if(st[tx][ty] == 1) // 重复路径
continue;
if(g[tx][ty] == (g[x][y] + 1) % k) // k 顺序
{
// if(i % 2 && st[x][ty] && st[tx][y]) 败笔
// continue;
if(edge[x][ty][tx][y] || edge[tx][y][x][ty]) // 对角判断
continue;
edge[x][y][tx][ty] = 1;
st[tx][ty] = 1;
if(dfs(tx, ty, sum + (char)('0' + i), step + 1))
return 1;
st[tx][ty] = 0;
edge[x][y][tx][ty] = 0;
}
}
return 0;
}
int main()
{
n = 0, k = 0;
cin>>n>>k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
cin>>g[i][j];
st[i][j] = 0;
}
st[1][1] = 1;
if(!dfs(1, 1, "", 1))
cout<<-1<<endl;
return 0;
}
7. 拔河
题目:
错误的解题思路
一开始没注意编号必须连续。所以以为是0-1背包问题。
就是求一个子集和最接近sum(a(i)) / 2，但是这样肯定不行。
既然要连续，那肯定考的是前缀和。
所以解题思路：
- 构造前缀和数组
- 遍历每一个
下标连着的子集然后得把每一个结果保存下来，找到最接近的两个。 - 根据
2.的分析set的特性非常满足我们的需要。如果有重复的插入会出错，那么直接打印0就行了。如果没有出错，由于set是有序的，那么只要遍历相邻两个元素，找出最小差值就行了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4;
ll a[N];
set<ll> s;//存放所有区间的力量值
int n;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
ll ans=1e9;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(s.find(a[j]-a[i-1])==s.end())s.insert(a[j]-a[i-1]);
else{
cout<<0;
return 0;
}
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=i;j++){
auto t=a[i]-a[j-1];
auto p=*s.lower_bound(t+1);
ans=min(ans,abs(t-p));
}
}
cout<<ans;
return 0;
}