题解 | 牛客周赛 Round 96 DEF Java题解

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

D 魔法棒

方法一：打卡找规律，经过打卡发现，只有在2,3,5,6,8,11,14的时候无法组成，因此打卡即可，时间复杂度O(T)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            long x=sc.nextLong();
            System.out.println(x==2||x==3||x==5||x==6||x==8||x==11||x==14?"No":"Yes");
        }
    }
}

方法二：赛时发现，符合要求的数字一定可以表示为3a+8b+1,a>=0,b>=0的形式，因此最多验证10次即可，时间复杂度O(T)，参考代码

E 字符串min-18

动态规划，由于先修改会影响到后修改，因此需要从前往后处理，不妨记录每一种结尾为0或者1的时候，且分别前缀用过奇数与偶数次翻转的最小次数，剩下的步骤就简单了，时间复杂度O(Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            String s=sc.next();
            long min[][]=new long[][]{{0,(long)1e18},{(long)1e18,(long)1e18}},ans=(long)1e18;
            for(int j=0;j<n;j++){
                int c=sc.nextInt(),b=s.charAt(j)-'0';
                long temp[][]=new long[][]{{(long)1e18,(long)1e18},{(long)1e18,(long)1e18}};
                for(int k=0;k<2;k++){
                    for(int p=0;p<2;p++){
                        if(k!=(p==0?b:b^1)){
                            continue;
                        }
                        //[最后数字][到此为止翻转次数]
                        for(int q=0;q<=k;q++){
                            for(int w=0;w<2;w++){
                                temp[k][p]=Math.min(temp[k][p],min[q][w]+(w==p?0:c));
                            }
                        }
                    }
                }
                min=temp;
            }
            for(int j=0;j<4;j++){
                ans=Math.min(ans,min[j/2][j&1]);
            }
            System.out.println(ans);
        }
    }
}

F Zeeman的异或数组

线性基组合，容易推测，mex一定为某个2的非负整数次幂，因为mex的非空子集也不能全部表示出来。。。接下来的是借鉴了视频题解，时间复杂度O(60Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            long base[]=new long[60];
            //插入
            for(int j=0;j<n;j++){
                long a=sc.nextLong();
                for(int k=59;k>=0;k--){
                    if((a>>k&1)==1){
                        if(base[k]!=0){
                            a^=base[k];
                        }
                        else{
                            base[k]=a;
                            break;
                        }
                    }
                }
            }
            //检查
            for(int j=0;;j++){
                long cur=1L<<j;
                for(int k=59;k>=0;k--){
                    if((cur>>k&1)==1&&base[k]!=0){
                        cur^=base[k];
                    }
                }
                if(cur!=0){
                    System.out.println(1L<<j);
                    break;
                }
            }
        }
    }
}