【题解】牛客小白月赛112
原本还有一个G题被审题人删了，不过很快就会在其他比赛放出来
A 智乃的天平
题解
主要考察读题以及分情况讨论，按题意枚举种情况判断即可
时间复杂度
代码
#include <iostream>
using namespace std;
bool check(int a, int b, int c) {
if (c - a - b == 0) return true; // 1. a 和 b 都在右侧
if (c + a - b == 0) return true; // 2. a 在左侧，b 在右侧
if (c - a + b == 0) return true; // 3. a 在右侧，b 在左侧
if (c - a == 0) return true; // 4. b 不用，b 在右侧
if (c - b == 0) return true; // 5. a 不用，b 在右侧
return false; // 如果没有情况能平衡
}
int main() {
int a, b, c;
cin >> a >> b >> c;
if (check(a, b, c)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
B 智乃爬山
题解
主要考察循如何使用循环语句
时间复杂度
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int max_height = -1;
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
int height = a[i] - (a[i - 1] + a[i + 1]) / 2;
max_height = max(max_height, height);
}
}
cout << max_height << endl;
return 0;
}
C 智乃放球
题解
主要考察简单数学计算和观察找规律
注意到一次只能同时消除个球，所以最终消除球的数目一定是
的倍数，所以必须有
在满足这个条件下，注意到合法的解集形成一个等差数列，其中
，所以只用考虑
在不在
的取值范围内
进一步的，发现上式中的取值范围连续，只用考虑最大的情况能不能放下所有的球即可
所以最终只需要判断和
的大小
时间复杂度 单组
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int T;
long long n, m, k, q;
int main(){
scanf("%d", &T);
while (T--) {
scanf("%lld %lld %lld %lld", &n, &m, &k, &q);
if (n % k != q % k){
printf("No\n");
continue;
}
printf(q <= m * (k - 1) ? "Yes\n" : "No\n");
}
return 0;
}
/*
2
1000000000 1000000000 1000000000 1000000000
1000000000 1 1000000000 1000000000
*/
D 智乃的"K"叉树
题解
主要考察贪心算法，提供如下一组hack数据
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
正确答案为
3 2
注意到选择某个节点作为根节点时，实际上的影响是其他所有节点因为其中一条边变为父向边导致减少
，所以只需要统计每个节点的度数，然后选择一个度数非当前最大值且节点编号最小的节点作为根节点即可。
唯一的特例是的情况需要特殊处理，其他情况均满足上述贪心算法。
时间复杂度
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
int a[MAXN];
int main(){
scanf("%d", &n);
for (int i = 1; i < n; ++i){
int u, v;
scanf("%d %d", &u, &v);
a[u]++;
a[v]++;
}
if (n == 2){
printf("1 1\n");
} else{
int mx = 0, root = -1;
for (int i = 1; i <= n; ++i){
mx = max(mx, a[i]);
}
for (int i = 1; i <= n; ++i){
if (a[i] != mx) {
root = i;
break;
}
}
printf("%d %d\n", mx - 1, root);
}
return 0;
}
E/F 智乃的"凑数"题
题解
主要考察对于时间复杂度的计算以及背包问题处理
首先题目里没明说，但是这个应该都知道吧，如果不知道记得知道一下，还挺常用的
easy
写的比较好的dfs可以直接冲过去，这个数据范围本来也是卡不掉乱搞减枝的，不如说hard的正解本来就是一种可以证明时间复杂度的减枝。
可以暴力bool dp[sum_a][sum_b]，然后dfs查找可行解，或者在dp的过程中记录可行解
转移方程：
初始状态
hard
如果easy使用了二维01背包算法，则直接把easy的算法贴过来就可以通过（但是要解决一下空间问题），想这么一个问题
现在需要令
如果，那么
如果，那么
如果，那么
以此类推则有（调和级数近似复杂度）
说明这个动态规划中，有效的状态总数只有个，故复杂度是
而不是
接下来要解决的问题就是数组怎么存的问题问题。
如果你开了一个1e8的数组也通过了本题，然后发现实际内存使用很低，则是由于操作系统机制导致，没有被实际使用到的内存会被操作系统按照512KB分页换页换走，所以实际上用不了那么多的物理内存，虚拟内存一般不作为oj判题的依据。
方法一
使用二维vector，因为可以每一行开不同长度的数组，所以可以直接开vector，开完以后当成普通的数组
时间复杂度
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef Cai_Guang
#define debug //
#define test //
#endif
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
const int M = 1e4 + 10;
std::vector dp(M, std::vector<bool>());
std::vector pre(M, std::vector<std::array<int, 2>>());
dp[0].assign(M, false);
pre[0].assign(M, {});
for (int i = 1; i < M; i++) {
dp[i].assign(M / i + 10, false);
pre[i].assign(M / i + 10, {});
}
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = M - 1; j >= 0; j--) {
for (int k = dp[j].size() - 1; k >= 0; k--) {
if (k >= a[i] && dp[j][k - a[i]] && !dp[j][k]) {
dp[j][k] = dp[j][k - a[i]];
pre[j][k] = {j, k - a[i]};
}
if (j >= a[i] && dp[j - a[i]][k] && !dp[j][k]) {
dp[j][k] = dp[j - a[i]][k];
pre[j][k] = {j - a[i], k};
}
}
}
}
for (int i = 1, x; i <= m; i++) {
std::cin >> x;
for (int j = 1; j * j <= x; j++) {
if (x % j == 0) {
if (dp[j][x / j]) {
std::cout << "Yes\n";
int L = j, R = x / j;
std::vector<int> l, r;
while (L != 0 || R != 0) {
test(L, R);
auto [LL, RR] = pre[L][R];
if (L != LL) {
l.push_back(L - LL);
}
if (R != RR) {
r.push_back(R - RR);
}
L = LL;
R = RR;
}
std::cout << l.size() << ' ' << r.size() << '\n';
for (auto _ : l) {
std::cout << _ << ' ';
} std::cout << '\n';
for (auto _ : r) {
std::cout << _ << ' ';
} std::cout << '\n';
goto G;
}
}
}
std::cout << "No\n";
G:;
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#ifdef Cai_Guang
//freopen("1.in", "r", stdin);
localTest = true;
#endif
int t = 1;
// std::cin >> t;
while(t--) {
solve();
}
}
方法二
将dp数组二维压缩成一维，我们按行切成一条一条的，可以开三个数组belong,l,r
belong表示压缩后的第个位置原来属于哪一行
l表示第行在压缩后数组中的第一个下标
r表示第行在压缩后数组中的最后一个下标
当然，本题dp部分由于是bool背包，显然可以使用类似bitset的数据结构进行加速，所以实际上的范围还能扩到
时间复杂度
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 115005;
const int M = 10000;
bool dp[MAXM];
int pre[MAXM];
int belong[MAXM], ans[MAXN], l[MAXM], r[MAXM], n, m, a[MAXN], tot, x;
int main(){
tot = M + 1;
r[0] = M;
for (int i = 1; i <= M; ++i){
l[i] = tot;
tot += M / i + 1;
r[i] = tot - 1;
for (int j = l[i]; j <= r[i]; ++j){
belong[j] = i;
}
}
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
}
dp[0] = true;
for (int i = 1; i <= n; ++i){
for (int j = tot - 1; j >= 0; --j){
if (dp[j])continue;
auto s1 = belong[j], s2 = j - l[belong[j]];
if (s1 >= a[i] && dp[l[s1 - a[i]] + s2]){
dp[j] = true;
pre[j] = l[s1 - a[i]] + s2;
} else if (s2 - a[i] >= 0 && dp[j - a[i]]){
dp[j] = true;
pre[j] = j - a[i];
}
}
}
for (int i = 0; i < tot; ++i){
if (dp[i]){
ans[belong[i] * (i - l[belong[i]])] = i;
}
}
while (m--){
scanf("%d", &x);
if (ans[x]){
printf("Yes\n");
vector<int> v[2];
for (x = ans[x]; x; x = pre[x]){
auto s1 = belong[x], s2 = x - l[belong[x]];
auto ss1 = belong[pre[x]], ss2 = pre[x] - l[belong[pre[x]]];
v[s1 == ss1].push_back((s1 - ss1) | (s2 - ss2));
}
printf("%d %d\n", (int) v[0].size(), (int) v[1].size());
for (int i = 0; i < v[0].size(); ++i){
printf("%d%c", v[0][i], " \n"[i + 1 == v[0].size()]);
}
for (int i = 0; i < v[1].size(); ++i){
printf("%d%c", v[1][i], " \n"[i + 1 == v[1].size()]);
}
} else{
printf("No\n");
}
}
return 0;
}
另外赛时好像没有人用py过
这里补一下py的通过代码
py代码
import sys
def main():
MAXN = 10005
MAXM = 115005
M = 10000
# 初始化数组
dp = [False] * (MAXM + 1)
pre = [0] * (MAXM + 1)
belong = [0] * (MAXM + 1)
ans = [0] * (MAXN)
l = [0] * (MAXM + 1)
r = [0] * (MAXM + 1)
tot = M + 1
r[0] = M
for i in range(1, M + 1):
l[i] = tot
tot += M // i + 1
r[i] = tot - 1
for j in range(l[i], r[i] + 1):
belong[j] = i
# 读取输入
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
a = [0] + a # 使a的索引从1开始
dp[0] = True
for i in range(1, n + 1):
for j in range(tot - 1, -1, -1):
if dp[j]:
continue
s1 = belong[j]
s2 = j - l[s1]
if s1 >= a[i] and (l[s1 - a[i]] + s2) <= MAXM and dp[l[s1 - a[i]] + s2]:
dp[j] = True
pre[j] = l[s1 - a[i]] + s2
elif (s2 - a[i]) >= 0 and dp[j - a[i]]:
dp[j] = True
pre[j] = j - a[i]
for i in range(tot):
if dp[i]:
key = belong[i] * (i - l[belong[i]])
if key < MAXN:
ans[key] = i
for _ in range(m):
x = int(sys.stdin.readline())
if ans[x] != 0:
print("Yes")
v = [[], []]
current = ans[x]
while current != 0:
s1 = belong[current]
s2 = current - l[s1]
ss1 = belong[pre[current]]
ss2 = pre[current] - l[ss1]
if s1 == ss1:
v[0].append((s1 - ss1) | (s2 - ss2))
else:
v[1].append((s1 - ss1) | (s2 - ss2))
current = pre[current]
print(len(v[0]), len(v[1]))
for num in v[0]:
print(num, end=' ')
print()
for num in v[1]:
print(num, end=' ')
print()
else:
print("No")
if __name__ == "__main__":
main()
n,m=map(int,input().split()) k=list(map(int,input().split())) M=[] for i in range(m): M.append(int(input())) def dfs(step,a,b,mi): global flag if flag: return if step==n: summ=sum(a)*sum(b) if summ==mi: print('Yes&(60527)#39;) print(len(a),len(b)) for i in a: print(i,end=' &(30184)#39;) print() for j in b: print(j,end=' &(30184)#39;) print() flag=1 return a2=a.copy() a2.append(k[step]) dfs(step+1,a2,b,mi) b2=b.copy() b2.append(k[step]) dfs(step+1,a,b2,mi) dfs(step+1,a,b,mi) for mi in M: flag=0 dfs(0,[],[],mi) if not flag: print('No&(60528)#39;)