题解 | #F. 是牛牛还是狗勾#

F. 是牛牛还是狗勾

一眼0-1背包

但是时间复杂度为 O(N*V)

但是这边N=10^6, V=10^3, 最大复杂度 10^9

显然直接做，是不行的

但是这题有个特例，如果N>=1001, 根据鹊巢原理，根据前缀和，必然存在2个同余(1000)相等。

也就是N>=1001必然有解

所以如果依旧使用 0-1背包算法

只要找到任意解就行，(最多1001项)

和 长途大佬 的解法，区别在于 不用分类讨论(n<=1000, n>1000)

当然这里还有一个难点，就是, 回溯构造

注意java要用快读

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

public class Main {

    public static void main(String[] args) {
        AReader sc = new AReader();

        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();

            long acc = 0;
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
                acc += arr[i];
            }

            boolean[] dp = new boolean[1001];
            dp[0] = true;
            int[] from = new int[1001];
            Arrays.fill(from, -1);

            // n > 1000, 前缀和鹊巢原理必然有解，思路很赞
            for (int i = 0; i < n; i++) {
                int v = arr[i];

                boolean[] dp2 = dp.clone();
                for (int j = 0; j <= 1000; j++) {
                    if (!dp[j]) continue;
                    // <=1000的处理
                    if (j + v <= 1000 && !dp2[j + v]) {
                        dp2[j + v] = true;
                        from[j + v] = i;
                    }
                    // > 1000需要取余
                    if (j + v > 1000 && !dp2[j + v - 1000]) {
                        dp2[j + v - 1000] = true;
                        from[j + v - 1000] = i;
                    }
                }
                dp = dp2;
                if (dp[1000]) {
                    // 找到了，就提前推出了
                    break;
                }
            }

            if (!dp[1000]) {
                System.out.println(-1);
            } else {
                List<Integer> res = new ArrayList<>();
                int id = 1000;
                while (from[id] != -1) {
                    res.add(from[id] + 1);
                    id = (id - arr[from[id]] + 1000) % 1000;
                }

                System.out.println(acc % 1000);
                System.out.print(res.size() + " ");
                System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            }

        }

    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
        // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
    }

}