2024年中国传媒大学程序设计大赛（同步赛）解题报告(流水账版) | 珂学家
小苯的区间和疑惑
https://ac.nowcoder.com/acm/contest/77526/A
前言
整体评价
整场还是挺nice，不是特别难，除了I题。J题是运气好，刚研究过区间gcd的性质，F题是启发式合并，不知道是不是正解，D题是一道很好的构造题，很妙。B题用了调和级数。其他的题，没啥印象了。倒是G题，感觉太套路，但是过的人有点少。
A. 小苯的区间和疑惑
思路: 前后缀拆解
n = int(input())
arr = list(map(int, input().split()))
if n == 1:
print (arr[0])
exit(0)
from math import inf
pre = [-inf] * n
suf = [-inf] * n
for i in range(n):
if i == 0:
pre[i] = max(0, arr[i])
else:
pre[i] = max(pre[i - 1] + arr[i], arr[i])
pre[i] = max(0, pre[i])
for i in range(n - 1, -1, -1):
if i == n - 1:
suf[i] = max(0, arr[i])
else:
suf[i] = max(suf[i + 1] + arr[i], arr[i])
suf[i] = max(0, suf[i])
res = [-inf] * n
res[0] = arr[0] + suf[1]
res[n - 1] = arr[n - 1] + pre[n - 2]
for i in range(1, n - 1):
res[i] = suf[i + 1] + pre[i - 1] + arr[i]
print (*res, sep=' ')
B. 小苯的三元组
思路: 调和级数
推导
说明 , 且满足
所以这题的思路，就是维护每个数的因子个数和倍数个数
调和级数
n = int(input())
arr = list(map(int, input().split()))
mx = max(arr)
# 感觉是调和级数
from collections import Counter
cnt = [0] * (mx + 1)
for v in arr:
cnt[v] += 1
hp1 = [0] * (mx + 1)
hp2 = [0] * (mx + 1)
# 预处理 因子和倍数
for i in range(1, mx + 1):
cc = cnt[i]
if cc == 0:
continue
j = 2
while j * i <= mx:
v = cnt[j * i]
if v > 0:
hp1[i] += v
hp2[j * i] += cc
j += 1
res = 0
for i in range(1, mx + 1):
if cnt[i] == 0:
continue
v = cnt[i]
res += v * v * v
res += v * v * hp1[i]
res += v * v * hp2[i]
res += v * hp1[i] * hp2[i]
print (res)
C. 小红的 CUC
签到题
n = int(input())
if n < 3:
print (-1)
else:
print ("CUC" + ''.join(['A' for _ in range(n - 3)]))
D. 小红的矩阵构造（一）
思路: 构造
从排列的角度出发
先从n的行和列，出发，这样可以填满每个格子（填1） 然后从1的行和列出发，这样可以填满剩余的格子（填0）
然后去掉这两行两列之后，
就会出现，一个(n-2) * (n-2) 矩阵，也就是子问题。
即(n, 1) -> (n-1, 2) -> (n-2, 3) -> ....
大概是这个思路，我觉得这题很难。
# (n, 1), (n - 1, 2)，...
n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
vis = [[False] * n for _ in range(n)]
chess = [['0'] * n for _ in range(n)]
arrRev = [0] * (n + 1)
brrRev = [0] * (n + 1)
for i in range(n):
arrRev[arr[i]] = i
brrRev[brr[i]] = i
big, small = n, 1
while big >= small:
idx = arrRev[big]
for i in range(n):
if not vis[idx][i]:
vis[idx][i] = True
chess[idx][i] = '1'
idx2 = brrRev[big]
for i in range(n):
if not vis[i][idx2]:
vis[i][idx2] = True
chess[i][idx2] = '1'
pdx = arrRev[small]
for i in range(n):
if not vis[pdx][i]:
vis[pdx][i] = True
pdx2 = brrRev[small]
for i in range(n):
if not vis[i][pdx2]:
vis[i][pdx2] = True
big-=1
small+=1
for i in range(n):
print (''.join(chess[i]))
E. 小红的矩阵构造（二）
思路：构造
按序构造即可
h, w, k = list(map(int, input().split()))
if k > (h - 1) * (w - 1):
print (-1)
else:
grids = [['0'] * w for _ in range(h)]
grids[0][0] = '1'
grids[1][0] = '1'
for i in range(1, w):
if k > 0:
grids[0][i] = '1'
grids[1][i] = '1'
k -= 1
row = 2
while k > 0:
grids[row][0] = '1'
for i in range(1, w):
if k > 0:
grids[row][i] = '1'
k -= 1
row += 1
for i in range(h):
print (''.join(grids[i]))
F. 小红的子树乘积
思路：启发式合并(大的合并小的) + 数论
这题用java写，因为python的递归栈深度太小了。
如果子节点>=k了，其实父节点肯定>=k, 这边是可以优化的
import java.io.*;
import java.util.*;
public class Main {
static class Solution {
int n;
long k;
List<Integer>[]g;
int[] dp;
int solve(int n, long k, List<Integer> []g) {
this.n = n;
this.g = g;
this.k = k;
this.dp = new int[n + 1];
dfs(1, -1);
return Arrays.stream(dp).sum();
}
// 有一个数学公式
Map<Integer, Integer> dfs(int u, int fa) {
// *)
Map<Integer, Integer> mp = new TreeMap<>();
for (int v: g[u]) {
if (v == fa) continue;
Map<Integer,Integer> cs = dfs(v, u);
if (dp[v] == 1) {
dp[u] = 1;
continue;
}
// 启发式合并
if (cs.size() > mp.size()) {
Map<Integer, Integer> tmp = mp;
mp = cs;
cs = tmp;
}
for (Map.Entry<Integer, Integer> ent: cs.entrySet()) {
mp.merge(ent.getKey(), ent.getValue(), Integer::sum);
}
}
if (dp[u] == 0) {
int cu = u;
for (int i = 2; i <= cu / i; i++) {
if (cu % i == 0) {
int cc = 0;
while (cu % i == 0) {
cu /= i;
cc++;
}
mp.merge(i, cc, Integer::sum);
}
}
if (cu > 1) {
mp.merge(cu, 1, Integer::sum);
}
long r = 1;
for (Map.Entry<Integer, Integer> ent: mp.entrySet()) {
r *= (ent.getValue() + 1);
if (r >= k) {
dp[u] = 1;
break;
}
}
}
return mp;
}
}
public static void main(String[] args) {
AReader sc = new AReader();
int n = sc.nextInt();
long k = sc.nextLong();
List<Integer>[] g = new List[n + 1];
Arrays.setAll(g, x->new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt(), v = sc.nextInt();
g[u].add(v);
g[v].add(u);
}
Solution solution = new Solution();
int res = solution.solve(n, k, g);
System.out.println(res);
}
static
class AReader {
private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer tokenizer = new StringTokenizer("");
private String innerNextLine() {
try {
return reader.readLine();
} catch (IOException ex) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String nextLine = innerNextLine();
if (nextLine == null) {
return false;
}
tokenizer = new StringTokenizer(nextLine);
}
return true;
}
public String nextLine() {
tokenizer = new StringTokenizer("");
return innerNextLine();
}
public String next() {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
// public BigInteger nextBigInt() {
// return new BigInteger(next());
// }
// 若需要nextDouble等方法，请自行调用Double.parseDouble包装
}
}
G. 小红的独特区间
思路：三指针
太套路了，这题，尤其在牛客上。
# 三指针就行
n = int(input())
arr = list(map(int, input().split()))
from collections import Counter
cnt1 = Counter()
cnt2 = Counter()
ptr1 = 0
ptr2 = 0
x1, x2 = 0, 0
res = 0
for i in range(n):
v = arr[i]
if cnt1[v] == 0:
x1 += 1
if cnt2[v] == 0:
x2 += 1
cnt1[v] += 1
cnt2[v] += 1
while ptr1 <= i and x1 > 3:
v1 = arr[ptr1]
if cnt1[v1] == 1:
x1 -= 1
cnt1[v1] -= 1
ptr1 += 1
while ptr2 <= i and x2 > 2:
v1 = arr[ptr2]
if cnt2[v1] == 1:
x2 -= 1
cnt2[v1] -= 1
ptr2 += 1
res += (ptr2 - ptr1)
print (res)
H. 小红的生物实验
思路： BFS
阅读理解题，有点绕，但是很板
h, w = list(map(int, input().split()))
chess = []
for _ in range(h):
chess.append(list(input()))
from collections import deque
vis = [[False] * w for _ in range(h)]
deq = deque()
for i in range(0, w):
if chess[0][i] == '.':
deq.append((0, i))
vis[0][i] = True
if chess[h - 1][i] == '.':
deq.append((h - 1, i))
vis[h - 1][i] = True
for i in range(1, h - 1):
if chess[i][0] == '.':
deq.append((i, 0))
vis[i][0] = True
if chess[i][w - 1] == '.':
deq.append((i, w - 1))
vis[i][w - 1] = True
while len(deq) > 0:
y, x = deq.popleft()
for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ty = y + dy
tx = x + dx
if 0 <= tx < w and 0 <= ty < h:
if vis[ty][tx]:
continue
if chess[ty][tx] == '.':
deq.append((ty, tx))
vis[ty][tx] = True
else:
vis[ty][tx] = True
for i in range(h):
for j in range(w):
if vis[i][j]:
chess[i][j] = '.'
for i in range(h):
print (''.join(chess[i]))
J. 小红种树（二）
思路: 枚举 + 区间gcd
区间gcd的性质为
枚举最终的高度x
那么可得
转换为
除了第一项，后面其实个是常量，可以预处理
为了应对负值的问题，可以把arr进行排序，从大到小排序。
最后的结果为 k的因子个数
n, m = list(map(int, input().split()))
# 考察区间gcd
arr = list(map(int, input().split()))
arr.sort(reverse=True)
from math import gcd
# 预处理区间gcd
g = 0
for i in range(1, n):
g = gcd(g, arr[i - 1] - arr[i])
# 预处理1000以内的质数
primes = []
vis = [False] * (1001)
for i in range(2, 1001):
if not vis[i]:
primes.append(i)
for j in range(i * i, 1001, i):
vis[j] = True
# 缓存优化
cache = {}
def compute(v):
cv = v
if v in cache:
return cache[v]
# 质因子拆解
res = 1
for i in range(len(primes)):
if cv < primes[i]:
break
if cv % primes[i] == 0:
cc = 0
while cv % primes[i] == 0:
cv = cv // primes[i]
cc += 1
res *= (cc + 1)
# 超过1000，最多一个质因子
if cv > 1:
res *= 2
cache[v] = res
return res
res = 0
for i in range(arr[0], m + 1):
gc = gcd(g, i - arr[0])
res += compute(gc)
print (res)
大疆公司氛围 168人发布
