牛客周赛 Round 51 解题报告

前言

alt

题解

典题场， EF都有很多种解法

A. 小红的同余

性质: 相邻两数互质

$x = (m + 1) /2$

m = int(input())

print ((m + 1) // 2)

B. 小红的三倍数

性质: 各个位数之和是3的倍数，可被3整除

和数的组合顺序无关

n = int(input())
arr = list(map(int, input().split()))

res = 0
for v in arr:
    while v > 0:
        res += v % 10
        v //= 10

if res %3 == 0:
    print ("YES")
else:
    print ("NO")

C. 小红充电

思路: 分类讨论题

要注意的是，可以通过耗电回撤到超级快充的状态

x, y, t, a, b, c = list(map(int, input().split()))

if x <= t:
    r = min((100 - x) / c, (100 - x) / a, (100 - x) / b)
    print ("%.8f" % (r))
else:
    r = min((100 - x) / a, (100 - x) / b, (x - t) / y + (100 - t) / c)
    print ("%.8f" % (r))

D. 小红的 gcd

因为a是一个大数

所以从gcd的推演公式切入

$g c d (a, b) = g c d (b, a$

可以迭代线性遍历a，来求解a%b的值

然后在求gcd(a%b, b)

a = input()
b = int(input())

r = 0
for c in a:
    p = ord(c) - ord('0')
    r = (r * 10 + p) % b
    
from math import gcd

print (gcd(r, b))

E. 小红走矩阵

方法1: 并查集

方法2: 二分+bfs

方法3: dijkstra

这边给了并查集的思路，即按权值从小到大合并，直至(0,0)和(n-1,m-1)连通.

class Dsu(object):
    def __init__(self, n) -> None:
        self.n = n
        self.arr = [-1] * n
    def find(self, u):
        if self.arr[u] == -1:
            return u
        self.arr[u] = self.find(self.arr[u])
        return self.arr[u]
    def merge(self, u, v):
        a, b = self.find(u), self.find(v)
        if a != b:
            self.arr[a] = b
            

n = int(input())

vis = [[False] * n for _ in range(n)]
ops = []
grid = []
for i in range(n):
    row = list(map(int, input().split()))
    grid.append(row)
    for j in range(n):
        ops.append((row[j], i, j))

ops.sort(key=lambda x: x[0])

ans = 0
dsu = Dsu(n * n)
for (v, y, x) in ops:
    vis[y][x] = True
    for (dy, dx) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        ty, tx = y + dy, x + dx
        if 0 <= ty < n and 0 <= tx < n:
            if vis[ty][tx]:
                dsu.merge(y * n + x, ty * n + tx)
    if dsu.find(0) == dsu.find(n * n - 1):
        ans = v
        break
        
print (ans)

F. 小红的数组

思路: ST表

这题思路应该蛮多的

有在线解法，离线解法

最直观的

$区间子数组的绝对值最大和，是区间前缀和的最大值 - 区间前缀和的最小值$

前缀和
RMQ(区间最大/最小)

莫队板子也可以的

import java.io.*;
import java.util.StringTokenizer;
import java.util.function.BiFunction;
 
public class Main {

    public static void main(String[] args) {
        AReader sc = new AReader();
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i]+arr[i];
 
        SparesTable maxSt = new SparesTable(pre, Math::max);
        SparesTable minSt = new SparesTable(pre, Math::min);
 
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1, r = sc.nextInt();
            long res = maxSt.query(l, r) - minSt.query(l, r);
            pw.println(res);
        }
        pw.flush();
    }
 
    static
    class SparesTable {
 
        long[][] tables;
        BiFunction<Long, Long, Long> callback;
 
        public SparesTable(long[] arr, BiFunction<Long, Long, Long> callback) {
            int n = arr.length;
            int m = (int)(Math.log(n) / Math.log(2) + 1);
            tables = new long[m][n];
            this.callback = callback;
 
            for (int i = 0; i < n; i++) {
                tables[0][i] = arr[i];
            }
            for (int i = 1; i < m; i++) {
                int half = 1 << (i - 1);
                for (int j = 0; j + half < n; j++) {
                    tables[i][j] = callback.apply(tables[i - 1][j], tables[i - 1][j + half]);
                }
            }
        }
 
        // 闭闭区间
        long query(int l, int r) {
            int t = (int)(Math.log(r - l + 1) / Math.log(2));
            return callback.apply(tables[t][l], tables[t][r - (1 << t) + 1]);
        }
 
    }
 
    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        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());
        }
        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;
        }
    }
 
}