Practice

A. Absolute Maximization

题意

给定一个数组 \(a\)，定义操作为选择两个元素 \(a_i, a_j\)，并交换它们二进制下的第 \(b\) 位。输出任意次操作后的 \(\max(a) - \min(a)\) 的最大值。

思路

既然可以无限次交换，那么我们只要找出最高位，从最高位开始往下找，只要有一个元素该位存在 \(1\)，那么我们就拿过来构建新的数字，这样即可得到最大值。反之同理。

时间复杂度：\(O(n)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for(int w=0;w<t;w++){
            int n = scanner.nextInt();
            int[] min = new int[12], max = new int[12];
            for(int i=0;i<12;i++){
                min[i] = 1;
                max[i] = 0;
            }
            int maxLen = 0;
            String[] input = new String[n];
            for(int i=0;i<n;i++) {
                input[i] = Integer.toBinaryString(scanner.nextInt());
                maxLen = Math.max(maxLen, input[i].length());
            }
            for(int i=0;i<n;i++) {
                while(input[i].length() != maxLen) input[i] = "0" + input[i];
                for(int j=0;j<maxLen;j++) {
                    int now = input[i].charAt(j) - '0';
                    max[j] = Math.max(max[j], now);
                    min[j] = Math.min(min[j], now);
                }
            }
            int maxx = 0, minn = 0;
            for(int i=0;i<maxLen;i++) {
                maxx = maxx * 2 + max[i];
                minn = minn * 2 + min[i];
            }
            System.out.println(maxx - minn);
        }
    }
}

简单思维题

B. Incinerate

题意

给定 \(n\) 个怪物的生命值 \(h_i\) 以及攻击力 \(p_i\)，主角的攻击力为 \(k\)，定义一次攻击为将所有怪物扣去 \(k\) 点生命值，生命值小于等于 \(0\) 的怪物死亡，剩余攻击力最低的怪物将会将主角的攻击力削减到 \(k - p_i\)。输出是否可以将怪打完。

思路

模拟。

我们可以先按照生命值升序排序，维护一个存活的怪物的开始下标 \(index\)，那么想要快速获取到存活的怪物中攻击力最低的，我们可以维护一个后缀数组，存储 \(index\) 及以后的 \(p_{\min}\)。

时间复杂度：\(O(n \log n)\)

对应AC代码

import java.util.*;

public class Main {

    private static class Monster{
        int h, p;
        Monster(int h){
            this.h = h;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for(int w=0;w<t;w++){
            int n = scanner.nextInt(), k = scanner.nextInt();
           Monster[] m = new Monster[n];
           for(int i=0;i<n;i++) m[i] = new Monster(scanner.nextInt());
           for(int i=0;i<n;i++) m[i].p = scanner.nextInt();
           Arrays.sort(m, Comparator.comparingInt(o -> o.h));
           int[] suf = new int[n + 1];
           suf[n] = Integer.MAX_VALUE;
           for(int i=n-1;i>=0;i--) suf[i] = Math.min(suf[i + 1], m[i].p);
           int index = 0, attack = 0;
           while(k > 0){
               for(int i=index;i<n;i++){
                   if(m[i].h - attack > k) break;
                   index ++;
               }
               if(index >= n) break;
               attack += k;
               k -= suf[index];
           }
           System.out.println(k > 0 ? "YES" : "NO");
        }
    }
}

略微暴力但又不暴力（

C. Another Array Problem

题意

给定一个数组 \(a\)，定义操作为选择 \(i, j,i \neq j\)，将所有 \(a_k, k \in [i, j]\) 修改为 \(|a_i - a_j|\)。在任意次操作后，输出数组的总和的最大值。

思路

我们来考虑一下 \(4\) 个及以上的情况：

在这个情况里，我们不妨找出最大值所在的下标 \(imax\)，然后用类似下面的思路完成：

\(\begin{array}{l}>>1\ 2\ 4\ 3 \\ => 1\ 1\ 4\ 3 \\ => 0\ 0\ 4\ 3 \\ => 4\ 4\ 4\ 3 \\ => 4\ 4\ 1\ 1 \\ => 4\ 4\ 0\ 0 \\ => 4\ 4\ 4\ 4\end{array}\)

也就是说，我们只需找出最大的值，最后一定有方案将所有数全都改为最大值。

那么 \(3\) 个数呢？此时存在局限性，若最大值在两端，那么和上述一致，但最大值在中间时，我们就只能找出两端的 \(\min , \max\)，然后取 \(a[1]-\min\) 和 \(\max\) 的最大值。

同上，两个数的时候，最大值即为两个元素的差。

当然，我们也可以不操作，所以需要取一下操作后的答案和原总和的最大值。

时间复杂度：\(O(n)?\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for(int w=0;w<t;w++){
            int n = scanner.nextInt();
            long[] a = new long[n];
            int maxIndex = 0;
            long sum = 0;
            for(int i=0;i<n;i++){
                a[i] = scanner.nextLong();
                sum += a[i];
                maxIndex = a[maxIndex] < a[i] ? i : maxIndex;
            }
            long ans;
            if(n == 2) {
                ans = Math.abs(a[1] - a[0]) * 2;
            }else if(n == 3){
                if(maxIndex == 0 || maxIndex == 2) ans = a[maxIndex] * n;
                else{
                    long min = Math.min(a[0], a[2]), sMin = Math.max(a[0], a[2]);
                    ans = Math.max(a[maxIndex] - min, sMin) * 3;
                }
            }else ans = a[maxIndex] * n;
            System.out.println(Math.max(sum, ans));
        }
    }
}

很巧妙的思维题