题解 | 牛客周赛 Round 98 CDEF Java题解

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

C 小红与red

贪心，凡是遇到跟前边一样的字符，就换成既跟前边不一样，也跟后边不一样的字符，时间复杂度O(n)

import java.util.*;
public class Main{
   static char candidateChars[]={'r','e','d'};
   public static void main(String args[]){
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       char ans[]=sc.next().toCharArray();
       for(int i=1;i<n;i++){
           if(ans[i]==ans[i-1]){
               for(char c:candidateChars){
                   if(c!=ans[i-1]&&(i==n-1||c!=ans[i+1])){
                       ans[i]=c;
                       break;
                   }
               }
           }
       }
       System.out.println(new String(ans));
   }
}

D 小红与好数组

按数据模拟即可，时间复杂度O(很小)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        find(new ArrayList<>(),sc.nextInt());
    }
    static void find(List<Integer> list,int p){
        if(p==0){
            for(int a:list){
                System.out.print(a+" ");
            }
            System.out.println();
        }
        else{
            for(int i=1;i<=p;i++){
                if(list.size()>0&&i==list.get(list.size()-1)){
                    continue;
                }
                list.add(i);
                find(list,p-i);
                list.remove(list.size()-1);
            }
        }
    }
}

E 小红与gcd和sum

若固定了序列的gcd，那么所有该数的倍数均可以加到序列中来，因此只需记录数组中每个数字对于其约数的贡献即可，也就是累加到每种约数的和即可，时间复杂度分析：只考虑数组中存在数字的约数试探最大为1e5*sqrt(max(a))<=1e8，总时间复杂度为O(n*sqrt(C)+C),C==1e6

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long sum[]=new long[(int)1e6+5],ans=0;
        for(int i=sc.nextInt();i!=0;i--){
            int a=sc.nextInt();
            sum[a]+=a;
        }
        for(int i=1;i<=1e6;i++){
            if(sum[i]!=0){
                for(int j=1;j*j<=i;j++){
                    if(i%j==0&&i!=j){
                        sum[j]+=sum[i];
                        if(j!=1&&i/j!=j){
                            sum[i/j]+=sum[i];
                        }
                    }
                }
            }
        }
        for(int i=1;i<=1e6;i++){
            ans=Math.max(ans,sum[i]*i);
        }
        System.out.println(ans);
    }
}

F 小红与天使猫猫酱

推公式即可，对于所求，可知其通项公式为bn=(4*100^n+28*10^n+49)/81，其前n项之和为Sn=((100^(n+1)-100)*4/99+(10^(n+1)-10)/9*28+49n)/81，直接计算即可，时间复杂度O(log(mod))

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        //寻找sigma(a^n,n∈[1,n])的值
        //就是(a^(n+1)-a)/(a-1);
        System.out.println(((pow(100,n+1)-100+mod)*pow(99,mod-2)%mod*4+(pow(10,n+1)-10+mod)*pow(9,mod-2)%mod*28%mod+n%mod*49)%mod*pow(81,mod-2)%mod);
    }
    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;
    }
}