C~F Java题解

C 连锁进位

其实是从最低位开始到次高位，判断把这一位加到10的倍数需要最少加几，注意需要考虑进位，时间复杂度O(sum(len(n)))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            String n=sc.next();
            int ans=0,carry=0;
            for(int j=n.length()-1;j>0;j--){
                int cur=n.charAt(j)-'0'+carry;
                if(cur%10!=0){
                    ans+=10-cur%10;
                    carry=1;
                }
                else{
                    carry=cur/10;
                }
            }
            System.out.println(ans);
        }
    }
}

D 因子区间

注意到1e5范围内的数字，因子数最多的有128个，因此可以分组考虑因子数的前缀和，本题求因子数采用暴力，时间复杂度为O(n*sqrt(C)+qd)，其中c==1e5 d==128

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),q=sc.nextInt(),pre[][]=new int[n+1][130];
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1].clone();
            pre[i][find(sc.nextInt())]++;
        }
        for(int i=0;i<q;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            long ans=0;
            for(int j=1;j<=128;j++){
                ans+=(long)(pre[r][j]-pre[l-1][j])*(pre[r][j]-pre[l-1][j]-1);
            }
            System.out.println(ans>>1);
        }
    }
    static int find(int a){
        int ans=1;
        for(int i=2;i*i<=a;i++){
            int count=0;
            while(a%i==0){
                count++;
                a/=i;
            }
            ans*=count+1;
        }
        return a==1?ans:ans<<1;
    }
}

E 小苯的排列构造

参考视频讲解，列举1到10的可以放在的下标位置，可观察到，n在小于8的时候无解，因为1最小可以在5,234同理，那么在n至少为8的时候，可以数字整体左移4，最后4个数一定在1234四个位置，按照奇偶性分配，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n<8){
            System.out.println("-1");
        }
        else{
            for(int i=5;i<=n;i++){
                System.out.print(i+" ");
            }
            System.out.println(n%2==0?"1 2 3 4":"2 1 4 3");
        }
    }
}

F 小红的基环树删边

1到n最多有两条路径，找到路径上的边即可判断删边后最短距离，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),dis[][]=new int[2][];
        List<int[]> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(new int[]{v,i+1});
            path[v].add(new int[]{u,i+1});
        }
        find(n,-1,1,path,new ArrayList<>(),dis,new boolean[n+5]);
        if(dis[1]==null){
            for(int i=1;i<=n;i++){
                System.out.println(dis[0][i]==1?"-1":dis[0][0]);
            }
        }
        else{
            for(int i=1;i<=n;i++){
                System.out.println(dis[0][i]==1&&dis[1][i]==1?"-1":dis[0][i]==1?dis[1][0]:dis[1][i]==1?dis[0][0]:Math.min(dis[0][0],dis[1][0]));
            }
        }
    }
    static void find(int n,int p,int k,List<int[]> path[],List<Integer> list,int dis[][],boolean has[]){
        has[k]=true;
        if(k==n){
            int j=0;
            while(dis[j]!=null){
                j++;
            }
            dis[j]=new int[n+5];
            dis[j][0]=list.size();
            for(int a:list){
                dis[j][a]=1;
            }
        }
        else{
            for(int a[]:path[k]){
                if(p!=a[0]&&!has[a[0]]){
                    list.add(a[1]);
                    find(n,k,a[0],path,list,dis,has);
                    list.remove(list.size()-1);
                }
            }
        }
        has[k]=false;
    }
}