第十一届蓝桥杯省赛第一场C++AB组真题题解

整除序列题目描述：

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

思路：

模拟就行

#includeusing namespace std;typedef long long ll;int main(){ll n; cin >> n;while(n){cout << n << ' ';n /= 2;}cout << endl;return 0;}

解码题目描述：

给出缩写后的字符串，让你还原回去，缩写的方式是将一段长度小于10的相同的字符串缩写成一个字符+一个数字的形式

思路：

模拟就行

#includeusing namespace std;typedef long long ll;int main(){string s;cin >> s;for(int i = 0; i < s.size(); ++i){if(s[i] >= '0' && s[i] <= '9'){int p = s[i] - '1';while(p>0)cout<[i-1], --p;}else cout<[i];}return 0;}

走方格题目描述：

二维矩阵，你在(1, 1)问到(n, m)的路线的数量，其中不能走横纵坐标都是偶数的点

思路：

最简单的dp计数

#include using namespace std;#define endl '\n'#define inf 0x3f3f3f3f#define mod 1000000007#define m_p(a,b) make_pair(a, b)#define mem(a,b) memset((a),(b),sizeof(a))#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";typedef long long ll;typedef pair  pii;#define MAX 300000 + 50int n, m, k;int tr[MAX];int dp[50][50];void work(){cin >> n >> m;dp[1][1] = 1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){if(i % 2 == 0 && j % 2 == 0)continue;dp[i][j] += dp[i - 1][j] + dp[i][j - 1];}}cout << dp[n][m] << endl;}int main(){io;work();return 0;}

整数拼接题目描述：

给定长度为n的数组a[i] ，你可以从中选择出两个数a[i], a[j](i != j) ，将其一前一后拼在一起形成一个新的数字，例如：12和345可以拼接出12345或者34512 ，问存在多少种拼接方法，使的拼接出来的数是k的倍数

思路：

很有意思的一个题
我们将在前面的数字叫做a, 将后面的数字叫做b
拼接得到的数字可以被拆成两部分：a?10log10b+1a*10^{log_{10}{b}+1}a?10log10?b+1和bbb两部分
我们先考虑每个数a[j]作为b的情况，假设p=10log10b+1p=10^{log_{10}{b}+1}p=10log10?b+1,则我们需要求1到j-1中出现的数a[i] ，能满足(a[i]*p) % k + a[j] % k) %k = 0,也就是(a[i]*p) % k = k - a[j] % k
所以我们可以开一个数组tr[pp][x],pp=log10b+1pp={log_{10}{b}+1}pp=log10?b+1,表示乘以x?10ppx*10^{pp}x?10pp%k后等于x的数量,对于每个数x ，当她作为拼接的后半部分数字的情况，答案是tr[pp][(k-tr[i]%k)%k]
注意要判断不能用同一个数，自己和自己能结合的情况就是：(tr[i]+tr[i]*pp)%k=0
特别特别坑的一个点是，极限情况下使用pow函数和数字相乘会爆longlong ，用快速幂就行

#include using namespace std;#define endl '\n'#define inf 0x3f3f3f3f#define m_p(a,b) make_pair(a, b)#define mem(a,b) memset((a),(b),sizeof(a))#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";typedef long long ll;typedef pair  pii;#define MAX 300000 + 50ll n, m, k;ll tr[MAX];ll num[15][MAX];ll q_pow(ll a, ll b, ll mod){ll ans = 1;while(b > 0){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}inline ll lg(ll x){ll num = 0;while (x) {++num;x /= 10;}return num;}void work(){cin >> n >> k;for(int i = 1; i <= n; ++i)cin >> tr[i];for(int i = 1; i <= n; ++i){ll p = 1;for(int j = 0; j <= 10; ++j){++num[j][(tr[i] * p) % k];p = (p * 10) % k;}}ll ans = 0;for(int i = 1; i <= n; ++i){ans += num[lg(tr[i])][(k - (tr[i]%k))%k];if((tr[i] + (tr[i] * q_pow(10, lg(tr[i]), k))%k)%k == 0)--ans;}cout << ans << endl;}int main(){io;work();return 0;}

网络分析题目描述：

两种操作

1 x y ，表示将x和y连接起来
2 x c ，表示将与x在同一个连通块的点的权值+c
问最后每个点的权值是多少

思路：

带权并查集
tr[i]表示节点i的权值
对于权值修改，我们只需要修改根节点的权值，这样每个点的答案就是当前点到跟节点上路径的权值
如何进行路径压缩？
int getfa(int x){if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];//如果当前点就是根节点或者当前点的父亲节点就是根节点，就返回int root = getfa(fa[x]);tr[x] += tr[fa[x]];//先更新权值fa[x] = root;//再更新父节点return fa[x];}如何合并？
int xx = getfa(x);int yy = getfa(y);if(xx == yy)continue;//如果在同一个连通块内就不用管tr[xx] -= tr[yy];//消除新的根节点yy的权值的影响fa[xx] = yy;//更新根节点答案怎么输出：
for(int i = 1; i <= n; ++i){if(i == getfa(i))cout << tr[i] << ' ';//如果自己就是根节点，就直接输出else cout << tr[getfa(i)] + tr[i] << ' ';//否则，经过路径压缩后，一定是直接连接在根节点上面，所以答案是两部分，加上就行}

#include using namespace std;#define endl '\n'#define inf 0x3f3f3f3f#define mod 1000000007#define m_p(a,b) make_pair(a, b)#define mem(a,b) memset((a),(b),sizeof(a))#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";typedef long long ll;typedef pair  pii;#define MAX 300000 + 50int n, m, k;int tr[MAX];int fa[MAX];int getfa(int x){if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];int root = getfa(fa[x]);tr[x] += tr[fa[x]];fa[x] = root;return fa[x];}void work(){cin >> n >> m;for(int i = 1; i <= n; ++i)fa[i] = i;for(int i = 1, op, x, y; i <= m; ++i){cin >> op >> x >> y;if(op == 1){int xx = getfa(x);int yy = getfa(y);if(xx == yy)continue;tr[xx] -= tr[yy];fa[xx] = yy;}else{int xx = getfa(x);tr[xx] += y;}}for(int i = 1; i <= n; ++i){if(i == getfa(i))cout << tr[i] << ' ';else cout << tr[i] + tr[getfa(i)] << ' ';}cout << endl;}int main(){io;work();return 0;}

超级胶水题目描述：

n颗石子，按顺序排成一排
每个石子都有自己的重量，相邻两个石子粘起来的花费是两个石子的重量的乘积，每次只能粘相邻的两个石子，问将所有的石子粘起来的最小花费是多少

思路：

假设当前有三个石子，重量是a, b, c
粘1, 2后花费：a*b
再粘剩下的两个，花费是(a+b)*c
总花费是：ab + ac + bc
不难发现，无论粘贴的顺序如何，结果是不变的

【第十一届蓝桥杯省赛第一场C++AB组真题题解】

#include using namespace std;#define endl '\n'#define inf 0x3f3f3f3f#define mod 1000000007#define m_p(a,b) make_pair(a, b)#define mem(a,b) memset((a),(b),sizeof(a))#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";typedef long long ll;typedef pair  pii;#define MAX 300000 + 50int n, m, k;ll ans, sum;ll tr[MAX];void work(){cin >> n;for(int i = 1; i <= n; ++i)cin >> tr[i];sum = tr[1];for(int i = 2; i <= n; ++i){ans += sum * tr[i];sum += tr[i];}cout << ans << endl;}int main(){io;work();return 0;}