Codeforces#811 Div3 题解

D. Color with Occurrences

You are given some text t and a set of n strings .

In one step, you can choose any occurrence of any string in the text and color the corresponding characters of the text in red. For example, if and , , you can get , or in one step.

You want to color all the letters of the text t in red. When you color a letter in red again, it stays red.

In the example above, three steps are enough:

• Let’s color in red, we get ;
• Let’s color in red, we get ;
• Let’s color in red, we get .
  Each string can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.

Determine the minimum number of steps needed to color all letters t in red and how to do it. If it is impossible to color all letters of the text t in red, output -1.

Input

The first line of the input contains an integer —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains the text , consisting only of lowercase Latin letters, where is the length of the text t.

The second line of each test case contains a single integer — the number of strings in the set.

This is followed by n lines, each containing a string consisting only of lowercase Latin letters, where — the length of string .

Output

For each test case, print the answer on a separate line.

If it is impossible to color all the letters of the text in red, print a single line containing the number -1.

Otherwise, on the first line, print the number m — the minimum number of steps it will take to turn all the letters t red.

Then in the next m lines print pairs of indices: and , which denote that the string with index was used as a substring to cover the occurrences starting in the text t from position . The pairs can be output in any order.

If there are several answers, output any of them.

解法一

题目核心其实是一个区间覆盖的问题，每个 在 中能匹配上的部分就是一个区间，题目求的就是用最少的区间去覆盖整个 。所以我们按照贪心的思路，从开始找到能overlap右边界的最大区间，然后更新右边界，最后覆盖完所有的区间，得到的就是最少的覆盖次数。在过程中记录下区间信息，输出步骤即可。

代码实现如下：

import java.util.*;
import java.io.*;

// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class D {
    public static void main(String[] args) throws Exception {
        // 输入重定向，通过jvm参数判断环境
        if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
            System.setIn(new FileInputStream("./input.txt"));
        }
        new Main().main(args);
    }
}

class Main {

    public static void main(String[] args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Q = read(br)[0];
        while (Q-- > 0) {
            String t = br.readLine();
            int n = read(br)[0];
            // match[i]: t第i个位置最远能匹配到哪里
            var match = new int[t.length()][2];

            String[] s = new String[n];
            for (int i = 0; i < n; i++) {
                s[i] = br.readLine();
                // 预处理每个s[i]在t中能匹配的位置
                for (int j = 0; j < t.length(); j++) {
                    var flag = true;
                    for (int k = 0; k < s[i].length(); k++) {
                        if (j + k >= t.length() || t.charAt(j+k) != s[i].charAt(k)) {
                            flag = false;
                            break;
                        }
                    }
                    if (!flag) continue;
                    if (match[j][1] <= s[i].length() + j) {
                        match[j] = new int[]{i, s[i].length() + j};
                    }
                }
            }
            // 下一次开始匹配的位置
            var last = 0;
            var flag = true;
            var cnt = 0;
            var lis = new ArrayList<String>();
            while (last < t.length()) {
                var temp = last;
                int w = 0, p = 0;
                for (int i = 0; i <= temp; i++) {
                    if (match[i][1] >= last) {
                        last = match[i][1];
                        w = match[i][0]+1;
                        p = i+1;
                    }
                }
                // 没有能cover last的区间
                if (last == temp) {
                    flag = false;
                    break;
                }
                cnt++;
                lis.add(w + " " + p);
            }
            if (flag) {
                out.println(cnt);
                lis.stream().forEach(out::println);
            } else {
                out.println(-1);
            }

        }
        out.flush();
    }


    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

E. Add Modulo 10

You are given an array of n integers

You can apply the following operation an arbitrary number of times:

• select an index and replace the value of the element with the value , where is the remainder of the integer dividing by .

For a single index (value ), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of is taken into account each time. For example, if then after the first operation we get , and after the second operation we get .

Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.

For example, you have an array .

• Let’s apply this operation to the first element of the array. Let’s replace with . We get the array .
• Then apply this operation to the second element of the array. Let’s replace with . We get the array .

Thus, by applying 2 operations, you can make all elements of an array equal.

Input

The first line contains one integer — the number of test cases. What follows is a description of each test case.

The first line of each test case contains one integer — the size of the array.

The second line of each test case contains n integers — array elements.

It is guaranteed that the sum of n over all test cases does not exceed .

Output

For each test case print:

• YES if it is possible to make all array elements equal;
• NO otherwise.

You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .

解法一

找规律，题目大意是给定一组数组，尝试替换为，问能否是的数组所有元素相等。

我们可以将元素替换序列都列出来，然后找规律，进行分组，具体见代码：

import java.util.*;
import java.io.*;

// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class E {
    public static void main(String[] args) throws Exception{
        // 输入重定向，通过jvm参数判断环境
        if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
            System.setIn(new FileInputStream("./input.txt"));
        }
        new Main().main(args);
    }
}

class Main {

    // 1  2  4  8  16  22  24  28  36  42  44 ...
    // 3  6  12 14  18  26  32  34  38  46  52 ...
    // 5  10 10 10 ....
    // 15 20 20 20 ...
    // 7 14 18 26 ....
    // 9 18
    public static void main(String[] args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = read(br)[0];
        // 分析发现20为一个循环，我们将20以内的元素进行分组，两组元素序列完全平行，无法相交
        // 所以如果元素 mod 20在同一组中，那么就一定可以转化成一样的，否则一定不行
        // 除此之外，需要额外注意5和0结尾的元素，它们最多只能转化一次，所以如果有5/0结尾的元素，那么所有元素都必须是5/0结尾，且5结尾经过转换后与0结尾相同
        var s1 = new HashSet<>();
        s1.add(1); s1.add(2); s1.add(4); s1.add(8); s1.add(13); s1.add(16); s1.add(17); s1.add(19);
        var s2 = new HashSet<>();
        s2.add(3); s2.add(6); s2.add(7); s2.add(9); s2.add(11); s2.add(12); s2.add(14); s2.add(18); 
        while (T-- > 0) {
            read(br);
            var a = read(br);
            var set5 = new HashSet<Integer>();
            var cnt5 = 0;

            var ins1 = false;
            var ins2 = false;
            for (Integer v : a) {
                if (v%10 == 5 || v%10 == 0) {
                    cnt5++;
                    set5.add(v + v%10);
                }
                if (s1.contains(v%20)) {
                    ins1 = true;
                }
                if (s2.contains(v%20)) {
                    ins2 = true;
                }
            }
            // 既有s1中的元素，又有s2中的元素 || 有5/0结尾的但是不全是 || 全是5/0结尾的，但是转换后不想等
            if ((ins2 && ins1) || (cnt5 != 0 && cnt5 != a.length) || (cnt5 == a.length && set5.size() != 1)) {
                out.println("No");
            } else {
                out.println("Yes");
            }
        }
        out.flush();
    }


    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

G. Path Prefixes

You are given a rooted tree. It contains vertices, which are numbered from to . The root is the vertex .

Each edge has two positive integer values. Thus, two positive integers and are given for each edge.

Output numbers , where $r_i is defined as follows.

Consider the path from the root (vertex ) to . Let the sum of the costs of along this path be . Then is equal to the length of the maximum prefix of this path such that the sum of along this prefix does not exceed .

… 题目太长，懒得copy，去看原题吧

解法一

dfs栈上二分，如果这题放在D或者E我肯定能写出来，放在后面并且题目这么长，让人有点畏惧，不过说到底还是太菜了。

import java.util.*;
import java.io.*;

// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class G {
    public static void main(String[] args) throws Exception{
        // 输入重定向，通过jvm参数判断环境
        if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
            System.setIn(new FileInputStream("./input.txt"));
        }
        new Main().main(args);
    }
}

class Main {

    static int idx;
    static int[] e, ne, h, wa, wb;
    static int si;
    static long[] stack;
    static int[] res;

    public static void add(int a, int b, int i, int j) {
        e[idx] = b; ne[idx] = h[a];
        wa[idx] = i; wb[idx] = j;
        h[a] = idx++;
    }

    public static void main(String[] args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = read(br)[0];
        while (T-- > 0) {
            int N = read(br)[0];
            
            idx = 0;   
            h = new int[N+1]; Arrays.fill(h, -1);
            e = new int[N+1]; ne = new int[N+1];
            wa = new int[N+1]; wb = new int[N+1];

            stack = new long[N+1];
            si = 0;

            res = new int[N+1];
            for (int i = 2; i <= N; i++) {
                int[] t = read(br);
                add(t[0], i, t[1], t[2]);
            }
            dfs(1, 0, 0);
            for (int i = 2; i <= N; i++) {
                out.print(res[i] + " ");
            }
            out.println();
        }
        out.flush();
    }

    public static void dfs(int x, long suma, long sumb) {
        stack[si++] = sumb;
        // 二分找suma
        int left = 0, right = si-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (stack[mid] <= suma) {
                res[x] = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        for (int i = h[x]; i != -1; i = ne[i]) {
            dfs(e[i], suma+wa[i], sumb+wb[i]);
        }
        // 出栈
        si--;
    }


    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

倍增的做法，学习下

import java.util.*;
import java.io.*;

// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class G_2 {
    public static void main(String[] args) throws Exception{
        // 输入重定向，通过jvm参数判断环境
        if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
            System.setIn(new FileInputStream("./input.txt"));
        }
        new Main().main(args);
    }
}

class Main {

    static int idx;
    static int[] e, ne, h, wa, wb;
    static int[] res;
    // fa[i][j]，节点i向上跳2^j的节点
    static int[][] fa;
    // fsb[i][j]，节点i向上跳2^j的节点sumb总和
    static long[][] fsb;
    static int[] dep;
    static long[] suma, sumb;

    public static void add(int a, int b, int i, int j) {
        e[idx] = b; ne[idx] = h[a];
        wa[idx] = i; wb[idx] = j;
        h[a] = idx++;
    }

    // 倍增做法
    public static void main(String[] args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = read(br)[0];
        while (T-- > 0) {
            int N = read(br)[0];
            idx = 0;   
            h = new int[N+1]; Arrays.fill(h, -1);
            e = new int[N+1]; ne = new int[N+1];
            wa = new int[N+1]; wb = new int[N+1];

            suma = new long[N+1]; sumb = new long[N+1];
            dep = new int[N+1];
            // fa[i][j]: i向上跳2^j的节点
            fa = new int[N+1][31];
            fsb = new long[N+1][31];

            for (int i = 2; i <= N; i++) {
                int[] t = read(br);
                add(t[0], i, t[1], t[2]);
            }
            // 构建倍增数组
            dfs(1);
            for (int i = 2; i <= N; i++) {
                int res = dep[i];
                if (suma[i] < sumb[i]) {
                    // 向上走大于等于t距离的第一个
                    long t = sumb[i]-suma[i];
                    int x = i;
                    for (int k = 30; k >= 0; k--) {
                        if (fsb[x][k] <= t) {
                            t -= fsb[x][k];
                            x = fa[x][k];
                            res = dep[x];
                        }
                    }
                    // 找不到sumb刚好相差t的节点，再往上走一步
                    if (t > 0) res--;
                }
                out.print(res+" ");
            }
            out.println();
        }
        out.flush();
    }

    public static void dfs(int root) {

        for (int i = 1; i < 31; i++) {
            fa[root][i] = fa[fa[root][i-1]][i-1];
            // root跳2^i = root跳到2^(i-1) + 2^(i-1)到2^i
            fsb[root][i] = fsb[root][i-1] + fsb[fa[root][i-1]][i-1];
        }

        for (int i = h[root]; i != -1; i = ne[i]) {
            int t = e[i];
            suma[t] = suma[root] + wa[i];
            sumb[t] = sumb[root] + wb[i];
            dep[t] = dep[root] + 1;
            fa[t][0] = root;
            fsb[t][0] = wb[i];
            dfs(t);
        }
    }


    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

赞赏

感谢鼓励