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

D 小苯的最大和

删除一个长度为2或者3的段,等同于删除若干长度不为1的段,因此直接常规动态规划即可,时间 =复杂度O(Tn)

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();
            long max[]=new long[n+1];
            for(int j=1;j<=n;j++){
                max[j]=Math.max(sc.nextInt()+max[j-1],Math.max(j>=2?max[j-2]:-(long)1e18,j>=3?max[j-3]:-(long)1e18));
            }
            System.out.println(max[n]);
        }
    }
}

E 小苯的数组构造

拆位分解每一位,首先为了让数字可能大,不妨将答案填充为最大int数,之后按每一比特位进行分析:x位为0,y位为0,那么n个数的这一位全为0;x位为0,y位为1,不存在这杨的组合;x位为1,y位为0,n个数中填充的位数必须为偶数位,且不能一个也不填;x位为1,y位为1,与上一种情况类似;;以上的情况34是在固定位置操作的,可能将这个位置的数字减为0,因此需要将后边某一个非单比特置为数字拆解一位过来以保证全正,时间复杂度O(TnC),C==31

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(),x=sc.nextInt(),y=sc.nextInt(),ans[]=new int[n];
            Arrays.fill(ans,Integer.MAX_VALUE);
            boolean found=(x&y)==y;
            for(int j=30;j>=0&&found;j--){
                int a=x>>j&1,b=y>>j&1;
                if(a==0){
                    if(b==1){
                        found=false;
                    }
                    else{
                        for(int k=0;k<n;k++){
                            ans[k]^=1<<j;
                        }
                    }
                }
                else{
                    if(n%2!=b){
                        if(n==1){
                            found=false;
                        }
                        ans[0]^=1<<j;
                    }
                }
            }
            if(ans[0]==0){
                found=false;
                for(int j=1;j<n;j++){
                    if(Integer.bitCount(ans[j])>1){
                        ans[0]=ans[j]&-ans[j];
                        ans[j]&=ans[j]-1;
                        found=true;
                        break;
                    }
                }
            }
            if(!found){
                System.out.println("NO");
            }
            else{
                System.out.println("YES");
                for(int a:ans){
                    System.out.print(a+" ");
                }
                System.out.println();
            }
        }
    }
}

F 小苯的ovo2.0

最优的情况一定是将字符创分为三段,分别将问号填充为“ovo”,容易证明,交换相邻段的任意两个问号的取值并不会使得答案更优,因此枚举分界点即可,时间复杂度O(Tn^3)

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--){
           String s=sc.next();
           int n=s.length(),pre[][]=new int[n+1][3],ans=0;
           for(int j=1;j<=n;j++){
               pre[j]=pre[j-1].clone();
               pre[j][findIdx(s.charAt(j-1))]++;
           }
           for(int j=0;j<=n;j++){
               for(int k=j;k<=n;k++){
                   int count=0;
                   //[1,j,'o'],[j+1,k,'v],[k+1,n,'o']
                   for(int p=1;p<=n;p++){
                       count+=p<=j&&s.charAt(p-1)=='v'?(find(pre,'o',0,p-1)+find(pre,'?',0,p-1))*(find(pre,'o',p,j)+find(pre,'?',p,j)+find(pre,'o',j,k)+find(pre,'o',k,n)+find(pre,'?',k,n)):p>j&&p<=k&&s.charAt(p-1)!='o'?(find(pre,'o',0,j)+find(pre,'?',0,j)+find(pre,'o',j,p-1))*(find(pre,'o',p,k)+find(pre,'o',k,n)+find(pre,'?',k,n)):p>k&&s.charAt(p-1)=='v'?(find(pre,'o',0,j)+find(pre,'?',0,j)+find(pre,'o',j,k)+find(pre,'o',k,p-1)+find(pre,'?',k,p-1))*(find(pre,'o',p,n)+find(pre,'?',p,n)):0;
                   }
                   ans=Math.max(ans,count);
               }
           }
           System.out.println(ans);
        }
    }
    static int find(int pre[][],char c,int l,int r){
        return pre[r][findIdx(c)]-pre[l][findIdx(c)];
    }
    static int findIdx(char c){
        return c=='o'?0:c=='v'?1:2;
    }
}