第十一届蓝桥杯省赛第一场C++A/B组真题

整除序列

有一个序列，序列的第一个数是 $ n $，后面的每个数是前一个数整除 $ 2 $，请输出这个序列中值为正数的项。

输入格式

输入一行包含一个整数 $ n $。

输出格式

输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

数据范围

$ 1 \le n \le 10^{18} $

输入样例：

20

输出样例：

20 10 5 2 1

直接暴力模拟，没啥好说的

#include <bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    cin>>n;
    cout<<n<<" ";
    while (n/2)
    {
        n/=2;
        cout<<n<<" ";
    }
    
    return 0;
}

解码

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。

小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。

例如，连续的 $ 5 $ 个 $ a $，即 $ aaaaa $，小明可以简写成 $ a5 $（也可能简写成 $ a4a \(、\) aa3a $ 等）。

对于这个例子：$ HHHellllloo $，小明可以简写成 $ H3el5o2 $。

为了方便表达，小明不会将连续的超过 $ 9 $ 个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

输入格式

输入一行包含一个字符串。

输出格式

输出一个字符串，表示还原后的串。

数据范围

输入字符串由大小写英文字母和数字组成，长度不超过 $ 100 $。
请注意原来的串长度可能超过 $ 100 $。

输入样例：

H3el5o2

输出样例：

HHHellllloo

也是直接模拟即可

#include <bits/stdc++.h>
using namespace std;
string s,ans;
int main()
{
    cin>>s;
    for (int i=0;i<s.size();i++)
    {
        if (s[i]>='0'&&s[i]<='9')
            for (int j=0;j<s[i]-'0'-1;j++)
                ans+=s[i-1];
        else ans+=s[i];
    }
    
    cout<<ans<<endl;
    return 0;
}

走方格

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 $ 1 $ 至第 $ n $ 行，从左到右依次为第 $ 1 $ 至第 $ m $ 列，每一个点可以用行号和列号来表示。

现在有个人站在第 $ 1 $ 行第 $ 1 $ 列，要走到第 $ n $ 行第 $ m $ 列。

只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

输入格式

输入一行包含两个整数 $ n, m $。

输出格式

输出一个整数，表示答案。

数据范围

$ 1 \le n,m \le 30 $

输入样例1：

3 4

输出样例1：

2

输入样例2：

6 6

输出样例2：

0

经典的摘花生、机器人走方格等\(DP\)问题

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int n,m;
int f[N][N];
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) f[i][1]=1;
    for (int j=1;j<=m;j++) f[1][j]=1;
    
    for (int i=2;i<=n;i++)
        for (int j=2;j<=m;j++)
        {
            if (i%2==0&&j%2==0) continue;
            f[i][j]=f[i-1][j]+f[i][j-1];
        }
    cout<<f[n][m]<<endl;
    return 0;
}

整数拼接

给定一个长度为 $ n $ 的数组 $ A_1, A_2, · · · , A_n $。

你可以从中选出两个数 $ A_i $ 和 $ A_j \((\) i $ 不等于 $ j $)，然后将 $ A_i $ 和 $ A_j $ 一前一后拼成一个新的整数。

例如 $ 12 $ 和 $ 345 $ 可以拼成 $ 12345 $ 或 $ 34512 $。

注意交换 $ A_i $ 和 $ A_j $ 的顺序总是被视为 $ 2 $ 种拼法，即便是 $ A_i = A_j $ 时。

请你计算有多少种拼法满足拼出的整数是 $ K $ 的倍数。

输入格式

第一行包含 $ 2 $ 个整数 $ n $ 和 $ K $。

第二行包含 $ n $ 个整数 $ A_1, A_2, · · · , A_n $。

输出格式

一个整数代表答案。

数据范围

$ 1 \le n \le 10^5 \(, \) 1 \le K \le 10^5 \(, \) 1 \le A_i \le 10^9 $

输入样例：

4 2
1 2 3 4

输出样例：

6

暴力

暴力是比较容易想的，二重循环，每次判断两个数拼接起来是否符合条件即可。显然复杂度达到了\(O(n^2)\)

优化

超时原因就是我们在确定一个数\(A_i\) 后，确定\(A_j\) 时采用了枚举。那么优化就是可以从如何确定答案的方式上想了。

本质上，本题就是求解A[i] 和A[j] 拼接后即(A[i]*10^len(A[j])+A[j])%k==0 ，即符合上述等式的个数。

那么我们稍微移项一下化简为：(A[i]*10^len（A[i）)%k==-A[j]%k

那么此时我们就可以发现，可以哈希记录答案个数了。

因此，创建一个二维数组cnt[i][j]，这个数组就表示(A[j] 10 ^ i)% k == j的数量；
所以本题就转换为每次枚举一个Ai，然后计算出其%k的数来，然后再算出Ai的位数len.
然后去寻找cnt[len][Ai % k]的大小，就能得知有多少个数满足条件，同时也就是答案数。

我们会发现有几个小问题和细节需要处理

• 我们一定要保持逻辑清晰，即首先是只枚举一遍A[i]，先不管对应的A[j] 是什么，对于每个A[i]，都求A[i]*10^(len)%k，并记录结果，其中len是0~10。第二遍枚举A数组，其实是枚举的A[j]，其对于每一个A[j]，我们要看一下cnt[len(A[j])][(-A[j]%k+k)%k] 是多少并累加到答案中去。
• 当然这里我们发现等式的右侧是-A[i]%k 显然会是负数，但我们还是要把这个结果映射为整数才能存在二维数组的第二维中，即答案加上k再Mod k。即(-A[i]%k+k)%k
• 我们会发现上述操作，显然是没有考虑到A[i]和A[j]是不同的数（即\(i \ne j\)）。那么就需要在统计答案的时候，将同时选用A[i]和A[i]的情况去掉。其实并不是很复杂，即最后在统计答案的过程中，对于当前的A[j]，求解一下A[j]*10^len(A[j])%k 是否等于(-A[j]%k+k)%k ，如果等于就说明取的两个数是同一个数，去掉即可。

暴力实现，过4个样例

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n,k;
typedef long long ll;
ll ans;
bool check(int a,int b)  // 判断(a*10*len(b))%k 是否等于 (-b%k+k)%k
{
    int len = to_string(b).size();
    ll t = a%k;
    while (len--)
        t = t*10%k;
    if (t==(-b%k+k)%k)
        return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        {
            if (i==j) continue; // 选择不同的两个数
            if (check(a[i],a[j]))ans++;
        }
    
    printf("%lld\n",ans);
    return 0;
}

哈希记录答案，优化

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int cnt[10][N];
int n,k;
typedef long long ll;
ll ans;
int main()
{
    cin>>n>>k;
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    
    for (int i=0;i<n;i++)
    {
        ll t = a[i]%k;
        for (int j=0;j<10;j++)
        {
            cnt[j][t]++;
            t=t*10%k;
        }
    }
    
    for (int j=0;j<n;j++)
    {
        ll t = a[j]%k;
        int len = to_string(a[j]).size();
        ans+=cnt[len][(-t%k+k)%k];
        
        ll r = t;
        while (len--) r=r*10%k;
        if (r==(-t%k+k)%k) ans--;
    }
    
    printf("%lld\n",ans);
    return 0;
}

总结

• 还是先想朴素的做法，再看超时的原因卡在哪一步
• 这道题感觉就很经典，既然超时因为是我们在判断条件时想同时兼顾到\(A_i\) 和\(A_j\) ，那必然就是\(O(n^2)\) 的复杂度。但是如果先只考虑\(A_i\)，让\(A_i\) 生成全部的可能并用哈希表记录，再只考虑\(A_j\)，看前面生成的哪些是符合条件的。
• 这就非常巧妙地从“同时限制i和j”变成了“先只考虑i”，“再只考虑j的同时，去检查前面的i哪些合法”

网络分析

小明正在做一个网络实验。

他设置了 $ n $ 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。

两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。

所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式

输入的第一行包含两个整数 $ n, m $，分别表示节点数量和操作数量。

节点从 $ 1 $ 至 $ n $ 编号。

接下来 $ m $ 行，每行三个整数，表示一个操作。

• 如果操作为 1 a b，表示将节点 $ a $ 和节点 $ b $ 通过网线连接起来。当 a = b 时，表示连接了一个自环，对网络没有实质影响。
• 如果操作为 2 p t，表示在节点 $ p $ 上发送一条大小为 $ t $ 的信息。

输出格式

输出一行，包含 $ n $ 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 $ 1 $ 至节点 $ n $ 上存储信息的大小。

数据范围

$ 1 \le n \le 10000 \(, \) 1 \le m \le 10^5 \(, \) 1 \le t \le 100 $

输入样例1：

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

输出样例1：

13 13 5 3

并查集高级操作

这道题乍一看和食物链挺像，但我感觉区别还是比较明显的。食物链维护的是当前节点到父节点和根节点的距离，是维护边。

但这个题因为是对于某个节点，只要一发消息，所连通的节点都要收到消息，所以维护的是节点，不是边了。

/*
修改操作：改的时候不是暴力给所有点加，而是给一棵树的根节点作为代表元素加
那么每个节点最终真实的权值=该点到根节点的路径权值之和。
经过路径压缩后，每个节点的最终答案是当前点的权值+根节点的权值

加边的方式：
1、建立一个空的权值为0的节点作为两棵树的新的根节点
2、在一棵树的根节点指向另一棵树的根节点之前，提前把一个树的根节点减去另一个根节点的权值

路径压缩：1、类似食物链那道题。先判断当前节点是否为根节点或者当前节点的父节点是否为根节点。
2、如果是普通的情况，那么我们就需要先更新父节点的情况，即先让父节点指向根节点
因为路径压缩是递归处理，执行晚int root = find(p[x]) 之后，父节点的权值已经更新完毕
而且父节点及其以上的节点都指向了根节点，那么现在就更新当前节点x，先更新权值
即d[x]=d[x]+d[p[x]]，同时让当前节点x指向根节点root。完毕~

*/

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n,m;
int p[N],d[N];

int find(int x)
{
    if (p[x]==x||p[p[x]]==p[x])
        return p[x];
    
    int root = find(p[x]); // 这句执行完，zx的父节点及其以上的节点就完成了压缩过程
    d[x]+=d[p[x]];
    p[x]=root;
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) p[i]=i;
    
    while (m--)
    {
        int op;
        scanf("%d",&op);
        if (op==1)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int pa = find(a);
            int pb = find(b);
            if (pa!=pb)
            {
                d[pa]-=d[pb];
                p[pa]=pb;
            }
        }
        else
        {
            int a,t;
            scanf("%d%d",&a,&t);
            int pa = find(a);
            d[pa]+=t;
        }
    }
    
    for (int i=1;i<=n;i++)
        if (i==find(i)) printf("%d ",d[i]);
        else printf("%d  ",d[i]+d[find(i)]);
    puts("");
    
    return 0;
    
    
    
}

超级胶水

迷惑性极强的问题，石子合并 很像。但仔细分析之后，发现是找规律问题，这也是给我一个警醒，要认真分析，多做数据模拟！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
typedef long long ll;
int main()
{
    ll ans = 0;
    ll sum = 0;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        ans+=sum*x;
        sum+=x;
    }
    
    printf("%lld\n",ans);
    return 0;
}

本栏目推荐文章
• 第十二节：红黑树性质、相对平衡的原理、与AVL树的区别
• 简易机器学习笔记（十一）opencv 简易使用-人脸识别、分类任务
• UCB Data100：数据科学的原理和技巧：第十一章到第十五章
• UCB Data100：数据科学的原理和技巧：第十六章到第二十章
• 初始MQ（十一）
• P8649 [蓝桥杯 2017 省 B] k 倍区间
• Azure Data Factory（十一）Data Flow 的使用解析
• 大话 JavaScript（Speaking JavaScript）：第三十一章到第三十三章
• 大话 JavaScript（Speaking JavaScript）：第十八章到第二十章
• 大话 JavaScript（Speaking JavaScript）：第十一章到第十五章

蓝桥 第十一届 真题 AB蓝桥 第十一届 真题ab 个人赛 蓝桥 第十届 真题 蓝桥p8755 2021 ab2 蓝桥 全球2018 ab 蓝桥 真题 年第 大学 蓝桥8681 2019 ab 个人赛 蓝桥 真题 大学 蓝桥 选拔赛 题库 真题 蓝桥 三国游戏 真题 年第 蓝桥 真题 历年 年第