题解 | 牛客小白月赛122 DEF Java题解

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

D x_to_y_2

因为最差可以直接让x右移63次然后或运算y，所以题目保证有解，，而或运算两次完全可以简化为或1次，那么或运算最多一次，因此连续尝试x右移0到62次，看之后的结果可否通过添加比特得到y（或者无需添加就是y）,时间复杂度O(63T)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            long x=sc.nextLong(),y=sc.nextLong(),ans=100;
            for(int i=0;i<63;i++){
                if((x>>i|y)==y){
                    ans=Math.min(ans,(x>>i)==y?i:i+1);
                }
            }
            System.out.println(ans);
        }
    }
}

E AsubB

对于中间的子数组[l,r],只需要验证从开头开始的与子数组的公共前缀子序列长度，与从末尾开始的与子数组的公共前后子序列长度之和大于等于子数组长度即可，预处理最长前后缀长度后再枚举lr即可，时间复杂度O(n^2)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n],left[]=new int[n],ans=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=1;i<n;i++){
            for(int j=i,k=0;j<n&&k<i;j++,k++){
                while(k<i&&a[k]!=a[j]){
                    k++;
                }
                if(k<i){
                    left[i]++;
                }
            }
        }
        for(int i=n-2;i>=0;i--){
            int cur=0;
            for(int j=i,k=n-1;j>=0&&k>i;j--,k--){
                while(k>i&&a[k]!=a[j]){
                    k--;
                }
                if(k>i){
                    cur++;
                }
            }
            for(int j=1;j<=i;j++){
                if(i-j+1<=left[j]+cur){
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

F v_calc

部分思路参考：链接，时间复杂度O(TnClogC),C==1024

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),alr[][]=new int[n][],count[]=new int[1<<10],ans=0;
            for(int i=0;i<n;i++){
                alr[i]=new int[]{sc.nextInt(),sc.nextInt(),sc.nextInt()};
            }
            for(int i=0;i<=alr[0][0];i++){
                count[i]=1;
            }
            for(int i=1;i<n;i++){
                int cur[]=new int[1<<10];
                if(i%2==0){
                    Trie trie=new Trie();
                    for(int j=0;j<(1<<10);j++){
                        insert(trie,j,count[j]);
                    }
                    for(int j=0;j<=alr[i][0];j++){
                        cur[j]=(find(trie,j,alr[i-1][2])-find(trie,j,alr[i-1][1]-1)+mod)%mod;
                    }
                }
                else{
                    for(int j=1;j<(1<<10);j++){
                        count[j]=(count[j]+count[j-1])%mod;
                    }
                    cur[0]=find(count,0,alr[i][0]);
                    for(int j=1;j<(1<<10);j++){
                        cur[j]=(find(count,j,j+alr[i][0])+find(count,-j,alr[i][0]-j))%mod;
                    }
                }
                count=cur;
            }
            for(int a:count){
                ans=(ans+a)%mod;
            }
            System.out.println(ans);
        }
    }
    static int find(int count[],int l,int r){
        l=Math.max(0,l);
        r=Math.min((1<<10)-1,r);
        return l>r?0:(count[r]-(l==0?0:count[l-1])+mod)%mod;
    }
    static int find(Trie trie,int a,int max){
        if(max<0){
            return 0;
        }
        int ans=0;
        Trie t=trie;
        for(int i=9;i>=0&&t!=null;i--){
            for(int j=0;j<(max>>i&1);j++){
                int b=(a>>i&1)^j;
                if(t.children[b]!=null){
                    ans=(ans+t.children[b].count)%mod;
                }
            }
            t=t.children[(a>>i&1)^(max>>i&1)];
            if(i==0&&t!=null){
                ans=(ans+t.count)%mod;
            }
        }
        return ans;
    }
    static void insert(Trie trie,int a,int val){
        Trie t=trie;
        for(int i=9;i>=0;i--){
            int b=a>>i&1;
            if(t.children[b]==null){
                t.children[b]=new Trie();
            }
            t=t.children[b];
            t.count=(t.count+val)%mod;
        }
    }
}
class Trie{
    int count=0;
    Trie children[]=new Trie[2];
}