第十一届蓝桥杯国赛C++大学B组

一、美丽的2

问题描述

小蓝特别喜欢2，今年是2020年，他特别高兴。
他很好奇，在公元1年到公元2020年（包含）中，有多少年份的位数中包含数字2？

答案

563

Code

#include<iostream>
using namespace std;

bool check(int x)
{
    while(x)
    {
        if(x % 10 == 2) return true;
        x /= 10;
    }
    return false;
}

int main()
{
    int ans = 0;
    for(int i = 1;i <= 2020;i ++)
        ans += check(i);

    cout<<ans<<endl;
    return 0;
}

二、扩散

问题描述

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

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

小蓝在画布上首先点了一下几个点：(0, 0)，(2020, 11)，(11, 14)，(2000, 2000)

只有这几个格子上有黑色，其它位置都是白色的，每过一分钟，黑色就会扩散一点。

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

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

答案

20312088

Code

#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 6500;
const int M = 2020; //偏移量 
int dist[N][N];
bool st[N][N];
int ans = 4;    //初始时有4个黑点 

void bfs()
{
    int cnt = 0;
    q.push({0 + M,0 + M});
    q.push({2020 + M,11 + M});
    q.push({11 + M,14 + M});
    q.push({2000 + M,2000 + M});
    st[0 + M][0 + M] = true;
    st[2020 + M][11 + M] = true;
    st[11 + M][14 + M] = true;
    st[2000 + M][2000 + M] = true;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while(q.size())
    {
        PII t = q.front();
        q.pop();

        if(dist[t.x][t.y] >= 2020) return;

        for(int i = 0;i < 4;i ++)
        {
            int a = t.x + dx[i],b = t.y + dy[i];
            if(a < 0 || a > 6100 || b < 0 || b > 6100) continue;
            if(st[a][b]) continue;
            if(dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            st[a][b] = true;
            q.push({a,b});
            ans ++;
        }
    }
}

int main()
{
    memset(dist,-1,sizeof dist);
    dist[0 + M][0 + M] = 0;
    dist[2020 + M][11 + M] = 0;
    dist[11 + M][14 + M] = 0;
    dist[2000 + M][2000 + M] = 0;

    bfs();
    cout<<ans<<endl;
    return 0;
}

三、阶乘约数

相同题目： 约数个数

问题描述

定义阶乘 n! = 1 × 2 × 3 × ··· × n。

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

数论

任意一个正整数 X 都可以表示成若干个质数乘积的形式，即 $X = p_1^a1 * p_2^a2 * …… *p_k^ak$

约数个数 = $(a1 + 1)(a2 + 1)……(ak + 1)$

答案

39001250856960000

Code

#include<iostream>
#include <unordered_map>
using namespace std;

unordered_map<int,int> primes;

int main()
{
    for(int i = 1;i <= 100;i ++)
    {
        int x = i;
        for(int j = 2;j <= x / j;j ++)
            while(x % j == 0)   //while不要错写为if
            {
                primes[j] ++;
                x /= j;
            }
        if(x > 1) primes[x] ++;
    }

    long long cnt = 1;
    for(auto q : primes) cnt = cnt * (q.second + 1);  

    cout<<cnt<<endl;
    return 0;
}

四、本质上升序列

问题描述

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

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

例如，在字符串 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、lnq、anq、lno、ano、aio。

请问对于以下字符串（共 200 个小写英文字母，分两行显示）：

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个？

答案

3616159

Code

#include<iostream>
#include<iostream>
using namespace std;

int f[210];

int main()
{
    string s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";

    for(int i = 0;i < 200;i ++) f[i] = 1;

    for(int i = 0;i < 200;i ++)
        for(int j = 0;j < i;j ++)
        {
            if(s[i] > s[j]) f[i] += f[j];
            if(s[i] == s[j]) f[i] -= f[j];
        }

    int ans = 0;    
    for(int i = 0;i < 200;i ++) ans += f[i];

    cout<<ans<<endl;
    return 0;
}

五、玩具蛇

问题描述

小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。

小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为时不同的方案。

答案

552

Code

#include<iostream>
#include<cstring>
using namespace std;

int g[5][5];
int st[5][5];
int ans = 0;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x,int y,int u)
{
    if(u == 15)
    {
        ans ++;
        return;
    }

    for(int i = 0;i < 4;i ++)
    {
        int a = x + dx[i],b = y + dy[i];
        if(a < 0 || a >= 4 || b < 0 || b >= 4) continue;
        if(st[a][b]) continue;

        st[a][b] = 1;
        dfs(a,b,u + 1);
        st[a][b] = 0;
    }


}

int main()
{
    for(int i = 0;i < 4;i ++)
        for(int j = 0;j < 4;j ++)
        {
            st[i][j] = 1;
            dfs(i,j,0);
            memset(st, 0, sizeof st);
        }   

    cout<<ans<<endl;
    return 0;
}

六、皮亚诺曲线距离

七、游园安排

问题描述

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。

小蓝是 L 星球游乐园的管理员，为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。

每个游客的名字由一个大写英文字母开始，后面跟 0个或多个小写英文字母，游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，

在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 A 小于另一个名字 B 是指：

存在一个整数 i ，使得 A 的前 i 个字母与 B 的前 i 个字母相同，且 A 的第 i + 1个字母小于 B 的第 i + 1 个字母
如果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A AA 的第 i + 1 个字母小于 B 的第 i + 1 个字母
作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。

如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。

如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。

如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

输入格式

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

输出格式

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

样例输入

WoAiLanQiaoBei

样例输出

AiLanQiao

数据范围

对于 20% 的评测数据，输入的总长度不超过 20 个字母。
对于 50% 的评测数据，输入的总长度不超过 300 个字母。
对于 70% 的评测数据，输入的总长度不超过 10000 个字母。
对于所有评测数据，每个名字的长度不超过 10 个字母，输入的总长度不超过 1000000 个字母。

Code（过70%数据）

#include<iostream>
#include<vector>
#include<string>
using namespace std;

const int N = 1e5 + 10;
vector<string> q;
int len[N];
string f[N];

int main()
{
    string s;
    cin>>s;

    for(int i = 0;i < s.size();i ++)
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            int j = i + 1;
            while(s[j] >= 'a' && s[i] <= 'z') j ++;
            q.push_back(s.substr(i,j - i ));
        }

    for(int i = 0;i < q.size();i ++)    //初始化
    {
        len[i] = 1;
        f[i] = q[i];
    }

    for(int i = 0;i < q.size();i ++)
        for(int j = 0;j < i;j ++)
            if(q[i] > q[j])
                if(len[j] + 1 > len[i])
                {
                    len[i] = len[j] + 1;
                    f[i] = f[j] + q[i];
                }
                else if(len[j] + 1 == len[i])   //注意else if不能写成if
                {
                    len[i] = len[j];
                    f[i] = min(f[i],f[j] + q[i]);
                }

    string ans;
    int maxv = 0;
    for(int i = 0;i < q.size();i ++)
        if(maxv <= len[i]) maxv = len[i],ans = f[i];    //长度相同时后者为答案

    cout<<ans<<endl;
    return 0;
}

八、答疑

问题描述

有 n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下：

1. 首先进入办公室，编号为 i的同学需要 si毫秒的时间。
2. 然后同学问问题老师解答，编号为 i的同学需要 ai毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 ei毫秒的时间。一般需要 10秒、20秒或 30秒，即 ei取值为 10000，20000 或 30000 。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。

输入格式

输入第一行包含一个整数 n，表示同学的数量。
接下来 n行，描述每位同学的时间，其中第 i 行包含三个整数 s i , a i , e i ，意义如上所述。

输出格式

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

样例输入

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

样例输出

280000

样例说明

按照 1 , 3 , 2 的顺序答疑，发消息的时间分别是 20000 , 80000 , 180000

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
int q[1010][5];
vector<PII> p;
long long ans;

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i ++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        q[i][0] = a,q[i][1] = b,q[i][2] = c;
        p.push_back({a + b + c,i});
    }

    sort(p.begin(),p.end());

    int res = 0;
    for(int i = 0;i < p.size();i ++)
    {
        int cnt = 0;
        cnt = q[p[i].second][0] + q[p[i].second][1];
        ans += res + cnt;
        res += cnt + q[p[i].second][2];
    }

    cout<<ans<<endl;

    return 0;
}