[关闭]
@guxier 2022-04-10T10:01:40.000000Z 字数 3637 阅读 613

第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

蓝桥杯

试题 A: 九进制转十进制

本题总分：5 分

【问题描述】

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

【本题答案】

1478

C++代码

  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     string n = "2022";
  6.     int ans;
  7.     ans = (n[0] - '0') * 9;
  8.     ans = (n[1] - '0' + ans) * 9;
  9.     ans = (n[2] - '0' + ans) * 9;
  10.     ans = (n[3] - '0' + ans);
  12.     cout << ans;
  13.     return 0;
  14. }

试题 B: 顺子日期

本题总分：5 分

【问题描述】

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

【本题答案】

14

C++代码

试题 E: X 进制减法

时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】

进制规定了数字在数位上逢几进一。
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 的结果。

【样例输入】

  1. 11
  2. 3
  3. 10 4 0
  4. 3
  5. 1 2 0

【样例输出】

  1. 94

【样例说明】

当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

【评测用例规模与约定】

对于 30% 的数据，
对于 100% 的数据，.

贪心

差值最小，必要前提是 a，b的每位数的进制最低。
取进制最低方法即为：第i位的进制=a和b第i位数字最大值+1。（若a，b都=0，即取2进制）

C++代码

  1. #include <bits/stdc++.h>
  2. #define rep(i, a, n) for ( int i = a; i <= n; i++)
  3. #define per(i, a, n) for ( int i = n; i >= a; i--)
  4. #define debug(x) cout << #x << ": " << x << endl
  5. #define MOD 1000000007
  6. using namespace std;
  7. /*=====================Guxier=====================*/
  8. const int N = 1e5 + 10;
  9. int n ;
  10. int a[N] , b[N];
  11. int p[N];   //用来存放每个数位的进制 
  13. int main()
  14. {
  15.     cin >> n;
  16.     int ma;
  17.     cin >> ma;
  18.     rep(i , 1, ma) cin >> a[i], p[i] = max(a[i] + 1, 2); 
  19.     int mb;
  20.     cin >> mb;
  21.     rep(i , 1, mb) cin >> b[i], p[i] = max(b[i] + 1, p[i]);
  23.     rep(i , 1 , ma-1)
  24.         a[i+1] += (a[i] - b[i]) *p[i+1];
  26.     cout << a[ma] % MOD;
  28.     return 0;
  29. }

试题 I: 李白打酒加强版

本题总分：25 分

【问题描述】

话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

【输入格式】

第一行包含两个整数 N 和 M.

【输出格式】

输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。

【样例输入】

  1. 5 10

【样例输出】

  1. 14

【样例说明】

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

  1. 010101101000000
  2. 010110010010000
  3. 011000110010000
  4. 100010110010000
  5. 011001000110000
  6. 100011000110000
  7. 100100010110000
  8. 010110100000100
  9. 011001001000100
  10. 100011001000100
  11. 100100011000100
  12. 011010000010100
  13. 100100100010100
  14. 101000001010100

【评测用例规模与约定】

对于 40% 的评测用例：1 ≤ N, M ≤ 10。
对于 100% 的评测用例：1 ≤ N, M ≤ 100。

DFS

深搜没啥好说的，枚举每种情况，排除所有不合法的情况进行剪枝
有以下三种情况：
1. 花、店的数目超过总量
2. 酒的余量为负数
3. 最后一个位置遇到的不是花，或最后一个位置遇到花后酒的余量还不为0

  1. #include <bits/stdc++.h>
  2. #define rep(i, a, n) for ( int i = a; i <= n; i++)
  3. #define per(i, a, n) for ( int i = n; i >= a; i--)
  4. #define debug(x) cout << #x << ": " << x << endl
  5. #define MOD 1000000007
  6. using namespace std;
  7. typedef long long LL;
  8. /*=====================Guxier=====================*/
  9. const int N = 110;
  10. LL n , m , ans , len;
  11. LL t[N];    //用来记录李白路过花和店的序列 
  13. void dfs(int i, LL k, LL a, LL b)
  14. {
  15.     if(a > m || b > n) return;//花、店的数目超过总量 
  17.     if(i == len-1)  //最后一个必为花，且酒的余量为0 
  18.     {
  19.         if(k == 1 && a == m-1 && b == n)
  20.         {
  21.             //rep(j , 1, len) cout << t[j];
  22.             //cout << endl; 
  23.             ans++;
  24.         }
  25.         return;
  26.     }
  27.     if(k <= 0) return;  //酒余量不能为负 
  29.     //a是遇到的花的数目 b是遇到店的数目 
  30.     //t[i] = 0; 
  31.     dfs(i+1, k-1 , a+1 , b);
  32.     //t[i] = 1;
  33.     dfs(i+1, k+k , a , b+1);
  34. }
  36. int main()
  37. {
  38.     cin >> n >> m;
  39.     len = n + m;
  40.     dfs(0 , 2 , 0 , 0);
  41.     ans = ans % MOD;
  42.     cout << ans;
  44.     return 0;
  45. }

DP

dp[i][j][k] 表示为前i次 有j次遇到店 剩下酒为k斗
因为n,m最大值为100，因此当k>100之后，该情况必然不合法

  1. #include <bits/stdc++.h>
  2. #define rep(i, a, n) for ( int i = a; i <= n; i++)
  3. #define per(i, a, n) for ( int i = n; i >= a; i--)
  4. #define debug(x) cout << #x << ": " << x << endl
  5. #define MOD 1000000007
  6. using namespace std;
  7. typedef long long LL;
  8. /*=====================Guxier=====================*/
  9. const int N = 210;
  10. LL n , m , ans , len;   
  11. LL dp[N][N][N];     //前i次 有j次遇到店 剩下酒为k斗 
  14. int main()
  15. {
  16.     cin >> n >> m;      //N店  M花 
  17.     len = n + m;
  19.     dp[0][0][2] = 1;    //  李白初始有2 斗酒 
  21.     rep(i , 1 , len)    
  22.         rep(j , 0 , n)
  23.             rep(k , 0 , 100)
  24.             {
  25.                 dp[i][j][k] += dp[i-1][j][k+1]; //遇到花 
  27.                 if(j && k % 2 == 0)             //遇到店 
  28.                     dp[i][j][k] += dp[i-1][j-1][k/2];
  30.                 dp[i][j][k] %= MOD;             //答案取模
  31.             }
  33.     dp[len][n][0] = dp[len-1][n][1];    //最后遇到的一个一定是花 
  34.     cout << dp[len][n][0];
  36.     return 0;
  37. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注