题解 | 牛客小白月赛91 DEFG

Bingbong的化学世界

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

首先需要对一位数和多位数分别计数。一位数的好算，就是字符串里偶数的个数，对于多位数，需要在遍历到偶数的时候，累加上之前跟所有非零数字中间数字的“选或者不选”，也就是2的多少次方，这个技巧可以用前缀和的思想，时间复杂度O(n)

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String s=sc.next();
        long ans=0,pre=0;
        for(int i=0;i<n;i++){
            if(i>0&&s.charAt(i-1)!='0'){
                pre++;
            }
            if(s.charAt(i)%2==0){
                ans=(ans+pre+1)%mod;
            }
            pre=pre*2%mod;
        }
        System.out.println(ans);
    }
}

E Bingbong的字符串世界

对于每个字符串，找到可以完整配成子序列的最早位置，中间的长度就是可以的末尾，时间复杂度O(n(len(s1)+len(s2))，本题中s1="ACCEPT",s2="WA

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),next[][]=new int[n+1][26];
        Arrays.fill(next[n],n);
        String s=sc.next();
        for(int i=n-1;i>=0;i--){
            next[i]=next[i+1].clone();
            next[i][s.charAt(i)-'A']=i;
        }
        long ans=0;
        for(int i=0;i<n;i++){
            //end1是字符串最左边的可能终点，end2-1是最右边的终点
            int end1=find(n,i-1,next,"ACCEPT"),end2=find(n,i-1,next,"WA");
            ans+=Math.max(0,end2-Math.max(end1,i+k-1));
        }
        System.out.println(ans);
    }
    static int find(int n,int start,int next[][],String s){
        //寻找s作为子列的最左边下标
        for(char c:s.toCharArray()){
            start++;
            start=next[start][c-'A'];
            if(start==n){
                break;
            }
        }
        return start;
    }
}

F Bingbong的幻想世界

对于每个数，计算对于前边的贡献，再乘以对后边贡献的次数，时间复杂度O(nlogC)，其中C=1e6

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[][]=new int[20][2];
        long ans=0;
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            for(int j=0;j<20;j++){
                int b=a>>j&1;
                count[j][b]=(count[j][b]+i+1)%mod;
                ans=(ans+(1L<<j)*count[j][b^1]%mod*(n-i))%mod;
            }
        }
        System.out.println(ans*2%mod);
    }
}

G Bingbong的回文路径

方法一：总体思路就是字符串哈希，每个节点向根节点方向幂次上升和下降各哈一次，可用倍增的方法进行，正反哈希值比较，核心算法时间复杂度O((n+q)*logn)

题解 | 牛客小白月赛91 DEFG

全站热榜