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

DEF Java题解~~~代码已去除冗余，并保留必要的注释

D 小红的行列式构造

好烦啊，瞎做呗，令上边俩角的元素相同，下边俩角的元素相同，可以消掉一部分，剩下的代数式分解因式即可拼凑，时间复杂度O(1)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        System.out.println("99 100 99\n101 1 "+(sc.nextInt()+101)+"\n1 1 1");
    }
}

E 小红的 red 计数

寻找目标子序列的数目，可以找出任意分解在不同区间的贡献值，考虑全部情况相加，大串的数量跟串的数量（贡献）有关，减小复杂度可用分层前缀后缀和，时间复杂度O(n+q)

import java.util.*;
import java.io.*;
public class Main{
    static String red="red";
    static Map<String,Integer> map=new HashMap<>();
    static{
        for(int i=0;i<3;i++){
            for(int j=i;j<3;j++){
                map.put(red.substring(i,j+1),map.size());
            }
        }
    }
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]);
        String s=bf.readLine();
        long pre1[][]=new long[n+5][7],pre2[][]=new long[n+5][7];
        for(int i=1;i<=n;i++){
            pre1[i]=pre1[i-1].clone();
            char c=s.charAt(i-1);
            int idx=red.indexOf(c);
            if(idx>=0){
                for(int j=idx-1;j>=0;j--){
                    pre1[i][map.get(red.substring(j,idx+1))]+=pre1[i-1][map.get(red.substring(j,idx))];
                }
                pre1[i][map.get(String.valueOf(c))]++;
            }
        }
        for(int i=n;i>0;i--){
            pre2[i]=pre2[i+1].clone();
            char c=s.charAt(i-1);
            int idx=red.indexOf(c);
            if(idx>=0){
                for(int j=idx-1;j>=0;j--){
                    pre2[i][map.get(red.substring(j,idx+1))]+=pre2[i+1][map.get(red.substring(j,idx))];
                }
                pre2[i][map.get(String.valueOf(c))]++;
            }
        }
        for(int i=0;i<q;i++){
            arr=bf.readLine().split(" ");
            int l=Integer.parseInt(arr[0]),r=Integer.parseInt(arr[1]);
            long ans=0;
            for(int j=0;j<=3;j++){
                for(int k=j;k<=3;k++){
                    ans+=find1(pre1,1,l-1,substring(red,0,j-1))*find2(pre2,l,r,substring(red,j,k-1))*find1(pre1,r+1,n,substring(red,k,2));
                }
            }
            bw.write(ans+"\n");
        }
        bw.flush();
    }
    static long find1(long pre1[][],int l,int r,String s){
        if(s.length()>r-l+1){
            return 0;
        }
        if(s.length()==0){
            return 1;
        }
        long ans=pre1[r][map.get(s)]-pre1[l-1][map.get(s)];
        for(int i=1;i<s.length();i++){
            ans-=find1(pre1,1,l-1,s.substring(0,i))*find1(pre1,l,r,s.substring(i));
        }
        return ans;
    }
    static long find2(long pre2[][],int l,int r,String s){
        if(s.length()>r-l+1){
            return 0;
        }
        if(s.length()==0){
            return 1;
        }
        long ans=pre2[l][map.get(s)]-pre2[r+1][map.get(s)];
        for(int i=1;i<s.length();i++){
            ans-=find2(pre2,r+1,pre2.length-5,s.substring(0,i))*find2(pre2,l,r,s.substring(i));
        }
        return ans;
    }
    static String substring(String s,int l,int r){
        return l>r?"":s.substring(l,r+1);
    }
}

F 小红开灯

利用线性基，将每个灯所能够造成的影响用128位的二进制数表示，高斯消元至上三角矩阵，之后按位尝试变为1，由于Java不含int128，因此本代码中部分位运算采用手动处理，时间复杂度O(n^3)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),p[][]=new int[n][2],idx[]=new int[n];
        long mask[][]=new long[n][2],start[]=new long[2],xor[][]=new long[n][2],ans[]=new long[2];//假设每一维的比特数最大为60位
        String s=sc.next();
        for(int i=0;i<n;i++){
            idx[i]=i;
            p[i]=new int[]{sc.nextInt(),sc.nextInt()};
            start[i/60]|=(long)(s.charAt(i)-'0')<<(i%60);
            xor[i][i/60]|=1L<<(i%60);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(p[i][0]==p[j][0]||p[i][1]==p[j][1]){
                    mask[i][j/60]|=1L<<(j%60);
                }
            }
        }
        for(int i=0;i<n;i++){
            int curIdx=i;
            for(int j=i+1;j<n;j++){
                if(findMaxBit(mask[idx[curIdx]])<findMaxBit(mask[idx[j]])){
                    curIdx=j;
                }
            }
            if(curIdx!=i){
                idx[i]^=idx[curIdx];
                idx[curIdx]^=idx[i];
                idx[i]^=idx[curIdx];
            }
            int cur=findMaxBit(mask[idx[i]]);
            if(cur==-1){
                break;
            }
            for(int j=i+1;j<n;j++){
                if(findMaxBit(mask[idx[j]])==cur){
                    mask[idx[j]]=findXor(mask[idx[j]],mask[idx[i]]);
                    xor[idx[j]]=findXor(xor[idx[j]],xor[idx[i]]);
                }
            }
        }
        for(int i=n-1,j=0;i>=0;i--){
            if((start[i/60]>>(i%60)&1)==0){
                while(j<n&&findMaxBit(mask[idx[j]])>i){
                    j++;
                }
                if(j==n||findMaxBit(mask[idx[j]])<i){
                    System.out.println("-1");
                    return;
                }
                start=findXor(start,mask[idx[j]]);
                ans=findXor(ans,xor[idx[j]]);
            }
        }
        System.out.println(Long.bitCount(ans[0])+Long.bitCount(ans[1]));
        for(int i=0;i<n;i++){
            if((ans[i/60]>>(i%60)&1)==1){
                System.out.print((i+1)+" ");
            }
        }
    }
    static long[] findXor(long a[],long b[]){
        //128位的异或
        return new long[]{a[0]^b[0],a[1]^b[1]};
    }
    static int findMaxBit(long a[]){
        for(int i=100;i>=0;i--){
            if((a[i/60]>>(i%60)&1)==1){
                return i;
            }
        }
        return -1;
    }
}