Codeforces Round 910 (Div. 2) --- B-E 补题记录

B - Milena and Admirer 

Problem - B - Codeforces

题目大意：

现在给出一个无序序列，你可以使用任意次操作将这个无序序列修改为不递减序列，操作为你可以使用两个数a和b来替换ai，序列就变为了 ai-1， a，b，ai+1。求将这个序列修改为不递减序列的最少操作次数。

我比赛时的错误思路：（标红的是正确的）

对这个序列进行修改操作时，应该从后往前进行修改，因为他是不递减序列，所以我们只要保证后面满足条件，然后一直向前调整即可。（这个思路是对的）但是我刚开始想的是要让操作次数较少，应该要尽量2分这个不合理的数，让其变为合理的。所以如果是9，3。我的这个操作就会修改为2，2，2，3，3进行3次修改操作。然后我突然发现3，3，3，3.只会进行两次修改操作。所以思路应该为均分这个不合理的数。让他均分后小于他后面的数，均分还能保证他对前面的限制条件放松，来使操作次数进一步减小。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;

/**
 * @ProjectName: study3
 * @FileName: Ex15
 * @author:HWJ
 * @Data: 2023/11/19 23:05
 */
public class Ex15 {
    static int[] arr;
    static long total = 0;
    static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); 
        int n = (int) in.nval;
        for (int o = 0; o < n; o++) {
            total = 0;
            in.nextToken();
            int m = (int) in.nval;
            arr = new int[m];
            for (int i = 0; i < m; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }

            for (int i = m - 2; i >= 0; i--) {
                if (arr[i] > arr[i + 1]) {
                    // 尽量arr[i]均分为arr[i+1]的大小。
                    int cnt = (arr[i] + arr[i + 1] - 1) / arr[i + 1];
                    total += cnt - 1; // 均分为cnt份，需要cnt-1次。
                    arr[i] /= cnt;
                }
            }
            System.out.println(total);
        }
    }
}

Colorful Grid

Problem - C - Codeforces

题目大意：

现在给出一个方格n行m列，你可以将这个方格的任意一条边修改为红色或者蓝色，然后需要从（1，1）这个点前往到（n，m）这个点，要求在前往路程中走完蓝色的边下一次走的边应该为红色的边，走完红色的边下一次走的边应该为蓝色。然后在满足这个要求的情况下，如果经过了k条边，我们则称这次的路程长度为k。（边可以重复经过）现在给出n m k。问你有没有一个染色方案，可以使从起点到终点的路径长度为k。

思路：

对于一个方格，他的最短路径应该为（n+m-2），然后我们如果要判断k这个路程长度能不能到达，那可以想到，我们应该走多组无效路程，然后一组无效路程应该长度为2。所以k应该和（n+m-2）保持同样的奇偶性。所以他最后可能是多走了奇数组或者偶数组。那么最后就相当于多走一组（奇数组）或者没有多走（偶数组），所以我们可以构造一个正方形让他在浪费一组和不浪费的情况下都能前往终点。（这里给出代码，可以根据代码画图帮组理解）

代码：

import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex16
 * @author:HWJ
 * @Data: 2023/11/20 12:28
 */
public class Ex16 {
    static HashMap<Edge, Character> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        for (int o = 0; o < t; o++) {
            int n = input.nextInt();
            int m = input.nextInt();
            int k = input.nextInt();
            int mn = n + m - 2; // 所需要使用的最少边数
            // 因为k如果大于最少边数，他就只能一直重复走某些路径 但重复的时候肯定会重复多组边
            // 一组边会增加两次，所以k应该和最少边数保持同样的奇偶性
            if (k < mn || (k % 2) != (mn % 2)){
                System.out.println("No");
            }else {
                System.out.println("Yes");
                for (int i = 1; i <= n; i++) { // 这里将整个图的边全部染为红色
                    for (int j = 1; j <= m; j++) {
                        if (j + 1 <= m) map.put(new Edge(new Node(i,j), new Node(i,j+1)), 'R');
                        if (i + 1 <= n) map.put(new Edge(new Node(i,j), new Node(i+1,j)), 'R');
                    }
                }
                map.put(new Edge(new Node(1,1), new Node(2,1)), 'B');
                map.put(new Edge(new Node(1,2), new Node(2,2)), 'B');
                map.put(new Edge(new Node(1,3), new Node(2,3)), 'B');
                map.put(new Edge(new Node(2,2), new Node(3,2)), 'B');
                // 构造一个正方行的红蓝圈让他一直在里面绕，并且可以在某个半圈或者一圈使退出正方形圈

                boolean f = false;
                // 这里构造使任意一个退出的地方都一定能走到终点。
                for (int i = 3; i < m; i++) {
                    map.put(new Edge(new Node(3,i), new Node(3,i+1)), f ? 'R' : 'B');
                    f = !f;
                }

                for (int i = 3; i < n; i++) {
                    map.put(new Edge(new Node(i,m), new Node(i+1,m)), f ? 'R' : 'B');
                    f = !f;
                }
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j < m; j++) {
                        System.out.print(map.get(new Edge(new Node(i,j),new Node(i,j+1))) + " ");
                    }
                    System.out.println();
                }
                for (int i = 1; i < n; i++) {
                    for (int j = 1; j <= m; j++) {
                        System.out.print(map.get(new Edge(new Node(i,j),new Node(i+1,j))) + " ");
                    }
                    System.out.println();
                }

            }
        }
    }

    public static class Edge{
        Node s;
        Node e;
        public Edge(Node s, Node e){
            this.s = s;
            this.e = e;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return Objects.equals(s, edge.s) && Objects.equals(e, edge.e);
        }

        @Override
        public int hashCode() {
            return Objects.hash(s, e);
        }
    }


    public static class Node{
        int col;
        int row;
        public Node(int row, int col){
            this.col = col;
            this.row = row;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return col == node.col && row == node.row;
        }

        @Override
        public int hashCode() {
            return Objects.hash(col, row);
        }
    }
}

D. Absolute Beauty 

Problem - D - Codeforces

题目大意：

给出两个整数序列，a和b。得分为|ai - bi|之和。现在你可以进行至多一次操作使得得分最大。操作为选择任意bi 和 bj让其交换位置。

思路：

对于a序列和b序列，因为得分是计算绝对值且最多只能交换一次，所以ai和bi互换位置，是对答案没有影响。则我们可以通过互换位置，使得任意i位置上的ai一定大于等于bi。

这可以将绝对值表示的意义想象为这个线段的长度。

对于任意几个线段有三个情况。只有第一种情况的交换会使，绝对值之和增加。又因为只能进行一次交换操作，所以我们应该使第一种情况下的a1尽可能小，b2尽可能大。

则答案增量为2*（max（b）- min（a） ）

代码：

import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex17
 * @author:HWJ
 * @Data: 2023/11/21 9:29
 */
public class Ex17 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        for (int o = 0; o < t; o++) {
            int n = input.nextInt();
            int[][] a = new int[n][2];
            long total = 0;
            int max = 0;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                a[i][0] = input.nextInt();
            }
            for (int i = 0; i < n; i++) {
                a[i][1] = input.nextInt();
                if (a[i][1] > a[i][0]){
                    int tmp = a[i][1];
                    a[i][1] = a[i][0];
                    a[i][0]=tmp;
                }
                max = Math.max(max, a[i][1]);
                min = Math.min(min, a[i][0]);
                total += a[i][0] - a[i][1];
            }
            System.out.println(Math.max(total, total + 2L *(max - min)));


        }
    }
}

 E. Sofia and Strings

Problem - E - Codeforces

题目大意：

给你两个字符串S和T,数字n和m，n和m分别为字符串S和T的长度，你可以对字符串S进行操作使其变为字符串T。如果能变为字符串T则输出YES，否则输出NO。

操作为：

1. 选择 i（1 <= i <= n)，将字符串S这个位置上的字符删掉。

2. 选择 l 和 r ( 1 <= l <= r <= n),将字符串S [ l，r] 这段位置上的字符按照字典序进行排序。

思路：

因为他是按照字典序进行排序，那么字典序小的字符没有办法修改到字典序大的字符后面。

则给出一个样例：

S ： abcdgef

T : efg

遍历T，T1为e，可以找到它在S的位置为S5，S5前面的abcd已经对后序的整个操作是无效的了。

所以修改S T为

S ：gf

T：fg

遍历T，T1为f，可以找到它在S的位置为S2，S2前面的g对后序的操作是有效的，保留。

所以修改S T为

S ：g

T：g

.........这样的修改策略就可以判断S是否能修改为T。但是如果用遍历来寻找对应位置和是否删除是不明智的，因为时间开销太大了。所以我们可以使用队列来实现。因为删除时，只删除对应位置和对应位置前面字典序小于当前字典序的字符。满足先进先出的特性，位置靠前的先进行删除操作。

代码：

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex18
 * @author:HWJ
 * @Data: 2023/11/21 12:01
 */
public class Ex18 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        for (int o = 0; o < t; o++) {
            int n = input.nextInt();
            int m = input.nextInt();
            String str1 = input.next();
            String str2 = input.next();
            char[] s1 = str1.toCharArray();
            char[] s2 = str2.toCharArray();
            LinkedList<Integer>[] set = new LinkedList[27];
            for (int i = 0; i < 27; i++) {
                set[i] = new LinkedList<>();
            }
            for (int i = 0; i < n; i++) {
                set[s1[i] - 'a'].add(i);
            }
            boolean loop = true;
            for (int i = 0; i < m; i++) {
                if (set[s2[i] - 'a'].isEmpty()){
                    loop = false;
                    break;
                }
                int now = set[s2[i] - 'a'].removeFirst();
                for (int j = 0; j < s2[i] - 'a'; j++) {
                    while (!set[j].isEmpty() && set[j].getFirst() < now){
                        set[j].removeFirst();
                    }
                }
            }
            System.out.println(loop ? "YES" : "NO");
        }


    }
}