牛客周赛 Round 1 解题报告 | 珂学家 | 分类计数 + 同余DP

发布时间:2024年01月13日

前言

生于生时,亡于亡刻。遵从自心,尽人之事。


整体评价

终于等来了侧重面试的比赛,而且题量刚刚好,不超纲,不涉及算法竞赛。

第一场的比赛,感觉题目出的比较典,A是简单模拟,B则是计数题,C则是贪心思路,D是经典的同余DP。

唯一吐槽的是,牛客好像当前只JDK 8, 用不了var.


欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏


A. 游游画U

找规律题吧,就是找到底托,中间对等分开,然后往两边靠齐。

而N,则限定了最终图的长宽高,还有就是‘*’的长度

import java.io.BufferedInputStream;
import java.util.Arrays;
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();
        
        // 定义结果的画布
        char[][] res = new char[4 * n][4 * n];
        
        // 前面的3*n行
        for (int i = 0; i < 3 * n; i++) {
            Arrays.fill(res[i], '.');
            for (int j = 0; j < n; j++) {
                res[i][j] = res[i][4*n - 1 - j] = '*';
            }
        }
        
        // 最下面的n行
        for (int i = 3 * n; i < 4 * n; i++) {
            int offset = i + 1 - 3 * n;
            Arrays.fill(res[i], '.');
            for (int j = 0; j < n; j++) {
                res[i][offset + j] = res[i][4 * n - 1 - offset - j] = '*';
            }
        }
        
        // 输出内容
        for (int i = 0; i < 4 * n; i++) {
            System.out.println(new String(res[i]));
        }


    }

}

B. 游游的数组染色

先按同值进行分类,然后内部按颜色进行计数

m a p [ v a l u e ] [ c o l o r ] {map[value][color]} map[value][color]

那最终的结果为

∑ v i ∑ c j ∈ C m a p [ v i ] [ c j ] ? ( ∑ k ∈ C m a p [ v i ] [ c k ] ? m a p [ v i ] [ c j ] ) \sum_{v_i} \sum_{c_j \in C} map[v_i][c_j] * (\sum_{k\in C} map[v_i][c_k] - map[v_i][c_j]) vi??cj?C?map[vi?][cj?]?(kC?map[vi?][ck?]?map[vi?][cj?])

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        AReader sc = new AReader();
        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();

        Map<Integer, TreeMap<Character, Integer>> range = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!range.containsKey(arr[i])) {
                range.put(arr[i], new TreeMap<>());
            }
            range.get(arr[i]).merge(str[i], 1, Integer::sum);
        }

        long ans = 0;
        for (Map.Entry<Integer, TreeMap<Character, Integer>> kv: range.entrySet()) {
            TreeMap<Character, Integer> ts = kv.getValue();
            long acc = 0;
            for (Map.Entry<Character, Integer> kv2: ts.entrySet()) {
                acc += kv2.getValue();
            }

            for (Map.Entry<Character, Integer> kv2: ts.entrySet()) {
                ans += (long)(acc - kv2.getValue()) * kv2.getValue();
            }
        }

        System.out.println(ans / 2);
    }

    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());
        }
        
    }

}

#include <bits/stdc++.h>

using namespace std;

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    string s;
    cin >> s;
    map<int, int> h1, h2;
    for (int i = 0; i< n; i++) {
        char c = s[i];
        if (c == 'B') {
            h2[arr[i]]++;
        } else {
            h1[arr[i]]++;
        }
    }
    
    long long res = 0LL;
    for (auto iter = h1.begin(); iter != h1.end();  iter++) {
        if (h2.find(iter->first) != h2.end()) {
            res += (long long)h2[iter->first] * (iter->second);
        }
    }
    cout << res << endl;
    
    return 0;
}

C. 游游的交换字符

分类讨论,即构造1开头的串,和0开头的串,两者那个代价小。

一旦确定分头,实际上代价就定下来,重要的是如何计算。

比如当前串,以及构建好了’01…1’, 你要寻找下一个‘0’, 则需要多少代价呢?

这个时候,就是从原串中,下一个‘0’之前有几个’1’呢

同理,‘1’也是统计前置几个‘0’

那这个动态有变动的统计0-1该怎么处理呢?

我们可以尝试引入 0-1 树状数组

就是有一个单独统计‘1’的位置的树状数组,一个统计‘0’的树状数组

前置的01构建完后,就删掉对应的01位置即可。

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

public class Main {

    static class BIT {
        int n;
        int[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new int[n + 1];
        }
        void update(int p, int d) {
            while (p <= n) {
                arr[p] += d;
                p += p & -p;
            }
        }
        int query(int p) {
            int res = 0;
            while (p > 0) {
                res += arr[p];
                p -= p & -p;
            }
            return res;
        }
    }

    // *)
    public static long solve(char[] buf, char s) {
        // 找到最近的0
        int n = buf.length;
        BIT bit0 = new BIT(n);
        BIT bit1 = new BIT(n);

        List<Integer> list0 = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (buf[i] == '0') {
                list0.add(i + 1);
                bit0.update(i + 1, 1);
            } else {
                list1.add(i + 1);
                bit1.update(i + 1, 1);
            }
        }

        long ans = 0l;

        if (s == '0') {
            if (list0.size() < list1.size()) return Long.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    int idx = list0.get(i/2);
                    int delta = bit1.query(idx);
                    bit0.update(idx, -1);

                    ans += delta;
                } else {
                    int idx = list1.get(i/2);
                    int delta = bit0.query(idx);
                    bit1.update(idx, -1);
                    ans += delta;
                }
            }

        } else {

            if (list1.size() < list0.size()) return Long.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    int idx = list1.get(i/2);
                    int delta = bit0.query(idx);
                    bit1.update(idx, -1);

                    ans += delta;
                } else {
                    int idx = list0.get(i/2);
                    int delta = bit1.query(idx);
                    bit0.update(idx, -1);
                    ans += delta;
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        char[] buf = sc.next().toCharArray();

        long res = Math.min(solve(buf.clone(), '0'), solve(buf.clone(), '1'));

        System.out.println(res);
    }

}

不过这个解法,应该是写复杂了。

直接贪心即可

就是 ∑ i = 0 i = ( n + 1 ) / 2 ( c u r r e n t i ? e x p e c t i ) {\sum_{i=0}^{i=(n+1)/2} (current_i - expect_i)} i=0i=(n+1)/2?(currenti??expecti?)

c u r r e n t i 是第 i 个 1 所在的位子, e x p e c t i 是被期望的位子 current_i是第i个1所在的位子,expect_i是被期望的位子 currenti?是第i1所在的位子,expecti?是被期望的位子

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

public class Main {

    // *)
    public static long solve(char[] buf, char s) {
        // 找到最近的0
        int n = buf.length;
        
        List<Integer> list0 = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (buf[i] == '0') {
                list0.add(i);
            } else {
                list1.add(i);
            }
        }

        long ans = 0l;

        if (s == '0') {
            if (list0.size() < list1.size()) return Long.MAX_VALUE;
            for (int i = 0; i < list0.size(); i++) {
                ans += Math.abs(2 * i - list0.get(i)); 
            }
        } else {
            if (list1.size() < list0.size()) return Long.MAX_VALUE;
            for (int i = 0; i < list1.size(); i++) {
                ans += Math.abs(2 * i - list1.get(i)); 
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        char[] buf = sc.next().toCharArray();

        long res = Math.min(solve(buf.clone(), '0'), solve(buf.clone(), '1'));

        System.out.println(res);
    }

}
#include <bits/stdc++.h>

using namespace std;

struct FastIO {
    FastIO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }
}_fastIo;


int main() {
    string s;
    cin >> s;
    
    int n = s.length();
    vector<int> list0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') list0.push_back(i);
    }
    
    long long cost = 0x3f3f3f3f;
    if (n % 2 == 0) {
        if (list0.size() == n / 2) {
            long long tmp1 = 0, tmp2 = 0;
            for (int i = 0; i < n / 2; i++) {
                tmp1 += abs(list0[i] - (i * 2));   
                tmp2 += abs(list0[i] - (i * 2 + 1));
            }
            cost = min(tmp1, tmp2);
        }
    } else {
        if (list0.size() == n / 2 + 1) {
            long long tmp1 = 0;
            for (int i = 0; i < n / 2 + 1; i++) {
                tmp1 += abs(list0[i] - (i * 2));   
            }
            cost = tmp1;
        } else if (list0.size() == n / 2) {
            long long tmp2 = 0;
            for (int i = 0; i < n / 2; i++) {
                tmp2 += abs(list0[i] - (i * 2 + 1));
            }
            cost = tmp2;
        }
    }

    cout << cost << endl;
    
    return 0;
}

D. 游游的9的倍数

经典的同余DP

因为求的是9的倍数,而数字串前缀 S i = a 0 a 1 . . . a i = b 0 ? 9 x + b 1 ? 9 x ? 1 . . . + b i ? 9 0 S_i = a_0a_1...a_i = b_0 * 9^x + b_1 * 9^{x-1}... + b_i * 9^0 Si?=a0?a1?...ai?=b0??9x+b1??9x?1...+bi??90

S i a i + 1 = 10 ? b 0 ? 9 x + 10 ? b 1 ? 9 x ? 1 . . . + 10 ? b i ? 9 0 + a i + 1 = 10 ? b i + a i + 1 S_ia_{i+1} = 10 * b_0 * 9^x + 10 * b_1 * 9^{x-1}... + 10 * b_i * 9^0 + a_{i+1} = 10 * b_i + a_{i+1} Si?ai+1?=10?b0??9x+10?b1??9x?1...+10?bi??90+ai+1?=10?bi?+ai+1?

所以我们令

o p t [ i ] [ j ] , 前 i 元素中,构建对 9 余数为 j 的总个数 opt[i][j], 前i元素中,构建对9余数为j的总个数 opt[i][j],i元素中,构建对9余数为j的总个数

状态转移为

o p t [ i + 1 ] [ ( j ? 10 + a i + 1 ) % 9 ] = o p t [ i ] [ ( j ? 10 + a i + 1 ) % 9 ] + o p t [ i ] [ j ] {opt[i+1][(j*10+a_{i+1}) \% 9] = opt[i][(j*10+a_{i+1})\%9] + opt[i][j]} opt[i+1][(j?10+ai+1?)%9]=opt[i][(j?10+ai+1?)%9]+opt[i][j]

当然这边对空集合的处理,有个小技巧,就是单独加1

o p t [ i + 1 ] [ a i + 1 % 9 ] + = 1 opt[i+1][a_{i+1}\%9] += 1 opt[i+1][ai+1?%9]+=1

可以借助滚动数组来优化DP的空间

复杂度分析,时间 O ( 9 ? n ) O(9*n) O(9?n), 空间复杂度为 O ( 20 ) O(20) O(20)

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        char[] buf = sc.next().toCharArray();

        long mod = 10_0000_0007l;
        long[][] opt = new long[2][9];
        opt[0][0] = 0l;

        int prev = 0, next = 1;
        for (int i = 0; i < buf.length; i++) {
            int p = buf[i] - '0';

            // 添加/不添加
            Arrays.fill(opt[next], 0);

            for (int j = 0; j < 9; j++) {
                opt[next][j] = opt[prev][j];
            }
            for (int j = 0; j < 9; j++) {
                opt[next][(j * 10 + p) % 9] += opt[prev][j];
                opt[next][(j * 10 + p) % 9] %= mod;
            }

            opt[next][p % 9] = (opt[next][p % 9] + 1) % mod;

            prev = 1 - prev;
            next = 1 - next;
        }

        System.out.println(((opt[prev][0]) % mod + mod) % mod);

    }


}
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
    
    string s;
    cin >> s;
    
    int64 mod = 1'000'000'000 + 7;
    


    int64 dp[2][9];
    memset(dp[0], 0, sizeof(dp[0]));
    
    
    int prev = 0, next = 1;
    for (int i = 0; i < s.length(); i++) {
        memset(dp[next], 0, sizeof(dp[next]));
        char c = s[i];
        
        int d = c - '0';
        for (int j = 0; j < 9; j++) {
            dp[next][j] = (dp[next][j] + dp[prev][j]) % mod;
            dp[next][(j + d) % 9] = (dp[next][(j + d) % 9] + dp[prev][j]) % mod;
        }
        
        dp[next][d % 9] = (dp[next][d % 9] + 1) % mod;
        
        prev = 1 - prev;
        next = 1 - next;
    }
    
    cout << dp[prev][0] << endl;

    return 0;
}

如果9是个变量k,那其实也是同一种套路。

如果此题不用DP,能否解呢? 感觉有,因为9做为除数比较特殊,它打破了字符串的顺序限制。


写在最后

没有绝对的善意,关切的目光中也会掺杂恶意的期待。

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_66102593/article/details/135567228
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。