A~F 小白月赛94> 我的自动WA机又出手了, 狠狠掉分

A 九宫格

读入,按位置输出即可

import java.io.*;


public class Main {
    public static void main(String[] args) throws Exception {
        int[] a = new int[10];
        for (int i = 1; i < 10; i++) a[i] = I();
        String s = S();
        for (char ch : s.toCharArray()) pw.print(a[ch - '0']);
        pw.flush();
    }

    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    static String S() throws IOException {
        String res = bf.readLine();
        while (res.isEmpty()) res = bf.readLine();
        return res;
    }
}

B 好数组

(1) 数组已经是有序的, 不管怎么选都是有序的, 选不了, 输出0

(2) 数组不是有序的, 全部选上就行了, 输出n

import java.io.*;

public class Main {
    
    public static void main(String[] args) throws Exception {
        int n = I();
        int[] a = new int[n];
        for (int i = 1; i < n; i++) a[i] = I();
        System.out.println(check(a, n) ? 0 : n);
    }

    static boolean check(int[] a, int n) {//a是否有序
        for (int i = 0; i < n - 1; i++) {
            if (a[i] > a[i + 1]) return false;
        }
        return true;
    }

    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);
 
    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    } 

}

C 数字合并最大化极差

最终情况是:

左边一坨合一起, 中间是最小值, 右边一坨合一起

左右取最大值

所以处理出前后缀和, 然后枚举a[i]作为最小值

服了, 索引从1开始还是从0开始啥的一直搞不清, WA了14发, 给我打红温了

import java.io.*; 


public class Main {
    public static void main(String[] args) throws Exception {
        int n = I();
        long[] a = new long[n + 1];
        long[] preSum = new long[n + 1];//前缀和,[1,i]
        for (int i = 1; i <= n; i++) {
            a[i] = I();
            preSum[i] = preSum[i - 1] + a[i];
        }
        long suffSum = preSum[n];//后缀和,a[i+1,n]
        long ans = 0;
        for (int i = 1; i <= n; i++) {//枚举min
            suffSum -= a[i];
            ans = Math.max(ans, preSum[i - 1] - a[i]);// 左边合并
            ans = Math.max(ans, suffSum - a[i]); // 右边合并
        }
        System.out.println(ans);
    }


    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);

    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }


}

D gcd排列构造

a[i] = gcd(ans[1],...ans[i])
a[i-1] = gcd(ans[1],...ans[i-1]
∴ a[i] = gcd(a[i-1],ans[i])
∴ a[i-1]%a[i]=0, ans[i]%a[i]=0

由 a[i-1] % a[i] = 0可知,a是一个非增序列, a[i-1]与a[i]只有两种情况, a[i-1]==a[i], a[i-1]>a[i]

现在从前往后依次确定ans:

(1) 如果a[i - 1] > a[i]:  
意味着a[i]是第一次出现, 那么数a[i]一定是没使用过的, 该位需要填a[i] 

    证明:
    a[i-1] = gcd(ans[1],...ans[i-1]) > a[i] = gcd(ans[1],...ans[i])
    min(ans[1],...ans[i-1]) > min(ans[1],...ans[i])
    min(ans[1],...ans[i-1]) > ans[i]
    ∴ ans[1]~ans[i-1] 与 ans[i] 不相等, a[i]一定未使用
    
    填a[i]是否会导致无解:
    例如: a[i-1] = 4, a[i] = 2, n≥6
    显然6也可以填, 那么2可以填在哪
    如果 a[i+1] = 2, 则2可以填在i+1位, 这样的话,2与6可以互换, 不影响正确性
    如果 a[i+1] = 1, 则后面都是1, 可填数字是任意的, 2和6依旧可以互换
    所以填a[i] 不会导致无解
    
(2) 如果a[i-1] = a[i]:
那么需要找一个a[i]的未使用倍数

填多少倍: 
    与1的互换同理, 找一个最小的满足条件的倍数即可

从哪开始找:
    不能直接从a[i]开始查找, 数组a末尾有很长串的1, 会超时
    ∵ a[i] = gcd(ans[1],...ans[i])
    ∴ ans[i]是a[i]的倍数, ans[i-1]也是a[i]的倍数, 且 ans[i] > ans[i-1]
    所以可以从ans[i-1]+a[i]开始查找
    

import java.io.*; 

public class Main {
    static int N = (int) 2e5 + 1;
    static int[] a = new int[N];//a[i] = gcd(ans[1],...asn[i])
    static int[] ans = new int[N];
    static int n;
    static boolean[] used = new boolean[N];//used[i]:数字i是否被使用了

    public static void main(String[] args) throws Exception {
        n = I();
        if (!solve()) {
            System.out.println(-1);
        } else {
            for (int i = 1; i <= n; i++) System.out.print(ans[i] + " ");
        }
    }

    private static boolean solve() throws IOException {
        for (int i = 1; i <= n; i++) {
            a[i] = I();
            /*
            a[i] = gcd(ans[1],...ans[i]) = gcd(a[i-1],ans[i])
            ⇒ a[i-1] % a[i] == 0
             */
            if (a[i - 1] % a[i] != 0) return false;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i - 1] != a[i]) {// eg: i=2, a[1]=4, a[2]=2 -> 填2
                ans[i] = a[i];
            } else {// eg: i=2, a[1]=4, a[2]=4  -> 可填 8 12 16... 
                ans[i] = find(i);
                if (ans[i] == 0) return false;// 找最小的未填的a[i]倍数,找不到
            }
            used[ans[i]] = true;
        }
        return true;
    }

    /**
     查找a[i]的未使用的倍数, 且满足:
     gcd(ans[1],...ans[i-1],ans[i]) == a[i]
     ⇔ gcd(a[i-1], ans[i]) == a[i]
     */
    static int find(int i) {
        // ans[i] > ans[i-1], ans[i-1]也是a[i]的倍数
        for (int f = ans[i - 1] + a[i]; f <= n; f += a[i]) {
            if (!used[f] && gcd(a[i - 1], f) == a[i]) {
                return f;
            }
        }
        return 0;
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);

    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

}

E F "与"背包

与运算, 选的越多, 价值越低, 但总体积也越小越可行
现在需要找到最大价值, 设其为ans
∴ value[1] & value[2] & ... = ans
∴ ans & value[i] = ans (ans在任意一位的1, 每个value在对应位上都有)

假设ans = 10110
那么只要第1位、第3位、第4位都为1, 那么这个物品对于这个答案来说就是可选的
而体积是选的越多越可行, 所以可以枚举答案
然后按"ans & value[i] = ans"这个条件,选出所有物品
计算出这些物品的总体积, 如果满足容量k限制, 则找到一个可行解 

对于E, 数据范围2e3, 可以直接从2000开始枚举答案

对于F, 数据范围1e9, 可以从高位开始, 用试填法, 逐位确定

import java.io.*; 
 
public class Main { 

    public static void main(String[] args) throws Exception {
        int n = I(), k = I();
        int[] v = new int[n], w = new int[n];//v价值,w重量
        for (int i = 0; i < n; i++) {
            w[i] = I();
            v[i] = I();
        }
        System.out.println(solve2(n, v, w, k));
    }

    /**
     n,k,w,v ∈ [0,2e3] 
     枚举答案, 将可选的价值都选上, 计算出重量, 如果满足容量条件, 则找到一个可行解

     @param v 价值
     @param w 重量|体积
     */
    private static int solve1(int n, int[] v, int[] w, int k) {
        for (int guess = 2000; guess > 0; guess--) {//枚举答案,总价值
            //计算重量是否超标
            int weight = (1 << 20) - 1;
            for (int i = 0; i < n; i++) {
                if ((v[i] & guess) == guess) {// &{v[i]} = guess  =>  (guess & v[i]) = guess
                    weight &= w[i];
                }
            }
            if (weight <= k) return guess;
        }
        return 0; //啥也选不了, 空包
    }

    /**
     n,k,w,v ∈ [0,1e9]
     从高到低, 试填法确定每一位
     */
    private static int solve2(int n, int[] v, int[] w, int k) {
        int ans = 0;
        for (int bit = 30; bit >= 0; bit--) {//从高位枚举
            int guess = ans | (1 << bit);//尝试在该位填1
            int weight = (1 << 30) - 1;// 1e9 < 2^30
            for (int i = 0; i < n; i++) {
                if ((guess & v[i]) == guess) {
                    weight &= w[i];
                }
            }
            if (weight <= k) ans = guess;//该位可以为1
        }
        return ans;
    }

    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);

    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

}