Codeforces Round #498 (Div. 3) problem 1006

problem 1006

JAVA刷题随笔

• Codeforces Round #498 (Div. 3) problem 1006
  • A. Adjacent Replacements
  • B. Polycarp’s Practice
  • C. Three Parts of the Array
  • D. Two Strings Swaps
  • E. Military Problem

A. Adjacent Replacements

problem 1006A

这题描述了一大堆(浪费不少时间读题),实际上就是把所有偶数变奇数…….属于废话特别多的签到题

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x;
        for (int i = ; i < n; i++) {
            x = scan.nextInt();
            if ((x & ) == ) {
                System.out.print(x -  + " ");
            } else {
                System.out.print(x + " ");
            }
        }
    }
           

B. Polycarp’s Practice

problem 1006B

题意大致是把数组分割成k个子数组,然后要求每个子数组里的最大值相加的结果最大.

这题思路也比较简单,实际找到前k大的几个数,然后把这几个作为分割位置即可.

我的思路是把找出来的这k个数以(值,下标)的形式存入数组,然后再按下标排个序.接着一个for循环就完成.

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n, k, x;
        n = scan.nextInt();
        k = scan.nextInt();
        Integer[] arr = new Integer[k];
        Map.Entry<Integer, Integer>[] pairs = new Map.Entry[n];
        for (int i = ; i < n; i++) {
            x = scan.nextInt();
            pairs[i] = new AbstractMap.SimpleEntry<>(x, i);
        }
        Arrays.sort(pairs, (o1, o2) -> o1.getKey() > o2.getKey() ? - : o1.getKey().equals(o2.getKey()) ?  : );
        int max = ;
        for (int i = ; i < k; i++) {
            max += pairs[i].getKey();
            arr[i] = pairs[i].getValue();
        }
        System.out.println(max);
        if (k==){
            System.out.println(n);
            return;
        }
        Arrays.sort(arr, (o1, o2) -> o1 < o2 ? - : o1.equals(o2) ?  : );
        int former = ;
        for (int i = ; i < arr.length; i++) {
            System.out.print(arr[i] - former + " ");
            former = arr[i];
        }
        System.out.println(n-arr[k-]);
    }
           

C. Three Parts of the Array

problem 1006C

题意大概就是找到两个分割位置 , 最左的数组=最右的数组时为一个分割方式,然后找到这种分割的最左(或最右)的最大值

我的做法把分割线从左右两边往中间缩,左边大的时候缩右边,右边大的时候缩左边.

sum1(最左)==sum3(最右)时记录下来,再继续.直到缩到不能缩

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        int a = , b = n - ;
        for (int i = ; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        long ans = , sumLeft = arr[a], sumRight = arr[b];
        while (a < b) {
            if (sumLeft > sumRight) {
                sumRight += arr[--b];
            } else {
                if (sumLeft == sumRight) {
                    ans = sumLeft;
                }
                sumLeft += arr[++a];
            }
        }
        System.out.println(ans);
    }
           

D. Two Strings Swaps

problem 1006D

这题读题要仔细,题意大概是:

给两个字符串A,B

你一开始可以改变A字符(且只能改变A)串任意位置的任意字符,题目里叫做这个操作为preprocess(假设改变次数记为x).

改变完之后你可以执行以下操作(必须改变完之后才能进行交换操作!):

1. 交换ai与bi (即A与B字符串相同位置的两个字符可以交换)

2. 交换ai与a(n-i+1) (即交换A字符串对称位置的两个字符)

3. 交换bi与b(n-i+1) (即第2条变换的B字符串版本)

你的目标是通过最少的preprocess操作(即x最小)达到能用交换操作来让字符串A与B相同的目的.

根据这题的交换操作,我们可以把ai,a(n-i+1),bi,b(n-i+1)归为一组数据进行讨论

1.当这四个字符都不相同时:很显然无法通过使用交换位置来达成目的,所以只能使用preprocess改变A中的两个字符来达到相同(x+=2).

2.若有一对字符相同:这里要分两类讨论,(1)因为只能改变A的内容,所以若这一对相等的字符都在A时,那就只能把两个字符都改变(x+=2) (2)如果这一对相等的字符不全在A里,那么可以通过改变一个字符,让另一对也相等(x+=1)

3.有三个字符相同:改变一个字符(x+=1)

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String sa = scan.next(), sb = scan.next();
        char[] a = sa.toCharArray();
        char[] b = sb.toCharArray();
//        System.out.println(sa + "," + sb);
        int ans = ;
        boolean oddFlag = (n & ) == ;
        Map<Character, Integer> map = new HashMap<>();
        for (int l = (n - ) / , r = n / ; l >=  && r < n; l--, r++) {
            putIntoMap(a[l], map);
            putIntoMap(a[r], map);
            putIntoMap(b[l], map);
            putIntoMap(b[r], map);
//            System.out.println(String.format("l:%d,r:%d,map.size=%d, al:%c,ar:%c,bl:%c,br:%c", l, r, map.size(), a[l], a[r], b[l], b[r]));
            if (map.size() == ) {
                ans += ;
            } else if (map.size() == ) {
                if (a[l] == a[r]) {
                    ans += ;
                } else {
                    ans++;
                }
            } else if (map.size() == ) {
                if (oddFlag && l == (n - ) / ) {
                    ans++;
                } else {
                    for (Character c : map.keySet()) {
                        if (map.get(c) == ) {
                            ans++;
                            break;
                        }
                    }
                }
            }
            map.clear();
        }
        System.out.println(ans);
    }

    public static void putIntoMap(Character x, Map<Character, Integer> map) {
        Integer t = map.get(x);
        if (t == null) {
            map.put(x, );
        } else {
            map.put(x, t + );
        }
    }
           

E. Military Problem

problem 1006E

这题题意大致是给一颗树,然后问q次,对于每次询问(u,k)返回节点u开始的前序遍历序列中的第k个数字.

这题我一开始想错了,以为剪剪枝就行了.于是我一开始生成了一颗树,统计每个节点的子节点总数.然后用前序遍历走…

于是我又换了种方法,我对树执行了一次前序遍历,为每个节点增加一个从当前节点开始的遍历结果….然后果不其然,爆内存了.

然后我用小黄鸭调试法重新思考了一下发现,实际上从任意节点开始的前序遍历结果都是从根节点开始的前序遍历结果的子集,所以可以都使用从根节点开始的前序遍历的结果集即可.

我的做法如下:

统计了每个节点的子节点数量(用于判断k是否大于u的子节点的数量,若大于则输出-1)

记录了一个从根节点开始的前序遍历序列,同时记录下每个子节点在这个序列中的位置

所以结果就是根节点遍历结果序列里u开始的第k个位置就是我们要的结果

/**
 * E.Military Problem
 * 输入n个端点跟q次询问
 * 然后输入n-1个数,第i个数代表序号为(i+1)的端点的父节点
 * 接着输入q个询问,每个询问输入u跟k两个数,代表从u开始传播(前序遍历)的第k个数
 */
public class EMilitaryProblem {

    /**
     * 思路:
     * 1.维护一颗树,统计每个子树的数目
     * 2.生成一个从根节点开始前序遍历的序列,记录下每个节点在序列内的序号
     * 3.对于每一个询问(u,k)做如下处理:
     * (1)先判断k是否大于u节点的统计(第1步的统计)结果,若大于则输出-1
     * (2)再查找u在序列(第2步生成的序列)中的位置,那么序列的第u+k-1个数字就是要输出的结果
     *
     * @param args nothing
     */
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), q = scan.nextInt();
        int[] father = new int[n + ];
        for (int i = ; i <= n; i++) {
            father[i] = scan.nextInt();
        }
        //初始化军官树
        Officers officerTree = new Officers(father);
        //开始询问
        List<Integer> target = officerTree.getPreOrder();
        int u, k;
        for (int i = ; i < q; i++) {
            u = scan.nextInt();
            k = scan.nextInt();
            if (officerTree.getOfficer(u).getCount() < k) {
                System.out.println("-1");
            } else {
                System.out.println(target.get(officerTree.getOfficer(u).getOrder() + k - ));
            }

        }
    }

    /**
     * 存放军官的树,存放一个数组维护所有节点.
     */
    static class Officers {

        private Node[] nodes;
        private List<Integer> preOrder;

        /**
         * 初始化,将树连通,统计,生成前序遍历结果
         *
         * @param fatherArray 从2开始,fatherArray[i]对应军官i的上级
         */
        Officers(int[] fatherArray) {
            nodes = new Node[fatherArray.length];
            nodes[] = new Node();
            for (int i = ; i < fatherArray.length; i++) {
                nodes[fatherArray[i]].addSon(nodes[i] = new Node(i));
            }
            preOrder = new ArrayList<>(fatherArray.length - );
            countNodeAndGenerateOrder(nodes[]);
        }

        /**
         * 对每一个节点进行递归统计,顺便生成前序遍历的结果
         */
        private int countNodeAndGenerateOrder(Node nod) {
            nod.setOrder(preOrder.size());
            preOrder.add(nod.getIndex());
            int count = ;
            for (Node node : nod.sons) {
                count += countNodeAndGenerateOrder(node);
            }
            nod.setCount(count);
            return count;
        }

        public List<Integer> getPreOrder() {
            return preOrder;
        }

        public Node getOfficer(int index) {
            return nodes[index];
        }

        /**
         * 节点类,用于生成树
         */
        class Node {
            //军官的序列
            private int index;
            //统计子节点的总数
            private int count;
            //在从根节点开始的前序遍历中的位置
            private int order;
            //子节点列表
            private List<Node> sons = new LinkedList<>();

            Node(int index) {
                this.index = index;
            }

            public void addSon(Node son) {
                sons.add(son);
            }

            public void setCount(int count) {
                this.count = count;
            }

            public int getIndex() {
                return index;
            }

            public int getCount() {
                return count;
            }

            public void setOrder(int order) {
                this.order = order;
            }

            public int getOrder() {
                return order;
            }


        }
    }
}