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

while

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

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

容易观察到，连续至少两种数字的集合，点与点之间可以相互到达，因为可以利用相邻的数字作为桥；连续一种数字，则需要组内数字连边至少成树；；而以上的组之间需要至少连边成树，时间复杂度(Tnlogn)

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

E 小苯的矩阵反转

考虑三种情况：1：矩阵有一个位置为0，且所在行列的其他的位子都是1，矩阵其他的位置都是0；2：有两列全是1其他列全是0，或者所有列都为1；3：情况2换为行；时间复杂度O(Tnm)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),m=sc.nextInt(),row[]=new int[n],col[]=new int[m],sum=0,row0=0,row1=0,col0=0,col1=0;
            boolean ok=false;
            String s[]=new String[n];
            for(int j=0;j<n;j++){
                s[j]=sc.next();
                for(int k=0;k<m;k++){
                    row[j]+=s[j].charAt(k)-'0';
                    col[k]+=s[j].charAt(k)-'0';
                    sum+=s[j].charAt(k)-'0';
                }
            }
            if(sum==m+n-2){
                for(int j=0;j<n;j++){
                    for(int k=0;k<m;k++){
                        if(s[j].charAt(k)=='0'&&row[j]+col[k]==sum){
                            ok=true;
                        }
                    }
                }
            }
            for(int j=0;j<n;j++){
                if(row[j]==0){
                    row0++;
                }
                else if(row[j]==m){
                    row1++;
                }
            }
            for(int j=0;j<m;j++){
                if(col[j]==0){
                    col0++;
                }
                else if(col[j]==n){
                    col1++;
                }
            }
            System.out.println(ok||row0+row1==n&&(row1==0||row1==2)||col0+col1==m&&(col1==0||col1==2)?"YES":"NO");
        }
    }
}

F 小苯的因子查询

考虑质因子，奇数因子中的质因子只能为奇数，一旦出现偶数则为偶因子，那么所求的因子分为两种，含有2的和不含2的，很明显跟踪的2的次数有关：

方法一：利用前缀和的思想，预处理1~1e6的所有2的因子数的前缀和，时间复杂度O(ClogC+Tlog(mod)),mod==998244353,C==1e6

import java.util.*;
public class Main{
    static long mod=998244353,ans[]=new long[(int)1e6+5];
    static{
        for(int i=2;i<=1e6;i++){
            ans[i]=ans[i-1];
            int cur=i;
            while((cur&1)==0){
                cur>>=1;
                ans[i]++;
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            System.out.print(pow(ans[sc.nextInt()]+1,mod-2)+" ");
        }
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}

方法二：直接计算前n个树中有多少2的各种（正）次方即可，用来统计2的总次幂，时间复杂度O(T(logn+log(mod)),mod==998244353

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),count=0;
            for(int j=1;(1<<j)<=n;j++){
                count+=n>>j;
            }
            System.out.print(pow(count+1,mod-2)+" ");
        }
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}

而分析上述代码可以发现，对于n的每一个比特位，最终的2的次幂计数即为该比特位变成低于它现在的各种比特位之和，也就是它本身的置为大小减去1，对于n的总体来说，就是比减去n的比特数量，因此时间复杂度O(Tlog(mod))

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            System.out.print(pow(n-Integer.bitCount(n)+1,mod-2)+" ");
        }
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}