前言

alt

整体评价

整场还是挺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. 小苯的三元组

思路: 调和级数

$lcm(a_i, a_j) \le gcd(a_j, a_k)$

推导 $a_j \le lcm(a_i, a_j) \le gcd(a_j, a_k) \le a_j$

说明 $a_i \le a_j \le a_k$ , 且满足 $a_i | a_j, a_j | a_k$

所以这题的思路，就是维护每个数的因子个数和倍数个数

调和级数 $O(mlogm)$

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的性质为

$gcd(a, b, c, ..., z) = gcd(a, b - a, c - b, ..., z - y)$

枚举最终的高度x

那么可得

$k = gcd(x - arr[0], x - arr[1], ..., x - arr[n - 1])$

转换为

$k = gcd(x - arr[0], arr[0] - arr[1], ..., arr[n - 2] - arr[n - 1])$

除了第一项，后面其实个是常量，可以预处理

为了应对负值的问题，可以把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)

写在最后

alt

2024年中国传媒大学程序设计大赛（同步赛）解题报告(流水账版) | 珂学家

前言

整体评价

写在最后