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

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

D 小红的数学题

假设方程的两个根分别是a和b，那么根据韦达定理，a+b==p,ab==q，可推出(a+1)(b+1)==k+1，枚举验证即可，时间复杂度O(sqrt(k))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long k=sc.nextLong();
        for(long i=1;i*i<=k+1;i++){
            if((k+1)%i==0&&i>1&&(k+1)/i>1){
                System.out.println(i+(k+1)/i-2+" "+(i-1)*((k+1)/i-1));
                return;
            }
        }
        System.out.println(-1);
    }
}

E 小红的ds题

逐层填充即可，时间复杂度O(sum(a))

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],sum=0,next[][]=new int[(int)1e5+5][2];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
        }
        for(int i=1;i<=sum;i++){
            next[i]=new int[]{-1,-1};
        }
        Queue<Integer> last=new LinkedList<>();
        last.add(1);
        System.out.println(1);
        for(int i=1,j=1;i<n;i++){
            //j代表的本层的新节点
            Queue<Integer> cur=new LinkedList<>();
            while(a[i]!=0){
                int p=last.poll();
                j++;
                next[p][0]=j;
                cur.add(j);
                a[i]--;
                if(a[i]!=0){
                    a[i]--;
                    j++;
                    next[p][1]=j;
                    cur.add(j);
                }
            }
            last=cur;
        }
        for(int i=1;i<=sum;i++){
            System.out.println(next[i][0]+" "+next[i][1]);
        }
    }
}

F 小红的小苯题

参考资料，时间复杂度O(nm)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),xor=0;
        for(int i=1;i<=n+m;i++){
            xor^=i;
        }
        if(xor!=0){
            System.out.println(-1);
        }
        else{
            boolean rev=n>m;
            if(rev){
                n^=m;
                m^=n;
                n^=m;
            }
            int ans[][]=new int[n][m];
            for(int i=1,idx1=0,idx2=0;i<=m;i++){
                ans[idx1][idx2]=i;
                idx1=Math.min(idx1+1,n-1);
                idx2++;
            }
            //处理最后一列：
            for(int i=0,cur=m;i<n-1;i++,cur++){
                ans[i][m-1]=ans[i][i]^cur;
            }
            ans[n-1][m-1]=n+m;
            for(int i=0;i<m-1;i++){
                ans[n-1][m-1]^=ans[n-1][i];
            }
            if(rev){
                for(int i=0;i<m;i++){
                    for(int j=0;j<n;j++){
                        System.out.print(ans[j][i]+" ");
                    }
                    System.out.println();
                }
            }
            else{
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        System.out.print(ans[i][j]+" ");
                    }
                    System.out.println();
                }
            }
        }
    }
}