第十三届蓝桥杯（C/C++ 大学B组）

目录

试题 A: 九进制转十进制

试题 B: 顺子日期

试题 C: 刷题统计

试题 D: 修剪灌木

试题 E: X 进制减法

试题 F: 统计子矩阵

试题 G: 积木画

试题 H: 扫雷

试题  I: 李白打酒加强版

试题 J: 砍竹子

---

试题 A: 九进制转十进制

九进制正整数 ( 2022 )转换成十进制等于多少？

#include <bits/stdc++.h>
using namespace std;int main()
{int c, ans = 0;while (c = getchar(), '0' <= c && c <= '9')ans = ans * 9 + c - '0';cout<<ans<<endl; //1478return 0;
}

试题 B: 顺子日期

小明特别喜欢顺子。顺子指的就是连续的三个数字： 123 、 456 等。顺子日期指的就是在日期的 yyyymmdd表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；而 20221023则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期。

#include <bits/stdc++.h>using namespace std;
int date1[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};    //确定2022年的每月的天数
int main()
{int b[8];                              //b[0]到b[4]表示的是2022年b[0] = 2;b[1] = 0;        b[2] = 2;b[3] = 2;int sum = 0;for (int i = 1; i <= 12; i++)         //从一月到12月{b[4] = i / 10;                //月数的高位b[5] = i % 10;                //月数的低位for (int j = 1; j <= date1[i]; j++)   //从每月的第一天到最后一天{b[6] = j / 10;                //表示天数的高位b[7] = j % 10;                //表示天数的低位if ((b[4] + 1 == b[5] && b[5] + 1 == b[6]) || (b[5] + 1 == b[6] && b[6] + 1 == b[7]))  //如果是顺子日期就+1{sum++;}}}cout << sum << endl;return 0;
}

试题 C: 刷题统计

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a道题目，周六和周日每天做 b道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n题？

输入格式：输入一行包含三个整数a，b和n。

输出格式：输出一个整数代表天数。

样例输入：10 20 99

样例输出：8

#include <bits/stdc++.h>
using namespace std;int main()
{long long a,b,n,ans;cin>>a>>b>>n; ans = n / (5 * a + 2 * b) * 7;n %= 5 * a + 2 * b;if (n > 5 * a)ans += 5 + ((n - 5 * a) + b - 1) / b;elseans += (n + a - 1) / a;cout<<ans<<endl;return 0;
}

试题 D: 修剪灌木

爱丽丝要完成一项修剪灌木的工作。

  有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0  厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

  灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式：一个正整数N，含义如题面所述。

输出格式：输出N行，每行一个整数，表示从左到右第i棵树最高能长到多高。

样例输入：3

样例输出：

4

2

4

#include <bits/stdc++.h>
using namespace std;int n,a[10005];int main()
{int n;cin>>n;for(int i = 1;i <= n;i++){cout<<max(2*(i-1),2*(n-i))<<endl;}return 0;
}

试题 E: X 进制减法

进制规定了数字在数位上逢几进一。

  X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X进制数 321 转换为十进制数为 65 。

  现在有两个 X 进制表示的整数 A 和 B ，但是其具体每一数位的进制还不确定，只知道 A  和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

输入格式：

第一行一个正整数N，含义如题面所述。

第二行一个正整数Ma，表示x进制数A的位数。

第三行Ma个用空格分开的整数，表示x进制数A按从高位到低位顺序各个数位上的数字在十进制下的表示。

第四行一个正整数Mb，表示x进制数B的位数。

第五行Mb个用空格分开的整数，表示x进制数B按从高位到低位顺序各个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

输出格式：

输出一行一个整数，表示x进制数A-B的结果的最小可能值转换为十进制后再模1000000007的结果。

样例输入：

11
3
10 4 0
3
1 2 0

样例输出：

94

#include <bits/stdc++.h>
using namespace std;const int vinf = 100010;
const int mod = 1000000007;
typedef long long ll;
int a[vinf],b[vinf];
int weights[vinf];	//单个位数上的权值 
ll ans; int main()
{/*例如：3 的进制为8，2的进制为10，1的进制为23 2  18 10 2			1 + 2 * 2 + 3 * 10 * 2 = 6510 4 011 5 2			0 + 4 * 2 + 10 * 5 * 2 = 108当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。*/int N;	//最大进制数cin>>N;int na,nb;cin>>na;for(int i = na;i >= 1;i--) //从高位开始输入 cin>>a[i];cin>>nb;for(int i = nb; i >= 1;i--)cin>>b[i]; //选取位数多的int max_num = max(na,nb);	//计算每一位上的权值for(int i = 1;i <= max_num;i++)weights[i] = max(max(a[i], b[i]) + 1, 2);//计算两个数字的按权展开的和ll A = 0, B = 0;for(int i = na;i >= 1;i--)A = (A * weights[i] + a[i]) % mod;for(int i = nb;i >= 1;i--)B = (B * weights[i] + b[i]) % mod;	ans = (A - B) % mod;cout<<ans<<endl;return 0;
}

试题 F: 统计子矩阵

给定一个N*M的矩阵A，请你统计有多少个子矩阵（最小1*1，最大N*M）满足子矩阵中所有数的和不超过给定的整数K？

输入格式：

第一行包含三个整数N，M和K。

之后N行每行包含M个整数，代表矩阵A。

输出格式：

一个整数代表答案。

样例输入：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

19

#include <bits/stdc++.h>
using namespace std;const int MAX = 501;
typedef long long ll;
int area[MAX][MAX];
ll ans = 0;int main()
{int n,m,k;cin>>n>>m>>k;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin>>area[i][j];area[i][j] += area[i-1][j]; //前缀和 }}//滑动窗口算法for(int start = 1;start <= n;start++) //起始行 {for(int end = start;end <= n;end++) //最终行 {//滑动窗口的边界 int l = 1,r = 1,sum = 0;for(;r <= m;r++){//扩大窗口 sum += area[end][r] - area[start - 1][r];while(sum > k){//缩小窗口 sum -= area[end][l] - area[start - 1][l];//左边界右移 l++;}//算数 ans += r - l + 1;}}}cout<<ans<<endl;return 0;
}

试题 G: 积木画

样例输入：

3

样例输出：

5

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int mod = 1e9+7;
const int m = 10000000;
int f[m][3];
ll n;int main()
{cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);//设f[i][0]表示当前拼完了前i列的方案数，//f[i][1]表示当前拼完了前i-1列，且第i列拼完了上面方格的方案数，//f[i][2]表示当前拼完了前i-1列，且当前第i列拼完了下面方格的方案数。f[0][0] = 1;cin>>n;for(int i = 1;i <= n;i++){f[i][0] = (f[i-1][0] + f[i-1][1] + f[i-1][2]) % mod;if(i >= 2){f[i][0] = (f[i][0] + f[i-2][0]) % mod;f[i][1] = (f[i-1][2] + f[i-2][0]) % mod;f[i][2] = (f[i-1][1] + f[i-2][0]) % mod;}}cout<<f[n][0];return 0;
}

试题 H: 扫雷

样例输入：

2 1
2 2 4
4 4 2
0 0 5

样例输出：

2

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int M = 999997;
const ll Base = 1e9 + 7;
int hash[M];	//哈希值，用于维护find函数 
int num[M];	//当前位置有多少个炸弹 
int radius[M];	//当前位置的半径 
int visited[M];	//是否访问过 
int res;//降维
ll get_key(int x,int y)
{return x * Base + y;
}
//哈希函数
int find(int x)
{int t = (x % M + M) % M;while(hash[t] != -1 && hash[t] != x){t++;while(t == M) t = 0;}return t;
} 
//判断是否在范围内
bool judge(int x,int y,int r,int x2,int y2)
{int d = (x2 - x) * (x2 - x) + (y2 - y) * (y2 - y);return d <= r * r;
} void dfs(int x,int y,int r)
{for(int i = -r;i <= r;i++){for(int j = -r;j <= r;j++){int dx = x + i;int dy = y + j;int k = get_key(dx,dy);int t = find(k);while(hash[t] && judge(x,y,r,dx,dy) && !visited[t]){res += num[t];			//答案加上该点地雷个数visited[t] = 1;dfs(dx,dy,radius[t]);	//搜索下一个点}}}
}int main()
{cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);int n,m;cin>>n>>m;memset(hash,-1,sizeof hash);for(int i = 0;i < n;i++){int x,y,r;cin>>x>>y>>r;int k = get_key(x,y);int t = find(k);hash[t] = k;num[t]++;		 //统计该点地雷数量radius[t] = max(r,radius[t]);	//记录该点地雷半径的最大值}for(int i = 0;i < m;i++){int x,y,r;cin>>x>>y>>r;dfs(x,y,r);	//从每一个排雷火箭引爆点开始dfs}cout<<res;return 0;
}

试题  I: 李白打酒加强版

样例输入：

5 10

样例输出：

14

#include <bits/stdc++.h>
using namespace std;int mod = 1e9 + 7;
int dp[101][101][101];int main()
{cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);int n,m;cin>>n>>m;dp[0][0][2] = 1;for(int i = 0;i <= n;i++)for(int j = 0;j <= m;j++)for(int k = 0;k <= m;k++){//遇到花if(j && k) dp[i][j][k] = (dp[i][j][k] + dp[i][j-1][k+1]) % mod;//遇到店 if(i && k % 2 == 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k/2]) % mod;}//最后一次需要是花 cout<<dp[n][m-1][1];return 0;
}

试题 J: 砍竹子

样例输入：

6
2 1 4 2 6 7

样例输出：

5

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
struct Node
{ll h;int idx;bool operator <(const Node &rhs) const{if(h == rhs.h) return idx > rhs.idx; //索引升序 return h < rhs.h; //高度降序 }
};
priority_queue<Node> q;
int ans;int main()
{cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);int n,h;cin>>n;for(int i = 1;i <= n;i++) {cin>>h;q.push((Node){h,i});}while(!q.empty()){Node node = q.top();q.pop();if(node.h == 1) continue;while(!q.empty() && q.top().h == node.h && q.top().idx == node.idx + 1){node.idx = q.top().idx;q.pop();}node.h = sqrtl(node.h / 2 + 1);if(node.h > 1) q.push(node);ans++;}cout<<ans;return 0;
}