第十六届蓝桥杯大赛软件赛省赛 C++ 大学 B 组 部分题解

赛时参加的是Python组，这是赛后写的题解，还有两题暂时还不会，待更新

题目链接题目列表 - 洛谷 | 计算机科学教育新生态

A 移动距离

答案：1576

C  可分解的正整数

Python3
 

import itertools
from functools import cmp_to_keyimport sysinput = sys.stdin.readline
sys.set_int_max_str_digits(100000)def I():return input().strip()def II():return int(I())def MII():return map(int, I().split())def LMII():return list(MII())def solve():n = II()data = LMII()res = 0for x in data:if x != 1:res += 1print(res)T = 1
for _ in range(T):solve()

C++

#include"iostream"
using namespace std;int main() {int n = 0, x, res = 0;cin >> n;for (int i = 0;i < n;i++) {cin >> x;if (x != 1)res++;}cout << res;
}

D 产值调整

Python3

import itertools
from functools import cmp_to_keyimport sysinput = sys.stdin.readline
sys.set_int_max_str_digits(100000)def I():return input().strip()def II():return int(I())def MII():return map(int, I().split())def LMII():return list(MII())def solve():t = II()for i in range(t):a, b, c, k = MII()for j in range(k):if a == b == c:breaka, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2print(a, b, c)T = 1
for _ in range(T):solve()

C++

#include"iostream"
using namespace std;int main() {int t;cin >> t;for (int i = 0;i < t;i++) {int a, b, c, k;cin >> a >> b >> c >> k;for (int j = 0;j < k;j++) {if (a == b && b == c)break;int aa = (b + c) / 2;int bb = (a + c) / 2;int cc = (a + b) / 2;a = aa;b = bb;c = cc;}cout << a << " " << b << " " << c << endl;}
}

E 画展布置

Python3

import itertools
from functools import cmp_to_keyimport sysinput = sys.stdin.readline
sys.set_int_max_str_digits(100000)def I():return input().strip()def II():return int(I())def MII():return map(int, I().split())def LMII():return list(MII())def solve():n, m = MII()data = LMII()data.sort()tmp = [0] * (n - 1)for i in range(n - 1):tmp[i] = data[i + 1] ** 2 - data[i] ** 2res = 0for i in range(m - 1):res += tmp[i]idx = 0now = resfor i in range(m - 1, n - 1):now = now + tmp[i] - tmp[idx]res = min(res, now)idx += 1print(res)T = 1
for _ in range(T):solve()

C++

#include"iostream"
#include"math.h"
#include"algorithm"
#include"vector"
using namespace std;int main() {int n, m;cin >> n >> m;vector<int> data;for (int i = 0;i < n;i++) {int x;cin >> x;data.push_back(x);}sort(data.begin(), data.end());int tmp[100005] = { 0 };for (int i = 0;i < n - 1;i++)tmp[i] = pow(data[i + 1], 2) - pow(data[i], 2);long long res = 0;for (int i = 0;i < m - 1;i++)res += tmp[i];int idx = 0;long long now = res;for (int i = m - 1;i < n - 1;i++) {now = now + tmp[i] - tmp[idx];res = min(res, now);idx++;}cout << res << endl;
}

F 水质检测

Python3

import itertools
from functools import cmp_to_keyimport sysinput = sys.stdin.readline
sys.set_int_max_str_digits(100000)def I():return input().strip()def II():return int(I())def MII():return map(int, I().split())def LMII():return list(MII())def solve():s1 = I()s2 = I()st = -1en = 0for i in range(len(s1)):if s1[i] == "#" or s2[i] == "#":if st == -1:st = ielse:en = i# print(st, en)if st == -1 or en == 0:print(0)else:res = 0tmp = 0for i in range(st, en + 1):# print(tmp,s1[i],s2[i])if s1[i] == s2[i] == '.':res += 1elif s1[i] == '.':if tmp == 1:res += 1tmp = 0else:tmp = 2elif s2[i] == ".":if tmp == 2:res += 1tmp = 0else:tmp = 1else:tmp = 0# print(i, res)print(res)T = 1
for _ in range(T):solve()

C++

#include"iostream"
#include"math.h"
#include"algorithm"
#include"vector"
#include"string"
using namespace std;int main() {string s1;string s2;cin >> s1;cin >> s2;int st = -1;int en = 0;for (int i = 0;i < s1.size();i++) {if (s1[i] == '#' || s2[i] == '#') {if (st == -1)st = i;else en = i;}}if (st == -1 || en == 0)cout << 0;else {int res = 0;int tmp = 0;for (int i = st;i < en + 1;i++) {if (s1[i] == '.' && s2[i] == '.') {res++;}else if (s1[i] == '.') {if (tmp == 1) {res++;tmp = 0;}else tmp = 2;}else if (s2[i] == '.') {if (tmp == 2) {res++;tmp = 0;}else tmp = 1;}else tmp = 0;}cout << res;}
}

G 生产车间

Python3

import itertools
from functools import cmp_to_keyimport sysinput = sys.stdin.readline
sys.set_int_max_str_digits(100000)def I():return input().strip()def II():return int(I())def MII():return map(int, I().split())def LMII():return list(MII())def solve():n = II()data = LMII()dic = {}for i in range(n - 1):u, v = MII()dic[u] = dic.get(u, []) + [v]dic[v] = dic.get(v, []) + [u]visited = [0] * (n + 1)lst = [[1]]now_visit = [1]visited[1] = 1father = {}son = {}while now_visit:next_visit = []for x in now_visit:for xx in dic[x]:if not visited[xx]:father[xx] = xson[x] = son.get(x, []) + [xx]next_visit.append(xx)visited[xx] = 1if next_visit:lst.append(next_visit)now_visit = next_visitlst.reverse()res = [set() for _ in range(n)]for i in range(1, n + 1):if i not in son:res[i - 1].add(data[i - 1])# print(res)# print(lst)# print(father)# print(son)def fun(lst, x):"""lst: 一个列表，列表中每个元素都是一个可迭代的集合（或列表），表示“这一组”可供选择的数字。x: 目标上界（小于等于 x）返回: 一个集合 ans，包含所有可能的选数总和（<= x）。"""# 初始只能选空集，总和为 0ans = {0}# 对每一组可选数字，更新所有可能的总和for group in lst:new_ans = set(ans)  # 保留“都不选任何数”的那部分for s in ans:  # 对已有的每一种“已选总和”for num in group:tot = s + numif tot <= x:new_ans.add(tot)ans = new_ansans.remove(0)return anshandle = [0] * (n + 1)for x in lst[:-1]:for xx in x:if not handle[xx]:tmp = father[xx]need_handle = []for y in son[tmp]:handle[y] = 1need_handle.append(res[y - 1])# print(need_handle)res[tmp - 1] |= fun(need_handle, data[tmp - 1])# print(tmp, res[tmp - 1])if not res[0]:print(0)else:print(max(res[0]))T = 1
for _ in range(T):solve()

C++

#include"iostream"
#include"math.h"
#include"algorithm"
#include"vector"
#include"string"
#include"unordered_map"
#include"unordered_set"
#include"set"
using namespace std;unordered_set<int> fun(const vector<unordered_set<int>>& lst, int x) {unordered_set<int> ans = { 0 };for (const auto& group : lst) {unordered_set<int> new_ans;for (int s : ans) {new_ans.insert(s);  // 记得保留原来的情况（不选当前组）for (int num : group) {int tot = s + num;if (tot <= x) new_ans.insert(tot);}}ans = std::move(new_ans);}ans.erase(0);return ans;
}int main() {int n;cin >> n;vector<int> data;for (int i = 0;i < n;i++) {int x;cin >> x;data.push_back(x);}unordered_map<int, vector<int>> m;for (int i = 0;i < n - 1;i++) {int u, v;cin >> u >> v;m[u].push_back(v);m[v].push_back(u);}vector<int> visited(n + 1, 0);vector<vector<int>> lst = { {1} };vector<int> now_visit = { 1 };visited[1] = 1;unordered_map<int, int> father;unordered_map<int, vector<int>> son;while (!now_visit.empty()) {vector<int> next_visit;for (auto x : now_visit) {for (auto xx : m[x]) {if (!visited[xx]) {father[xx] = x;son[x].push_back(xx);next_visit.push_back(xx);visited[xx] = 1;}}}if (!next_visit.empty()) {lst.push_back(next_visit);}now_visit = next_visit;}reverse(lst.begin(), lst.end());vector<unordered_set<int>> res(n);for (int i = 1;i < n + 1;i++) {if (son.find(i) == son.end()) {res[i - 1].insert(data[i - 1]);}}vector<int> handle(n + 1, 0);for (int i = 0; i < (int)lst.size() - 1; i++) {for (auto x : lst[i]) {if (!handle[x]) {int tmp = father[x];vector<unordered_set<int>> need_handle;for (auto y : son[tmp]) {handle[y] = 1;need_handle.push_back(res[y - 1]);}unordered_set<int> merged = fun(need_handle, data[tmp - 1]);for (int val : merged) {res[tmp - 1].insert(val);}}}}if (res[0].empty()) {cout << 0 << endl;}else {int ans = 0;for (auto a : res[0]) {if (a > ans)ans = a;}cout << ans << endl;}
}