赛时参加的是Python组，这是赛后写的题解，还有两题暂时还不会，待更新
A 移动距离
答案：1576
C 可分解的正整数
Python3
import itertools
from functools import cmp_to_key
import sys
input = 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 = 0
for x in data:
if x != 1:
res += 1
print(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_key
import sys
input = 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:
break
a, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2
print(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_key
import sys
input = 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] ** 2
res = 0
for i in range(m - 1):
res += tmp[i]
idx = 0
now = res
for i in range(m - 1, n - 1):
now = now + tmp[i] - tmp[idx]
res = min(res, now)
idx += 1
print(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_key
import sys
input = 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 = -1
en = 0
for i in range(len(s1)):
if s1[i] == "#" or s2[i] == "#":
if st == -1:
st = i
else:
en = i
# print(st, en)
if st == -1 or en == 0:
print(0)
else:
res = 0
tmp = 0
for i in range(st, en + 1):
# print(tmp,s1[i],s2[i])
if s1[i] == s2[i] == '.':
res += 1
elif s1[i] == '.':
if tmp == 1:
res += 1
tmp = 0
else:
tmp = 2
elif s2[i] == ".":
if tmp == 2:
res += 1
tmp = 0
else:
tmp = 1
else:
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_key
import sys
input = 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] = 1
father = {}
son = {}
while now_visit:
next_visit = []
for x in now_visit:
for xx in dic[x]:
if not visited[xx]:
father[xx] = x
son[x] = son.get(x, []) + [xx]
next_visit.append(xx)
visited[xx] = 1
if next_visit:
lst.append(next_visit)
now_visit = next_visit
lst.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）。
"""
# 初始只能选空集，总和为 0
ans = {0}
# 对每一组可选数字，更新所有可能的总和
for group in lst:
new_ans = set(ans) # 保留“都不选任何数”的那部分
for s in ans: # 对已有的每一种“已选总和”
for num in group:
tot = s + num
if tot <= x:
new_ans.add(tot)
ans = new_ans
ans.remove(0)
return ans
handle = [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] = 1
need_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;
}
}