题解 | 牛客周赛 Round 108 EF Java题解

EF Java题解，代码已去除冗余~~~

E 小苯的有趣数

极限情况下，可以变成最后一项全是1，剩下的数字sum为最后一项，那么答案起码是n-1，之后利用背包枚所有可能的有趣数，来计算每种可能的长度且每种数字和的情况下可否全为有趣数，这一步需要预处理，时间复杂度O(2e6+T)

import java.util.*;
public class Main{
    static int interesting[]={2304,12544,1,4,16900,9,17161,3600,4624,10000,529,11025,12321,36,3364,14884,2601,5929,14641,7225,10816,14400,9025,324,12100,81,100,10609,121,19321,900,8836,4489,144,400,5776,19600,1681,3481,8100,10404,169,441,961,196,10201,225,12769,484,7396,2025,1521};
    static boolean has[][]=new boolean[205][20005];
    static{
        has[0][0]=true;
        for(int i=1;i<=100;i++){
            for(int j=1;j<=20000;j++){
                for(int a:interesting){
                    if(j>=a){
                        has[i][j]|=has[i-1][j-a];
                    }
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),sum=0;
            for(int i=0;i<n;i++){
                sum+=sc.nextInt();
            }
            System.out.println(has[n][sum]?n:n-1);
        }
    }
}

F AND VS MEX

高效枚举二进制子集，参考知识，参考代码，时间复杂度O(Tnloga)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),mask[]=new int[n+5];
            Arrays.fill(mask,Integer.MAX_VALUE);
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                mask[a]=a;
            }
            for(int i=n;i>0;i--){
                for(int j=0;1<<j<=n;j++){
                    if((i>>j&1)==1){
                        mask[i^(1<<j)]&=mask[i];
                    }
                }
            }
            for(int i=1;;i++){
                if(mask[i]!=i){
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}