题解 | 牛客周赛 Round 100 CDEFG Java题解

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

C 小红的双排列删除

先考虑第一个数字，它只能跟后边的那个自己一组删除，不妨先删除这个前缀，而剩下的数字亦可以进行一样的操作，因此只需要持续此种操作，直到数组为空或者首次找不到配对儿的数字为止，时间复杂度O(Tn)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=Integer.parseInt(bf.readLine());i!=0;i--){
            Queue<Integer> q=new LinkedList<>();
            bf.readLine();
            StringTokenizer st=new StringTokenizer(bf.readLine());
            while(st.hasMoreTokens()){
                q.add(Integer.parseInt(st.nextToken()));
            }
            boolean ok=true;
            while(!q.isEmpty()){
                ok=false;
                int a=q.poll();
                while(!q.isEmpty()){
                    int b=q.poll();
                    if(b==a){
                        ok=true;
                        break;
                    }
                }
                if(!ok){
                    break;
                }
            }
            bw.write(ok?"Yes\n":"No\n");
        }
        bw.flush();
    }
}

D 小红的双排列权值

先求出原始数组的权值之和，而为了使得权值增大，只能将某两个区间不想交的数字区间，前者的右端点和后者的左端点交换，从而使得两个区间的长度变大，而变化量则是交换下标之差的两倍，因此找到最小的右端点以及最大的左端点即可，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),l[]=new int[n+5],maxLIdx=-1,minRIdx=n*2+5;
        long ans=0;
        for(int i=1;i<=n*2;i++){
            int a=sc.nextInt();
            if(l[a]==0){
                l[a]=i;
                maxLIdx=i;
            }
            else{
                ans+=i-l[a]-1;
                if(minRIdx>n*2){
                    minRIdx=i;
                }
            }
        }
        System.out.println(ans+Math.max(0,(maxLIdx-minRIdx))*2);
    }
}

E 小红的双排列删除得分

删除的过程一定是从前到后一段一段删除，但是可能不连续，但是区间一定是按顺序的，因此，直接线性的动态规划即可，规划数组可设为删除到当前下标的的最大前缀得分，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),idx[]=new int[n+5];
        long max[]=new long[n*2+5],pre[]=new long[n*2+5];
        for(int i=1;i<=n*2;i++){
            int a=sc.nextInt();
            pre[i]=pre[i-1]+a;
            max[i]=max[i-1];
            if(idx[a]==0){
                idx[a]=i;
            }
            else{
                max[i]=Math.max(max[i],max[idx[a]-1]+pre[i]-pre[idx[a]-1]);
            }
        }
        System.out.println(max[n<<1]);
    }
}

F 小红的双排列期望（easy）

有贪心可得，b越大，越适合匹配更大的数字，因此先把b排序，按顺序匹配双排列中的数字，而经过简单推导可得，数字增大1的次数期望为1/b，因此直接计算即可，时间复杂度O(nlog(n*mod))

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Queue<Integer> q=new PriorityQueue<>();
        for(int i=0;i<n*2;i++){
            q.add(sc.nextInt());
        }
        long ans=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<2;j++){
                ans=(ans+pow(q.poll(),mod-2)*i)%mod;
            }
        }
        System.out.println(ans*100%mod);
    }
    static long pow(long a,long b){
        return b==0?1:b==2?a*a%mod:pow(pow(a,b>>1),2)*(b%2==1?a:1)%mod;
    }
}

G 小红的双排列期望（hard）

参考资料，时间复杂度O(nlogn+1e7)

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,pre[][]=new long[105][100005];
    static{
        for(int i=1;i<=100;i++){
            long p=i*pow(100,mod-2)%mod;
            pre[i][1]=pow(p,mod-2);
            for(int j=2;j<=100000;j++){
                //f(j)=p+(1-p)*(1+f(j-1)+f(j))
                //f(j)=(1+(1-p)f(j-1))/p
                pre[i][j]=(pre[i][j-1]+(1+(pre[i][j-1]-pre[i][j-2])*(1-p))%mod*pre[i][1]%mod+mod)%mod;
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Queue<Integer> q=new PriorityQueue<>();
        for(int i=0;i<n*2;i++){
            q.add(sc.nextInt());
        }
        long ans=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<2;j++){
                ans=(ans+pre[q.poll()][i])%mod;
            }
        }
        System.out.println(ans);
    }
    static long pow(long a,long b){
        return b==0?1:b==2?a*a%mod:pow(pow(a,b>>1),2)*(b%2==1?a:1)%mod;
    }
}