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

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

D 小心火烛的歪

注意到nmq都很小，状态可以使用二进制数来表示，最终安排的mask要是布局mask的补集，依次验证即可，时间复杂度O(nq(m+2^q))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),q=sc.nextInt(),grass[]=new int[n],plan[][]=new int[q][n],ans=100,mask=-1;
        for(int i=0;i<n;i++){
            grass[i]=find(sc.next());
        }
        for(int i=0;i<q;i++){
            for(int j=0;j<n;j++){
                plan[i][j]=find(sc.next());
            }
        }
        for(int i=0;i<(1<<q);i++){
            if(ans<=Integer.bitCount(i)){
                continue;
            }
            int cover[]=new int[n];
            for(int j=0;j<q;j++){
                if((i>>j&1)==1){
                    for(int k=0;k<n;k++){
                        cover[k]|=plan[j][k];
                    }
                }
            }
            boolean ok=true;
            for(int j=0;j<n;j++){
                if((cover[j]^grass[j])!=(1<<m)-1){
                    ok=false;
                    break;
                }
            }
            if(ok){
                ans=Integer.bitCount(i);
                mask=i;
            }
        }
        if(ans>q){
            System.out.println("-1");
        }
        else{
            System.out.println(ans);
            for(int j=0;j<q;j++){
                if((mask>>j&1)==1){
                    System.out.print(j+1+" ");
                }
            }
        }
    }
    static int find(String s){
        int ans=0;
        for(char c:s.toCharArray()){
            ans=ans<<1|(c-'0');
        }
        return ans;
    }
}

E 喜欢切数组的红

类似于双指针，把三分点存储起来，并保证每一部分正数至少一个，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long pre1[]=new long[n+1],pre2[]=new long[n+1],ans=0;
        for(int i=1;i<=n;i++){
            pre1[i]=pre1[i-1]+sc.nextInt();
            pre2[i]=pre2[i-1];
            if(pre1[i]>pre1[i-1]){
                pre2[i]++;
            }
        }
        if(pre1[n]%3==0){
            Queue<Integer> q1=new LinkedList<>(),q2=new LinkedList<>();
            for(int i=1;i<n;i++){
                if(i<n-1&&pre1[i]==pre1[n]/3&&pre2[i]>0){
                    q1.add(i);
                }
                if(pre1[i]==pre1[n]/3*2&&pre2[n]>pre2[i]){
                    q2.add(i);
                }
            }
            while(!q1.isEmpty()){
                int a=q1.poll();
                while(!q2.isEmpty()&&(q2.peek()<=a||pre2[q2.peek()]==pre2[a])){
                    q2.poll();
                }
                ans+=q2.size();
            }
        }
        System.out.println(ans);
    }
}

F 研究red子序列的红

线段树维护每种子序列的数量，兼具修改，时间复杂度O(nC*2^C(logn))，本题中C==3

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),q=sc.nextInt();
        char s[]=sc.next().toCharArray(),t[]=sc.next().toCharArray();
        SegTree st1=new SegTree(0,n-1),st2=new SegTree(0,n-1);
        build(st1,s);
        build(st2,t);
        for(int i=0;i<q;i++){
            int x=sc.nextInt()-1;
            char ch1=s[x],ch2=t[x];
            modify(st1,x,find(ch2));
            modify(st2,x,find(ch1));
            s[x]=ch2;
            t[x]=ch1;
            System.out.println(st1.count[7]-st2.count[7]);
        }
    }
    static void modify(SegTree st,int idx,int c){
        int l=st.l,r=st.r;
        if(l==r){
            Arrays.fill(st.count,0);
            st.count[0]=1;
            if(c!=-1){
                st.count[1<<c]=1;
            }
        }
        else{
            modify(idx<=(l+r)/2?st.left:st.right,idx,c);
            pushup(st);
        }
    }
    static void build(SegTree st,char c[]){
        int l=st.l,r=st.r;
        if(l==r){
            int idx=find(c[l]);
            if(idx>=0){
                st.count[1<<idx]=1;
            }
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,c);
            build(st.right,c);
            pushup(st);
        }
    }
    static void pushup(SegTree st){
        for(int j=1;j<8;j++){
            if(j==5){
                continue;
            }
            st.count[j]=st.left.count[j];
            for(int i=0;i<3;i++){
                if((j>>i&1)==1){
                    st.count[j]+=st.left.count[j>>(i+1)<<(i+1)]*st.right.count[j^(j>>(i+1)<<(i+1))];
                }
            }
        }
    }
    static int find(char c){
        return c=='r'?2:c=='e'?1:c=='d'?0:-1;
    }
}
class SegTree{
    int l,r;
    SegTree left,right;
    long count[]=new long[8];
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
        count[0]=1;
    }
}