第十一届蓝桥杯大赛决赛赛题 C++ 大学C组

试题A：美丽的2 问题描述

  小蓝特别喜欢2，今年是公元2020年，他特别高兴。

  他很好奇，在公元1年到公元2020年（包含）中，有多少个年份的数位中包含数字2？

算法设计

• 遍历1~2020，如果位数中含有2，则计数器加1，且跳出。
  

  
  

#include 
using namespace std;
int main(){
    int count = 0;
    for (int i = 1; i <= 2020; ++i) {
        int temp = i;
        while(temp){
            int x = temp % 10;
            temp = temp/10;
            if(x == 2){
                count++;
                break;
            }
        }
    }
    cout << count << endl;
    return 0;
}

输出：

563

试题B：合数个数 问题描述

  一个数如果除了1和自己还有其他约数，则称为一个合数。

例如：1、2、3不是合数，4、6是合数。

  请问从1到2020一共有多少个合数。

算法设计

• 合数即为非质数，使用欧拉线性筛筛选出素数，将非素数计数即可。
  

  
  

#include 
using namespace std;
int main(){
    int n = 2020;
    int pri[n+1];
    bool number[n+1];
    memset(pri,0,sizeof(pri));
    memset(number,true,sizeof(number));
    int temp = 0;
    for (int i = 2; i <= n; ++i) {
        if(number[i]){
            pri[temp++] = i;
        }
        for (int j = 0; j < temp && pri[j] * i <= n; ++j) {
            number[pri[j] * i] = false;
            if(i % pri[j] == 0){
                break;
            }
        }
    }
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if(!number[i]){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

输出：

1713

试题C：扩散 问题描述

  小蓝在一张无限大的特殊画布上作画。

  这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

  小蓝在画布上首先点了一下几个点（0,0）、（2020,11）、（11,14）、（2000,2000）。

只有这几个格子上有黑色，其他位置都是白色的。

  每过一分钟，黑色就会扩散一点。

具体的，如果一个格子里面全是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。

  请问，经过2020分钟后，画布上有多少个格子是黑色的。

算法设计

• 暴力求解很容易爆内存，所以选用BFS（广度优先搜索）算法是一种方法。
  

  
  

#include
using namespace std;
const int maxn = 10000;
int ans = 4; //已经存在4个黑点
bool vst[maxn][maxn]; //访问标记
int dir[4][2] = {0,1,0,-1,1,0,-1,0}; //方向向量
struct State{
    int x,y; //坐标位置
    int step; //搜索步数统计器
};
bool check(State s); //约束条件检验函数
void bfs(); //广度优先搜索
int main(){
    memset(vst,false,sizeof(vst)); //标记数组初始化
    bfs();
    cout << ans << endl;
    return 0;
}
bool check(State s){
    if(!vst[s.x][s.y] && s.step<=2020){ //坐标未被访问，且步数（即时间）小于等于2020
        return true;
    }
    return false;
}

void bfs(){
    queue<State> q; //BFS队列
    State now,next; //当前状态，下一个状态
    vst[3000][3000]=vst[5020][3011]=vst[3011][3014]=vst[5000][5000]=true;
    next.x=3000,next.y=3000,next.step=0;
    q.push(next);
    next.x=5020,next.y=3011,next.step=0;
    q.push(next);
    next.x=3011,next.y=3014,next.step=0;
    q.push(next);
    next.x=5000,next.y=5000,next.step=0;
    q.push(next);
    while(!q.empty()){
        now = q.front();
        for (int i = 0; i < 4; ++i) {
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];
            next.step = now.step+1;
            if(check(next)){
                q.push(next);
                vst[next.x][next.y] = true; //标记访问
                ans++;
            }
        }
        q.pop(); //出队
    }
}

输出：

20312088

试题D：阶乘约数 问题描述

  定义阶乘 n ! = 1 × 2 × 3 × . . . × n n! = 1 \times 2 \times 3 \times ... \times n n!=1×2×3×...×n。

  请问 100 ! 100! 100!（100的阶乘）有多少个正约数。

算法设计

• 将1~100中非质数做质因数分解。
  

  
  

#include 
using namespace std;
typedef long long LL;
const int N = 1024;
int n;
int p[N];
int main()
{
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int a = i;
        for (int j = 2; j <= a / j; ++j) {
            if (a % j == 0) {
                while (a % j == 0) {
                    p[j]++;
                    a /= j;
                }
            }
        }
        if (a > 1) p[a]++;
    }
    // 溢出风险
    LL res = 1;
    for (int i = 2; i <= n; ++i) {
        if (p[i] > 0) {
            res = res * (p[i] + 1);
        }
    }
    cout << res << endl;
    return 0;
}

输入：

10

输出：

39001250856960000

试题E：本质上升序列 问题描述

  小蓝特别喜欢单调递增的事物。

  在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

  例如，在字符串lanqiao中，如果取出字符n和q，则nq组成一个单调递增子序列。

类似的单调递增子序列还有lnq、i、ano等等。

  小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取代ao，取最后两个字符也可以取到ao。

小蓝认为他们并没有本质不同。

  对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？
  例如，对于字符串lanqiao，本质不同的递增子序列有21个。

它们分别是l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lng、anq、lno、ano、aio。

算法设计

• 对于相同的字符我们只需计算最左边第一次出现的值即可，第一次出现的值一定包括后面出现的情况。
  

  
  

  。
  

  
  

• 使用动态规划求解（参考）

#include 
using namespace std;
typedef long long ll;
const int maxn=200+10;
char s[maxn];
int dp[maxn];
map<int,int> book,tb;
map<char,int> book2,tb2;

int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        if(!book2[s[i]])
        {
            book2[s[i]]=1;
            book[i]=1;
        }
    }
    for(int i=1;i<=n;i++) dp[i]=1;
    for(int i=n-1;i>=1;i--)
    {
        tb.clear(),tb2.clear();
        for(int j=i+1;j<=n;j++)
        {
            if(!tb2[s[j]])
            {
                tb2[s[j]]=1;
                tb[j]=1;
            }
            if(s[i]<s[j] && tb[j]) dp[i]+=dp[j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!book[i]) continue;
        ans+=dp[i];
    }
    cout << ans << endl;
}