题解 | 牛客练习赛134 BCDEF Java题解

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

B 江

固定转折列后，求和结果即为左半边的上一行加上右半边的下一行，而交换的情况有多种：交换在同一侧，无变化，交换在转换列的两侧，需要分别计算前后缀的最大交换贡献；而就还有一种情况是，交换的其中一列就是转折列，，，以上三种情况分别在枚举转折列即可，时间复杂度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(),a[][]=new int[n+5][2];
            for(int k=0;k<2;k++){
                for(int j=1;j<=n;j++){
                    a[j][k]=sc.nextInt();
                }
            }
            //计算前后缀之和，计算一些列前缀，后缀最大值
            long pre[]=new long[n+5],suf[]=new long[n+5],maxPreSum[]=new long[n+5],maxSufSum[]=new long[n+5],maxPre[]=new long[n+5],maxSuf[]=new long[n+5],ans=-(long)1e18;
            maxPreSum[0]=maxPre[0]=maxSuf[n+1]=maxSufSum[n+1]=-(long)1e18;
            for(int j=1;j<=n;j++){
                pre[j]=pre[j-1]+a[j][0];
                suf[n+1-j]=suf[n+2-j]+a[n+1-j][1];
                maxPreSum[j]=Math.max(maxPreSum[j-1],a[j][1]);
                maxSufSum[n+1-j]=Math.max(maxSufSum[n+2-j],a[n+1-j][0]);
                maxPre[j]=Math.max(maxPre[j-1],a[j][1]-a[j][0]);
                maxSuf[n+1-j]=Math.max(maxSuf[n+2-j],a[n+1-j][0]-a[n+1-j][1]);
            }
            //枚举转折点：
            for(int j=1;j<=n;j++){
                long cur=pre[j]+suf[j];
                //无交换
                ans=Math.max(ans,cur);
                //交换前后两列：
                ans=Math.max(ans,cur+maxPre[j-1]+maxSuf[j+1]);
                //交换前边与转折点：
                ans=Math.max(ans,cur-a[j][1]+maxPreSum[j-1]);
                //交换后边与转折点：
                ans=Math.max(ans,cur-a[j][0]+maxSufSum[j+1]);
            }
            System.out.println(ans);
        }
    }
}

C 花

手动计算前几项，即可知道每个数的贡献即为自身呈上斐波那契数列前若干项，因此直接用前缀和相乘即可，时间复杂度(Tn+1e6)

import java.util.*;
public class Main{
    static long facPre[]=new long[(int)1e6+5],mod=998244353;
    static {
        facPre[1]=1;
        for(int i=2;i<=(int)1e6+2;i++){
            facPre[i]=(facPre[i-1]+facPre[i-2])%mod;
        }
        for(int i=2;i<=(int)1e6+2;i++){
            facPre[i]=(facPre[i]+facPre[i-1])%mod;
        }
    }
    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 ans=0;
            for(int j=1;j<=n;j++){
                ans+=sc.nextInt()*(1+facPre[Math.max(0,n-j-1)]+facPre[j-1])%mod;
            }
            System.out.println(ans%mod);
        }
    }
}

D 月

大多数边都是全覆盖的，因此最基本的邻接表可以先用弗洛伊德算法算出来，而最多有q个边石需要区间覆盖的，因此可以使用延迟更新线段树分割时间轴，每次更新区间的时候，利用父节点的邻接矩阵，加上没被跟新过且全覆盖本区间的边，时间复杂度O(T(n^3+n^2qlogn))

import java.util.*;
public class Main{
    static long mod=998244353,inf=(long)1e18;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),m=sc.nextInt(),q=sc.nextInt();
            SegTree st[]=new SegTree[q<<2|3];
            st[1]=new SegTree(0,q);
            st[1].dis=new long[n+1][n+1];
            //[start,end,x,y,w]
            for(int j=0;j<m;j++){
                int u=sc.nextInt(),v=sc.nextInt(),w=sc.nextInt();
                st[1].edges.add(new int[]{0,q,u,v,w});
            }
            for(int j=1;j<=n;j++){
                Arrays.fill(st[1].dis[j],inf);
                st[1].dis[j][j]=0;
            }
            build(st,1);
            List<Integer> list=new ArrayList<>();
            for(int j=1;j<=q;j++){
                int op=sc.nextInt();
                if(op==1){
                    int x=sc.nextInt(),y=sc.nextInt(),w=sc.nextInt();
                    st[1].edges.add(new int[]{j,q,x,y,w});
                }
                else if(op==2){
                    st[1].edges.get(sc.nextInt()-1)[1]=j;
                }
                else{
                    list.add(j);
                }
            }
            //将全覆盖的边更新：
            for(int e[]:st[1].edges){
                if(e[0]==0&&e[1]==q){
                    st[1].dis[e[2]][e[3]]=st[1].dis[e[3]][e[2]]=Math.min(st[1].dis[e[3]][e[2]],e[4]);
                }
            }
            //弗洛伊德：
            for(int d=1;d<=n;d++){
                for(int j=1;j<=n;j++){
                    for(int k=1;k<=n;k++){
                        st[1].dis[j][k]=Math.min(st[1].dis[j][k],st[1].dis[j][d]+st[1].dis[d][k]);
                    }
                }
            }
            st[1].edges=find(st[1].edges,q);
            for(int a:list){
                System.out.println(find(st,1,a));
            }
        }
    }
    static long find(SegTree st[],int idx,int a){
        int l=st[idx].l,r=st[idx].r;
        if(l==r){
            long ans=0;
            for(int i=1;i<st[idx].dis.length;i++){
                for(int j=1;j<st[idx].dis.length;j++){
                    ans+=(st[idx].dis[i][j]==inf?0:st[idx].dis[i][j]);
                }
            }
            return ans%mod;
        }
        clear(st,idx,a<=(l+r)/2?0:1);
        return find(st,idx<<1|(a<=(l+r)/2?0:1),a);
    }
    static void clear(SegTree st[],int idx,int next){
        if(st[idx].l<st[idx].r&&st[idx<<1|next].dis==null){
            int n=st[idx].dis.length;
            st[idx<<1|next].dis=new long[n][];
            for(int i=1;i<n;i++){
                st[idx<<1|next].dis[i]=st[idx].dis[i].clone();
            }
            for(int a[]:st[idx].edges){
                if(a[0]!=-1&&!(a[0]>st[idx<<1|next].r||a[1]<st[idx<<1|next].l)){
                    st[idx<<1|next].edges.add(a.clone());
                }
            }
            update(st[idx<<1|next]);
        }
    }
    static void update(SegTree st){
        int l=st.l,r=st.r;
        for(int e[]:st.edges){
            if(e[0]<=l&&e[1]>=r){
                e[0]=-1;
                for(int i=1;i<st.dis.length;i++){
                    for(int j=1;j<st.dis.length;j++){
                        st.dis[i][j]=Math.min(st.dis[i][j],Math.min(st.dis[i][e[2]]+st.dis[e[3]][j],st.dis[i][e[3]]+st.dis[e[2]][j])+e[4]);
                    }
                }
            }
        }
    }
    static void build(SegTree st[],int idx){
        int l=st[idx].l,r=st[idx].r;
        if(l<r){
            int mid=(l+r)>>1;
            st[idx<<1]=new SegTree(l,mid);
            st[idx<<1|1]=new SegTree(mid+1,r);
            build(st,idx<<1);
            build(st,idx<<1|1);
        }
    }
    static List<int[]> find(List<int[]> list,int q){
        //将全覆盖的边去除
        List<int[]> ans=new ArrayList<>();
        for(int a[]:list){
            if(a[0]!=0||a[1]!=q){
                ans.add(a);
            }
        }
        return ans;
    }
}
class SegTree{
    int l,r;
    long dis[][];
    List<int[]> edges=new ArrayList<>();
    SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

E 夜

可启发式合并集合，在合并时，若是需要将大集合合并到小集合中，需要反向操作，并更改集合标记，因此实合并此时最多为n次，记录交集可用集合标记组合，时间复杂度T(nlogn+q)

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--){
            //group表示的是，某个元素实际上指向哪个位置，idx表示的是，每个组实际上指向哪个位置
            int n=Integer.parseInt(bf.readLine()),groupA[]=new int[n+5],groupB[]=new int[n+5],idxA[]=new int[n+5],idxB[]=new int[n+5];
            List<Integer> listA[]=new List[n+5],listB[]=new List[n+5];
            for(int j=1;j<=n;j++){
                listA[j]=new ArrayList<>();
                listB[j]=new ArrayList<>();
                idxA[j]=idxB[j]=j;
            }
            StringTokenizer st=new StringTokenizer(bf.readLine());
            for(int j=1;j<=n;j++){
                int a=Integer.parseInt(st.nextToken());
                groupA[a]=j;
                listA[j].add(a);
            }
            st=new StringTokenizer(bf.readLine());
            for(int j=1;j<=n;j++){
                int b=Integer.parseInt(st.nextToken());
                groupB[b]=j;
                listB[j].add(b);
            }
            Map<Long,Integer> map=new HashMap<>();
            for(int j=1;j<=n;j++){
                inc(map,(long)groupA[j]*(n+5)+groupB[j],1);
            }
            for(int j=Integer.parseInt(bf.readLine());j!=0;j--){
                st=new StringTokenizer(bf.readLine());
                int op=Integer.parseInt(st.nextToken()),idxI=Integer.parseInt(st.nextToken()),idxJ=Integer.parseInt(st.nextToken());
                if(op==1){
                    bw.write(map.getOrDefault((long)idxA[idxI]*(n+5)+idxB[idxJ],0)+"\n");
                }
                else if(op==2){
                    int p1=idxA[idxI],p2=idxA[idxJ];
                    //把小的集合都清空，元素全部放到大的集合里
                    if(listA[p1].size()<listA[p2].size()){
                        for(int a:listA[p1]){
                            listA[p2].add(a);
                            inc(map,(long)p1*(n+5)+groupB[a],-1);
                            inc(map,(long)p2*(n+5)+groupB[a],1);
                            groupA[a]=p2;
                        }
                        listA[p1].clear();
                        idxA[idxI]=p2;
                        idxA[idxJ]=p1;
                    }
                    else{
                        for(int a:listA[p2]){
                            listA[p1].add(a);
                            inc(map,(long)p2*(n+5)+groupB[a],-1);
                            inc(map,(long)p1*(n+5)+groupB[a],1);
                            groupA[a]=p1;
                        }
                        listA[p2].clear();
                    }
                }
                else{
                    int p1=idxB[idxI],p2=idxB[idxJ];
                    //把小的集合都清空，元素全部放到大的集合里
                    if(listB[p1].size()<listB[p2].size()){
                        for(int a:listB[p1]){
                            listB[p2].add(a);
                            inc(map,(long)groupA[a]*(n+5)+p1,-1);
                            inc(map,(long)groupA[a]*(n+5)+p2,1);
                            groupB[a]=p2;
                        }
                        listB[p1].clear();
                        idxB[idxI]=p2;
                        idxB[idxJ]=p1;
                    }
                    else{
                        for(int a:listB[p2]){
                            listB[p1].add(a);
                            inc(map,(long)groupA[a]*(n+5)+p2,-1);
                            inc(map,(long)groupA[a]*(n+5)+p1,1);
                            groupB[a]=p1;
                        }
                        listB[p2].clear();
                    }
                }
            }
        }
        bw.flush();
    }
    static void inc(Map<Long,Integer> map,long a,int b){
        map.put(a,map.getOrDefault(a,0)+b);
    }
}

F 。

参考资料

本题中利用线段树，需要维护的是每个叶子结点的相关信息，而且由于变化是线性的，因此可以生成一个转移矩阵，并为每个节点以一个转移矩阵最为懒标记，，，本题一开始略微卡常，因此在跟出题人沟通并得到帮助后，调大了时限，并修改了代码得以AC

import java.util.*;
import java.io.*;
public class Main{
    static int mod=998244353,addMatrix[][][]=new int[7][7][],mulMatrix[][][]=new int[7][7][],sumMatrix[][]=new int[7][7];
    static{
        for(int i=0;i<7;i++){
            for(int j=0;j<7;j++){
                addMatrix[i][j]=new int[2];
                mulMatrix[i][j]=new int[2];
            }
            addMatrix[i][i]=new int[]{1,0};
            sumMatrix[i][i]=1;
            mulMatrix[i][i]=new int[]{1,Math.max(0,5-i)};
            for(int j=i+1;j<6;j++){
                addMatrix[i][j]=new int[]{(int)comb(5-i,j-i),j-i};
            }
        }
        for(int i=0;i<5;i++){
            sumMatrix[6][i]=1;
        }
    }
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer sto=new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(sto.nextToken()),m=Integer.parseInt(sto.nextToken()),a[]=new int[n+5];
        sto=new StringTokenizer(bf.readLine());
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(sto.nextToken());
        }
        SegTree st[]=new SegTree[n<<2|3];
        st[1]=new SegTree(1,n);
        build(st,a,1);
        for(int i=0;i<m;i++){
            sto=new StringTokenizer(bf.readLine());
            int op=Integer.parseInt(sto.nextToken()),l=Integer.parseInt(sto.nextToken()),r=Integer.parseInt(sto.nextToken()),x=Integer.parseInt(sto.nextToken());
            modify(st,1,l,r,generate(op==1?addMatrix:mulMatrix,x));
            modify(st,1,1,n,sumMatrix);
        }
        for(int i=1;i<=n;i++){
            bw.write(find(st,1,i)+" ");
        }
        bw.flush();
        //System.out.println(st.val[6]);
    }
    static long find(SegTree st[],int idx,int a){
        int l=st[idx].l,r=st[idx].r;
        if(l==r){
            return mulVec(st[idx].mat,st[idx].val)[6];
        }
        clear(st,idx);
        return a<=(l+r)/2?find(st,idx<<1,a):find(st,idx<<1|1,a);
    }
    static void modify(SegTree st[],int idx,int a,int b,int mat[][]){
        int l=st[idx].l,r=st[idx].r;
        if(l==a&&r==b){
            st[idx].pushed=false;
            st[idx].mat=mulMatrix(mat,st[idx].mat);
        }
        else{
            clear(st,idx);
            int mid=(l+r)>>1;
            if(b<=mid){
                modify(st,idx<<1,a,b,mat);
            }
            else if(a>mid){
                modify(st,idx<<1|1,a,b,mat);
            }
            else{
                modify(st,idx<<1,a,mid,mat);
                modify(st,idx<<1|1,mid+1,b,mat);
            }
        }
    }
    static void build(SegTree st[],int a[],int idx){
        int l=st[idx].l,r=st[idx].r;
        if(l<r){
            int mid=(l+r)>>1;
            st[idx<<1]=new SegTree(l,mid);
            st[idx<<1|1]=new SegTree(mid+1,r);
            build(st,a,idx<<1);
            build(st,a,idx<<1|1);
        }
        else{
            st[idx].val=new int[7];
            for(int i=0;i<6;i++){
                st[idx].val[i]=(int)pow(a[l],5-i);
            }
        }
    }
    static void clear(SegTree st[],int idx){
        if(st[idx].l<st[idx].r&&!st[idx].pushed){
            st[idx].pushed=true;
            st[idx<<1].pushed=st[idx<<1|1].pushed=false;
            st[idx<<1].mat=mulMatrix(st[idx].mat,st[idx<<1].mat);
            st[idx<<1|1].mat=mulMatrix(st[idx].mat,st[idx<<1|1].mat);
            for(int i=0;i<7;i++){
                Arrays.fill(st[idx].mat[i],0);
                st[idx].mat[i][i]=1;
            }
        }
    }
    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;
    }
    static long comb(long a,long b){
        long ans=1;
        for(int i=1;i<=b;i++){
            ans=ans*(a-i+1)/i;
        }
        return ans;
    }
    static int[] mulVec(int a[][],int b[]){
        int ans[]=new int[7];
        for(int i=0;i<7;i++){
            long s=0;
            for(int j=0;j<7;j++){
                s+=(long)a[i][j]*b[j];
            }
            ans[i]=(int)(s%mod);
        }
        return ans;
    }
    static int[][] mulMatrix(int a[][],int b[][]){
        int ans[][]=new int[7][7];
        for(int i=0;i<7;i++){
            for(int j=0;j<7;j++){
                long s=0;
                for(int k=0;k<7;k++){
                    s+=(long)a[i][k]*b[k][j];
                }
                ans[i][j]=(int)(s%mod);
            }
        }
        return ans;
    }
    static int[][] generate(int g[][][],long a){
        int ans[][]=new int[7][7];
        for(int i=0;i<7;i++){
            for(int j=0;j<7;j++){
                ans[i][j]=(int)(g[i][j][0]*pow(a,g[i][j][1])%mod);
            }
        }
        return ans;
    }
}
class SegTree{
    int l,r;
    int val[],mat[][]=new int[7][7];
    boolean pushed=true;
    SegTree(int l,int r){
        this.l=l;
        this.r=r;
        for(int i=0;i<7;i++){
            mat[i][i]=1;
        }
    }
}