当前位置：首页 > news >正文

（个人题解）第十六届蓝桥杯大赛软件赛省赛C/C++ 研究生组

news 来源：原创 2025/9/6 16:19:59

宇宙超级无敌声明：个人题解（好久不训练，赛中就是一个憨憨）
先放代码吧，回头写思路。

文章目录

A. 数位倍数
B. IPv6
C. 变换数组
D. 最大数字
E. 冷热数据队列
F. 01串
G. 甘蔗
H. 原料采购

A. 数位倍数

问：
在1至202504 （含）中，有多少个数的各个数位之和是5的整数倍。

code：

#include<bits/stdc++.h>using namespace std;int main(){int cnt = 0;for(int i = 1; i <= 202504; i++){int tmp = 0, x = i;while(x){tmp += x % 10;x /= 10;}if(tmp % 5 == 0){cnt++;}}	cout << cnt << endl;return 0;
}

B. IPv6

问：
所有IPv6地址的最短缩写的长度和是多少，对1e9+7取模。

思路：
八段IPv6地址，每一段有四位十六进制数。考虑每一位是否为零，使用四位二进制表示（0 - 15）。
eg：0101，表示第三位是有值的，这个段长度为3，有15*15种方案
DFS搜每一段，然后在考虑连续多个段为零的情况。
ps: 赛后发现数组忘记清零了/(ㄒoㄒ)/~~

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 1e9 + 7;int a[20], b[20], is0[20], n = 8;
ll res = 0;void dfs(int pos){if(pos == n+1){for(int i = 1; i <= n; i++){int x = a[i];if(x == 0) b[i] = 1, is0[i] = 1; else{while(x){b[i]++;x >>= 1;}				}}ll len = 7, cnt = 0, mx = 0, flag = 0;for(int i = 1; i <= n; i++){len += b[i];if(is0[i] == 0){ // 不是0 if(cnt >= mx){ // 细节 >= if(i == cnt) flag = 1;else flag = 0;mx = cnt;}cnt = 0;} else cnt++;b[i] = is0[i] = 0;}if(cnt > mx){	// 细节 > mx = cnt;flag = 1;}if(mx == 8) len = 2;else if(flag && mx > 0) len = len - (2 * mx - 1) + 1;	// 首尾长度+1 else if(mx > 0) len = len - (2 * mx - 1); ll base = 1;for(int i = 1; i <= n; i++){int x = a[i];while(x){if(x & 1) base = base * 25 % mod;x >>= 1;}}res = (res + len * base % mod) % mod;return;}for(int i = 0; i < 16; i++){a[pos] = i;dfs(pos+1);}
}int main(){dfs(1);cout << res << endl;return 0;
}

C. 变换数组

问：
对数组a的每个元素进行 m 次操作，每次操作令 a[i] = a[i] * bit(a[i])，其中 bit(a[i]) 表示 a[i] 的二进制表示有多
少个1。

思路：
数据范围不大，直接模拟。

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 1e3 + 5;int a[maxn];int main(){int n, m;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];cin >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int cnt = 0, x = a[i];while(x){if(x & 1) cnt++;x >>= 1;}a[i] *= cnt;}}for(int i = 1; i <= n; i++) cout << a[i] << (i == n ? "\n" : " ");return 0;
}

D. 最大数字

问：
有 n 个连续的整数1,2,3,··· ,n，可以自由排列它们的顺序。
然后，把这些数字转换成二进制表示，按照排列顺序拼接形成一个新的二进制数。
目标是让这个二进制数的值最大，并输出这个二进制对应的十进制表示。

思路：
首先，考虑如何排序：
如下图，进行先序遍历，即可得到最大的二进制表示。
在这里插入图片描述
再考虑如何输出这个数，我写了个大数加法，过 n <= 1e3，没问题。对于所有数据的 n <= 1e4，坐等大佬的最优解。

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 1e3 + 5;string add(string a, string b){	// 大数加法if(a.size() > b.size()) swap(a, b);int lena = a.size(), lenb = b.size(), flag = 0;for(int i = 0; i < lena; i++){int num = a[lena - i - 1] - '0' + b[lenb - i - 1] - '0' + flag;if(num >= 10) flag = 1, num -= 10;else flag = 0;b[lenb - i - 1] = char(num + '0');}if(flag){if(lena == lenb) b = "1" + b;else{int pos = lena;while(flag && pos < lenb){b[lenb - pos - 1] += 1;if(b[lenb - pos - 1] > '9'){b[lenb - pos - 1] = '0';flag = 1;}else flag = 0;pos++;}if(flag) b = "1" + b;}}return b;
}string t = "";void dfs(int x, int n, string s){	// 先序遍历t = t + s;if(2*x+1 <= n) dfs(2*x+1, n, s + "1");if(2*x+0 <= n) dfs(2*x+0, n, s + "0");
}string res = "0", base = "1";int main(){int n;cin >> n;dfs(1, n, "1");	int len = t.size();for(int i = 0; i < len; i++){if(t[len-i-1] == '1') res = add(res, base);base = add(base, base);}cout << res << endl;return 0;
}

E. 冷热数据队列

问：
有两个队列 q1 和 q2，初始为空，容量分别为 n1 和 n2。
进行 m 次操作，对于每次操作，查询一个 x：

若 x 既不在 q1 中，也不在 q2 中，把 x 放入 q2 的首部。
若 x 已经在队列中，则将 x 移动至 q1 首部。
当 q1 或 q2 队列容量不足时，会将其尾部的数据页淘汰出去。
当 q1 已满，但 q2 未满时，从 q1 中淘汰出的数据页会移动到 q2 首部。

输出 m 次操作后，两个队列中的元素。
在这里插入图片描述
思路：
根据题意模拟，注意这里的队列的首部的定义，观察样例。
对于每次操作的元素 x，维护一个状态 f，表示其在那个队列中。
对于移动操作或弹出操作，只修改状态，进行懒操作(像线段树的lazy操作一样)，具体实现看代码。
对于 q1，因为有移动操作，当元素进队时，连着操作次数一起进队，并且通过记录最新操作来判断，队头的元素是否真的被弹出了。

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 5;int f[maxn], op[maxn]; // 如x在q1中，op表示操作号 
int res[maxn];
queue<int> q2, qu;
queue<pair<int, int> > q1;int n1, n2;
int cnt1 = 0, cnt2 = 0;void push_q2(int x){f[x] = 2;q2.push(x);cnt2++;	while(cnt2 > n2){int tmp = q2.front();q2.pop();if(f[tmp] == 2){cnt2--;f[tmp] = 0;}}
}void push_q1(int x, int i){f[x] = 1;op[x] = i;q1.push({x, i});cnt1++;	while(cnt1 > n1){pair<int, int> tmp = q1.front();q1.pop();if(f[tmp.first] == 1 && op[tmp.first] == tmp.second){cnt1--;f[tmp.first] = 0;if(cnt2 < n2) push_q2(tmp.first);}}
}int main(){cin >> n1 >> n2;int q;cin >> q;for(int i = 1; i <= q; i++){int x;cin >> x;if(f[x] == 0) push_q2(x);else if(f[x] == 1){// 在q，且在q1，仅移动 q1.push({x, i});op[x] = i; // 记录最大的操作号 }else{// 在q，在q2，移动到q1 cnt2--;	 // q2中移除 push_q1(x, i); // 放入q1 }}int cnt = 0;while(!q1.empty()){pair<int, int> tmp = q1.front();q1.pop();if(f[tmp.first] == 1 && op[tmp.first] == tmp.second){res[++cnt] = tmp.first;}}for(int i = cnt; i >= 1; i--) cout << res[i] << " ";cout << endl;cnt = 0;while(!q2.empty()){int tmp = q2.front();q2.pop();if(f[tmp] == 2){res[++cnt] = tmp;}}for(int i = cnt; i >= 1; i--) cout << res[i] << " ";cout << endl;return 0;
}

F. 01串

给定一个由0,1,2,3··· 的二进制表示拼接而成的长度无限的 01 串。其前若干位形如011011100101110111··· 。
请求出这个串的前x位里有多少个1。
在这里插入图片描述
思路：
赛中就写了个模拟。
看数据范围，应该是有结论的，即 x 位二进制下，有多少个1 这种结论，然后再处理一些细节才能过所有数据。
挖坑，有时间再想结论。

code:

#include<bits/stdc++.h>using namespace std;stack<int> st;int main(){long long n;scanf("%lld", &n);long long res = 0, len = 1;for(int i = 1; i <= n; i++){int x = i;while(x){	// 注意要逆过来st.push(x % 2);x >>= 1;}while(len < n && !st.empty()){res += st.top();st.pop();len++;}}	printf("%lld", res);return 0;
}

G. 甘蔗

应该是个DP，赛中写了个爆搜。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e3 + 5;int res = 2e9;int a[maxn], b[maxn], v[maxn];vector<int> check(int A, int B, int C){// 默认砍A vector<int> tmp; if(A <= B){if(B - C >= 0 && B - C <= A){tmp.push_back(B - C);}} else{if(A - C >= B) tmp.push_back(B + C);if(B - C >= 0) tmp.push_back(B - C);}return tmp;
}void dfs(int pos, int n, int m, int cnt){if(pos > n){res = min(res, cnt);return;}if(cnt > res) return;int A = a[pos], B = a[pos-1];for(int i = 1; i <= m; i++){vector<int> tmp = check(A, B, b[i]);for(auto x : tmp){a[pos] = x;dfs(pos+1, n, m, cnt+1);a[pos] = A;}}if(v[abs(A - B)] == 1){dfs(pos+1, n, m, cnt);}
}int main(){int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= m; i++) scanf("%d", &b[i]), v[b[i]] = 1;sort(b+1, b+1+m);res = 2e9;dfs(2, n, m, 0);int A = a[1];for(int i = 1; i <= m; i++){vector<int> tmp = check(a[1], a[2], b[i]);for(auto x : tmp){a[1] = x;dfs(3, n, m, 1);a[1] = A;}		}if(res > n) res = -1;cout << res << endl;return 0;
}

H. 原料采购

维护一个大小为 m 的大根堆，即单价大的在上，依次走所有采购点。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;ll a[maxn], b[maxn], c[maxn];priority_queue<pair<ll, ll> > qu;int main(){ll n, m, o;scanf("%lld %lld %lld", &n, &m, &o);for(int i = 1; i <= n; i++) scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);ll res = 9e18, len_value = 0, now_value = 0, v = 0;	// 距离 + 产品, 体积 for(int i = 1; i <= n; i++){len_value = c[i] * o;if(v + b[i] <= m){qu.push({a[i], b[i]});now_value = a[i] * b[i];continue;}else{if(v < m){qu.push({a[i], m - v});now_value += a[i] * (m - v);b[i] -= (m - v);v = m;}// 已经满 m ll num = 0;while(!qu.empty()){pair<ll, ll> t = qu.top();if(t.first > a[i]){qu.pop();if(num + t.second >= b[i]){now_value -= t.first * (b[i] - num);t.second -= (b[i] - num);num = b[i];if(t.second != 0) qu.push(t);break;}else{num += t.second;now_value -= t.first * t.second;}}else break;}if(num != 0){qu.push({a[i], num});now_value += a[i] * num;}res = min(res, now_value + len_value);}}if(m != v) res = -1;printf("%lld\n", res);return 0;
}

文章目录

A. 数位倍数

B. IPv6

C. 变换数组

D. 最大数字

E. 冷热数据队列

F. 01串

G. 甘蔗

H. 原料采购

相关文章：