牛客周赛 Round 25 解题报告 | 珂学家 | 猜猜乐 + 换根

小红购物

https://ac.nowcoder.com/acm/contest/72266/A

前言

alt

整体评价

思维场吧，T3印象深刻，其实我不会做，我就是猜的，到现在都不知道怎么过的，惭愧。

T4是换根模板题，也就这样了。

欢迎关注

珂朵莉牛客周赛专栏

珂朵莉牛客小白月赛专栏

A. 小红购物

思路: 模拟

java
python

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        char[] str = sc.next().toCharArray();

        long res = 0;
        for (int i = 0; i< n; i++) {
            if (str[i] == 'T') {
                res += arr[i];
            } else {
                res += Math.max(5, arr[i] / 100);
            }
        }
        System.out.println(res);
    }
}

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

s = input()

res = 0
for i in range(n):
    if s[i] == 'T':
        res += arr[i]
    else:
        res += max(5, arr[i] // 100)
        
print (res)

B. 小红吃桃

思路: 贪心

算思维题吧，就是大的和大的组合，小的和小的组合，这样整体一定是最大，乘积效应吧

java
python

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        long mod = (long)1e9 + 7;

        long[] a = new long[n];
        for (int i = 0; i < n ;i++) {
            a[i] = sc.nextInt();
        }
        long[] b = new long[n];
        for (int i = 0; i < n ;i++) {
            b[i] = sc.nextInt();
        }

        long r1 = 1, r2 = 1;
        for (int i = 0; i < n; i++) {
            if (a[i] >= b[i]) {
                r1 = r1 * a[i] % mod;
                r2 = r2 * b[i] % mod;
            } else {
                r1 = r1 * b[i] % mod;
                r2 = r2 * a[i] % mod;
            }
        }

        System.out.println((r1 + r2) % mod);
    }
}

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

mod = 10 ** 9 + 7
c, d = 1, 1

for i in range(n):
    if arr[i] >= brr[i]:
        c = c * arr[i] % mod
        d = d * brr[i] % mod
    else:
        c = c * brr[i] % mod
        d = d * arr[i] % mod
        
print ((c + d) % mod)

C. 小红的踏前斩

思路: 贪心

其实我更愿意是DP，但是值域真的太大的。

所以从哪里切入呢？

一开始从开头无脑贪，WA

然后想是不是从峰值点，处理，感觉收敛太慢了。

后来，想了想，要不逆向思维，从后往前贪心，哈哈，蒙对了。

java
python

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }

        // 逆向贪心
        long res = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i >= 2) {
                long d1 = arr[i] / 3, d2 = arr[i - 1] / 2, d3 = arr[i - 2];
                long md = Math.min(d1, Math.min(d2, d3));
                res += md * 5l;

                arr[i] -= 3 * md;
                arr[i - 1] -= md * 2l;
                arr[i - 2] -= md;
            }
            res += arr[i];
        }

        System.out.println(res);
    }
    
}

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

res = 0
for i in range(n - 1, -1, -1):
    if i - 2 >= 0:
        m = min(arr[i] // 3, arr[i - 1] // 2, arr[i - 2])
        
        res += 5 * m
        arr[i] -= 3 * m
        arr[i - 1] -= 2 * m
        arr[i - 2] -= m
    res += arr[i]
    
print (res)

D. 小红树

思路：换根DP

从换根的角度出发，然后在每条边上，处理边两侧的连通数差值

java
python

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    // 换根板子
    static class Solution {
        int n;
        List<Integer> []g;
        char[] colors;

        long[] dp1;
        long gAns = 0;

        long solve(int n, List<Integer> []g, char[] colors) {
            this.g = g;
            this.n = n;
            this.colors = colors;

            dp1 = new long[n];
            dfs1(0, -1);
            dfs2(0, -1, 0);
            return gAns;
        }

        void dfs1(int u, int fa) {
            int res = 1;
            for (int v: g[u]) {
                if (v == fa) continue;
                dfs1(v, u);
                if (colors[u] == colors[v]) {
                    res += dp1[v] - 1;
                } else {
                    res += dp1[v];
                }
            }
            dp1[u] = res;
        }

        void dfs2(int u, int fa, long w) {
            long tmp = dp1[u];
            if (fa != -1) {
                if (colors[u] ==  colors[fa]) {
                    tmp += w - 1;
                } else {
                    tmp += w;
                }
            }
            for (int v: g[u]) {
                if (v == fa) continue;
                long ctmp = tmp;
                if (colors[u] == colors[v]) {
                    ctmp -= (dp1[v] - 1);
                } else {
                    ctmp -= dp1[v];
                }
                gAns += Math.abs(ctmp - dp1[v]);
                dfs2(v, u, ctmp);
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();

        char[] str = sc.next().toCharArray();
        List<Integer>[]g = new List[n];
        Arrays.setAll(g, x->new ArrayList<>());

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
            g[u].add(v);
            g[v].add(u);
        }

        Solution solution = new Solution();
        long res = solution.solve(n, g, str);
        System.out.println(res);
    }

}

from types import GeneratorType

# 递归栈优化
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc


n = int(input())
s = " " + input()

g = [[] for _ in range(n + 1)]

for i in range(n - 1):
    u, v = list(map(int, input().split()))
    g[u].append(v)
    g[v].append(u)
    

dp = [0] * (n + 1)
depth = [0] * (n + 1)

@bootstrap
def dfs(u: int, fa: int, d: int):
    depth[u] = d
    res = 1
    for v in g[u]:
        if v == fa:
            continue
        yield dfs(v, u, d + 1)
        if s[u] == s[v]:
            res += dp[v] - 1
        else:
            res += dp[v]
    dp[u] = res
    yield
    
dfs(1, -1, 1)

ans = 0
for i in range(1, n + 1):
    for v in g[i]:
        if depth[v] > depth[i]:
            if s[i] == s[v]:
                ans += abs(dp[1] - dp[v] + 1 - dp[v])
            else:
                ans += abs(dp[1] - dp[v] - dp[v])
                
print (ans)