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

小红的好数

https://ac.nowcoder.com/acm/contest/91592/A

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

好烦啊，瞎做呗，令上边俩角的元素相同，下边俩角的元素相同，可以消掉一部分，剩下的代数式分解因式即可拼凑，时间复杂度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)

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

全站热榜