2023年第6届传智杯省赛第二场复赛 解题报告 | 珂学家

---

前言

因为OJ的承办方是牛客，除了初赛用的原题有点争议外，复赛用的是原创的新题(点赞)。

说真的，这个难度，超过我的想象，打得非常的吃力。

我其实总共打了两场初赛，一场复赛，外加VP一场复赛，没有一场是AK的，很惭愧。

第二场复赛，T3卡了下，然后T4头痛，T5没找到线索，倒是T6一眼题，最后关头磨出了T4，真的太不容易，感谢自己的坚持。

---

A.

思路: 模拟

标准的签到题

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(), x = sc.nextInt();
        int res = 0;
        int pre = 0;
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            if (i > 0 && pre < x && v >= x) {
                res++;
            }
            pre = v;
        }
        System.out.println(res);
    }
    
}

---

B.

思路: 贪心

尽量挑选频数多的字母，尾巴需要额外处理下

因为 $x+y=a+b,x<a<b<y$
进而 $x^2+y^2>a^2+b^2$

所以大的就让它越大，这样整体就越大

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        // 需要替换为快读
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt(), k = sc.nextInt();
        int[] hash = new int[26];

        char[] str = sc.next().toCharArray();
        for (int i = 0; i < str.length; i++) {
            hash[str[i] - 'a']++;
        }

        long res = 0;
        Arrays.sort(hash);
        for (int i = 0; k > 0 && i < 26; i++) {
            int d = Math.min(k, hash[i]);
            res += (long)d * d;
            k -= d;
        }
        System.out.println(res);
    }

}

---

C.

思路: 枚举

找到所有不满足要求的相邻点

然后枚举被交换的位置，如果操作之后，会消灭点不满足要求的点，那么该点就是解。

这边有个结论
$$如果不满足的相邻点超过2个，那一定无解$$

这题挺容易错的，出的蛮好，很羡慕哪些秒杀这题的同学。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {

        // 预处理质数
        int MN = 2 * 10_0000;
        boolean[] vis = new boolean[MN + 1];
        vis[1] = false;
        for (int i = 2; i <= MN; i++) {
            if (!vis[i]) {
                if (i > MN / i) continue;
                for (int j = i * i; j <= MN; j+=i) {
                    vis[j] = true;
                }
            }
        }

        AReader sc = new AReader();
        int n = sc.nextInt();

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

        // 收集所有的坏点
        List<Integer> bads = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            if (vis[arr[i] + arr[i + 1]]) bads.add(i);
        }
        if (bads.size() > 2) {
            System.out.println(-1);
        } else {
            TreeSet<Integer> ans = new TreeSet<>();
            for (int v: bads) ans.add(v);

            // 模拟统计满足要求的点
            int res = -1;
            int exp = 0;
            for (int i = 0; i < n - 1; i++) {
                TreeSet<Integer> tmp = new TreeSet<>(ans);
                if (i > 0 && !vis[arr[i + 1] + arr[i - 1]]) tmp.remove(i - 1);
                if (i + 2 < n && !vis[arr[i + 2] + arr[i]]) tmp.remove(i + 1);
                if (tmp.size() == 0) {
                    res = i + 1;
                    exp++;
                }
            }

            System.out.println(exp == 1 ? res : -1);
        }
    }

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

}

---

D.

思路：枚举

$$有一个特例，就是重合的点数刚好为n$$

枚举两点(不重合)构建的一条直线，然后利用叉乘计算

• 直线上
• 直线左侧
• 直线右侧
  的点个数和分布，满足均分，就是所求的结果

是一道蛮数学化的题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class D {

    static class Key {
        int x, y;
        public Key(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return x * 1331 + y;
        }

        @Override
        public boolean equals(Object obj) {
            Key d = (Key)obj;
            return x == d.x && y == d.y;
        }
    }

    static class Line {
        int x, y;
        int x2, y2;
        int dx, dy;
        public Line(int x1, int y1, int x2, int y2) {
            // 直线的表达
            this.x = x1; this.y = y1;
            this.x2 = x2; this.y2 = y2;
            this.dx = x2 - x1;
            this.dy = y2 - y1;

            if (this.dx < 0) {
                this.dx = -this.dx;
                this.dy = -this.dy;
            }
        }

        boolean inLine(int px, int py) {
            int tx = px - x;
            int ty = py - y;

            if (tx < 0) {
                tx = -tx;
                ty = -ty;
            }

            if (dx == 0) {
                return tx == 0;
            }
            if (dy == 0) {
                return ty == 0;
            }
            return (long)dx * ty == (long)dy * tx;
        }

        boolean isLeft(int px, int py) {
            int dx1 = px - x, dy1 = py - y;
            int dx2 = x2 - x, dy2 = y2 - y;
            return dx1 * dy2 - dx2 * dy1 > 0;
        }

        long[] expr() {
            // y = dy/dx * x + c
            // c => y0 - dy/dx * x0
            if (dx == 0) {
                return new long[] {1, 0, -x};
            }
            if (dy == 0) {
                return new long[] {0, 1, -y};
            }
            return new long[] {dy, -dx, (long)y * dx - (long)dy * x};
        }

    }

    public static void main(String[] args) {

        AReader sc = new AReader();

        Map<Key, Integer> hash = new HashMap<>();
        int n = sc.nextInt();
        int m = 3 * n;
        int[][] ps = new int[m][2];
        for (int i = 0; i < m; i++) {
            ps[i][0] = sc.nextInt();
            ps[i][1] = sc.nextInt();
            hash.merge(new Key(ps[i][0], ps[i][1]), 1, Integer::sum);
        }

        Line ans = null;
        boolean found = false;
        // 这边进行枚举
        for (int i = 0; !found && i < m; i++) {
            for (int j = i + 1; !found && j < m; j++) {
                if (ps[i][0] == ps[j][0] && ps[i][1] == ps[j][1]) continue;

                Line line = new Line(ps[i][0], ps[i][1], ps[j][0], ps[j][1]);
                int n0 = 2, n1 = 0, n2 = 0;
                for (int k = 0; k < m; k++) {
                    if (k == i || k == j) continue;
                    if (line.inLine(ps[k][0], ps[k][1])) n0++;
                    else if (line.isLeft(ps[k][0], ps[k][1])) n1++;
                    else n2++;
                }
                if (n0 == n1 && n1 == n2) {
                    found = true;
                    ans = line;
                }
            }
        }

        if (ans == null) {
            // 存在一个特例
            for (Map.Entry<Key, Integer> kv : hash.entrySet()) {
                if (kv.getValue() == n) {
                    int sx = kv.getKey().x;
                    int sy = kv.getKey().y;
                    // 黑洞点
                    for (int i = -2000; i <= 2000; i++) {
                        Line tmp = new Line(sx, sy, sx + 1, sy + i);

                        int left = 0, right = 0;
                        for (int k = 0; k < m; k++) {
                            if (ps[k][0] == sx && ps[k][1] == sy) continue;
                            if (tmp.isLeft(ps[k][0], ps[k][1])) left++;
                            else right++;
                        }
                        if (left == right) {
                            ans = tmp;
                            break;
                        }
                        left = 0;
                        right = 0;
                        tmp = new Line(sx, sy, sx + i, sy + 1);
                        for (int k = 0; k < m; k++) {
                            if (ps[k][0] == sx && ps[k][1] == sy) continue;
                            if (tmp.isLeft(ps[k][0], ps[k][1])) left++;
                            else right++;
                        }
                        if (left == right) {
                            ans = tmp;
                            break;
                        }
                    }
                    break;
                }
            }
        }
        if (ans == null) {
            System.out.println(-1);
        } else {
            long[] cur = ans.expr();
            System.out.println(cur[0] + " " + cur[1] + " " + cur[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());
        }
    }

}

---

E.

完全没思路，蒙了

---

F.

思路：字符串hash + 线段树

综合题，但是比较简单

这边可以借助双hash，来构建，避免碰撞带来的WA.

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

public class F {

    static long mod = (long)1e9 + 7;
    static long p1 = 13;
    static long p2 = 17;

    static final int MZ = 100_00000;
    static long[] dp1 = new long[MZ + 1];
    static long[] dp2 = new long[MZ + 1];

    public static void setUp() {
        dp1[0] = dp2[0] = 1;
        for (int i = 1; i < MZ; i++) {
            dp1[i] = dp1[i - 1] * p1 % mod;
            dp2[i] = dp2[i - 1] * p2 % mod;
        }
    }

    // 线段树
    static class SegTree {
        int l, r;
        SegTree left, right;
        int v;
        long h1, h2;

        public SegTree(char[] str, int l, int r) {
            this.l = l;
            this.r = r;
            if (l == r) {
                this.v = str[l] - 'a';
                h1 = v % mod;
                h2 = v % mod;
                return;
            } else {
                int m = l + (r - l) / 2;
                left = new SegTree(str, l, m);
                right = new SegTree(str, m + 1, r);
                pushup();
            }
        }

        public void update(int p, char c) {
            if (isLeaf()) {
                this.v = c - 'a';
                h1 = v % mod;
                h2 = v % mod;
                return;
            }

            int m = l + (r - l) / 2;
            if (p <= m) {
                this.left.update(p, c);
            } else {
                this.right.update(p, c);
            }
            pushup();
        }

        long query1(int ql, int qr) {
            if (isLeaf()) {
                return this.h1;
            }
            if (ql <= l && qr >= r) {
                return this.h1;
            }

            int m = l + (r - l) / 2;
            long lh = 0;
            if (ql <= m) {
                lh = this.left.query1(ql, Math.min(m, qr));
            }
            long rh = 0;
            if (qr > m) {
                rh = this.right.query1(Math.max(m +1, ql), qr);
            }

            int d = Math.max(0, qr - m);
            return (lh * dp1[d] + rh) % mod;
        }

        long query2(int ql, int qr) {
            if (isLeaf()) {
                return this.h2;
            }
            if (ql <= l && qr >= r) {
                return this.h2;
            }

            int m = l + (r - l) / 2;
            long lh = 0;
            if (ql <= m) {
                lh = this.left.query2(ql, Math.min(m, qr));
            }
            long rh = 0;
            if (qr > m) {
                rh = this.right.query2(Math.max(m +1, ql), qr);
            }

            int d = Math.max(0, qr - m);
            return (lh * dp2[d] + rh) % mod;
        }

        public void pushup() {
            int m = l + (r - l) / 2;
            h1 = (left.h1 * dp1[r - m] % mod + right.h1) % mod;
            h2 = (left.h2 * dp2[r - m] % mod + right.h2) % mod;
        }

        boolean isLeaf() {return l== r;}

    }

    public static void main(String[] args) {

        setUp();

        AReader sc = new AReader();

        int n = sc.nextInt();
        int q = sc.nextInt();
        char[] str = sc.next().toCharArray();

        SegTree root = new SegTree(str, 0, n - 1);

        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();
            if (op == 1) {
                int x = sc.nextInt() - 1;
                char c = sc.next().charAt(0);
                root.update(x, c);
            } else if (op == 2) {
                int l1 = sc.nextInt() - 1, r1 = sc.nextInt() - 1;
                int l2 = sc.nextInt() - 1, r2 = sc.nextInt() - 1;
                if (root.query1(l1, r1) == root.query1(l2, r2) && root.query2(l1, r1) == root.query2(l2, r2)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            }
        }
    }

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

}

---

写在最后