题解 | 牛客周赛 Round 106 BCDEF Java题解

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

B 小苯的数字折叠

按规则模拟即可，时间复杂度O(Tklogn)

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 n=sc.nextInt(),k=sc.nextInt(),ans=0;
            while(n!=findInv(n)&&ans<k){
                ans++;
                n+=findInv(n);
            }
            System.out.println(n+" "+(n==findInv(n)?ans:-1));
        }
    }
    static long findInv(long a){
        long ans=0;
        for(;a!=0;ans=ans*10+a%10,a/=10){}
        return ans;
    }
}

C 小苯的波浪加密器

其实不管区间有多长，呢每个区间最多尝试10个数字，时间复杂度O(T(n+100))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int a[]=new int[500005];
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),l1=sc.nextInt(),r1=sc.nextInt(),l2=sc.nextInt(),r2=sc.nextInt();
            for(int i=3;i<=n;i++){
                a[i]=sc.nextInt();
            }
            boolean found=false;
            for(int i=l1;i<=r1&&i<l1+10&&!found;i++){
                a[1]=i%10;
                for(int j=l2;j<=r2&&j<l2+10;j++){
                    a[2]=j%10;
                    found=true;
                    for(int k=3;k<=4&&k<=n;k++){
                        if(a[k-1]*a[k-2]%10!=a[k]){
                            found=false;
                        }
                    }
                    if(found){
                        System.out.println(i+" "+j);
                        break;
                    }
                }
            }
            if(!found){
                System.out.println("-1 -1");
            }
        }
    }
}

D 小苯的数字变换

两个数字可以变得相等，当且仅当它们都在同一个循环中，而又可以证明循环节长度为数字的二进制位数，时间复杂度O(32Tn)

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--){
            int n=sc.nextInt(),a[]=new int[n],ans=0;
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            for(int i=0,j=n-1;i<j&&ans>=0;i++,j--){
                Map<Integer,Integer> map=new HashMap<>();
                for(int k=0;!map.containsKey(a[i]);k++,a[i]^=a[i]>>1){
                    map.put(a[i],k);
                }
                ans=map.containsKey(a[j])?ans+Math.min(map.get(a[j]),map.size()-map.get(a[j])):-1;
            }
            System.out.println(ans);
        }
    }
}

E 小苯的洞数组构造

每种洞数都有最小的数字可以达到，要么全用8，要么首位是4，当洞数是0则需要是1，因此贪心天池即可，时间复杂度O(T(n+10))

import java.util.*;
public class Main{
    static long candidate[]={1,4,8,48,88,488,888,4888,8888,48888,88888,488888,888888,4888888,8888888,48888888,88888888,488888888,888888888,4888888888L,8888888888L};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt();
            long sum=Math.min(sc.nextLong(),n*candidate[20]);
            if(sum<n){
                System.out.println(-1);
            }
            else{
                for(int i=20;i>=0;i--){
                    if(n*candidate[i]<=sum){
                        for(int j=0;j<n;j++){
                            System.out.print((j<(sum-candidate[i]*n)/(candidate[i+1]-candidate[i])?candidate[i+1]:candidate[i])+" ");
                        }
                        System.out.println();
                        break;
                    }
                }
            }
        }
    }
}

F 小苯的数组计数

对于每个左边界，假设右边界比它大，那么若存在，这样的右边界有且仅有一个，就是最近的大约它的数，反向同理，但是需要去除最近的同值在区间内的情况，时间复杂度O(Tn)

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--){
            int n=sc.nextInt(),a[]=new int[n],ans=0,next[]=new int[n];
            Stack<Integer> stack=new Stack<>();
            Map<Integer,Integer> map=new HashMap<>();
            Arrays.fill(next,n);
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
                while(!stack.isEmpty()&&a[i]>a[stack.peek()]){
                    next[stack.pop()]=i;
                }
                stack.push(i);
            }
            for(int i=n-1;i>=0;i--){
                if(next[i]<n&&next[i]-i>1&&next[i]<map.getOrDefault(a[i],n)){
                    ans++;
                }
                map.put(a[i],i);
            }
            stack.clear();
            map.clear();
            Arrays.fill(next,-1);
            for(int i=n-1;i>=0;i--){
                while(!stack.isEmpty()&&a[i]>a[stack.peek()]){
                    next[stack.pop()]=i;
                }
                stack.push(i);
            }
            for(int i=0;i<n;i++){
                if(next[i]>=0&&i-next[i]>1&&next[i]>map.getOrDefault(a[i],-1)){
                    ans++;
                }
                map.put(a[i],i);
            }
            System.out.println(ans);
        }
    }
}