题解 | 牛客周赛 Round 58 CEFG Java题解

会赢吗？

https://ac.nowcoder.com/acm/contest/89510/A

CEFG Java题解~

笨方法可以反推在原点的时候的胜负态，记忆化搜索，时间复杂度O(Txy)

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++){
            int x=sc.nextInt(),y=sc.nextInt();
            if(x<0||y<0){
                System.out.println("PING");
            }
            else{
                int ans=find(x,y,0,0,new int[x+5][y+5]);
                System.out.println(ans==1?"YES":ans==2?"NO":"PING");
            }
        }
    }
    static int find(int x,int y,int a,int b,int arr[][]){
        //0：未处理，1：赢，2：输，3：平局
        if(a>x||b>y){
            return 3;
        }
        if(a==x&&b==y){
            return 2;
        }
        if(arr[a][b]==0){
            int p=find(x,y,a+1,b,arr),q=find(x,y,a,b+1,arr);
            arr[a][b]=p==1&&q==1?2:p==2||q==2?1:3;
        }
        return arr[a][b];
    }
}

事实上，只需要考虑在第一象限和正半轴的点，如果x==y那么后手只需要跟先手每次走一样的就能赢，若是差距为1，先手需要先向多出来的方向走一下，之后就是后手必应策略，其他情况平局，时间复杂度O(T)

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++){
            int x=sc.nextInt(),y=sc.nextInt();
            System.out.println(x<0||y<0?"PING":x==y?"NO":Math.abs(x-y)==1?"YES":"PING");
        }
    }
}

E 好好好数组

待续

F 随机化游戏时间？

求区间内的第k小数字，可持续化线段树，时间复杂度O(T(nlogn+m(logn)^2))

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 t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),m=sc.nextInt(),min=1,max=n;
            SegTree st[]=new SegTree[n+1];
            st[0]=new SegTree(1,n);
            build(st[0]);
            for(int j=1;j<=n;j++){
                st[j]=new SegTree(1,n);
                insert(st[j-1],st[j],sc.nextInt());
            }
            for(int j=0;j<m;j++){
                int l=sc.nextInt(),r=sc.nextInt(),k=sc.nextInt();
                if(k>0){
                    min=Math.max(min,binarySearch(st[l-1],st[r],n,k-1)+1);
                }
                max=Math.min(max,binarySearch(st[l-1],st[r],n,k));
            }
            System.out.println(pow(max-min+1,mod-2)+(max==min?" "+max:""));
        }
    }
    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 int binarySearch(SegTree st1,SegTree st2,int n,int target){
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(find(st2,1,mid)-find(st1,1,mid)<=target){
                l=mid;
            }
            else{
                r=mid-1;
            }
            if(l==r-1){
                if(find(st2,1,r)-find(st1,1,r)<=target){
                    l=r;
                }
                break;
            }
        }
        return l;
    }
    static int find(SegTree st,int a,int b){
        //寻找树中的[a,b]区间的频数
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            return st.count;
        }
        else{
            int mid=(l+r)>>1;
            if(b<=mid){
                return find(st.left,a,b);
            }
            else if(a>mid){
                return find(st.right,a,b);
            }
            return find(st.left,a,mid)+find(st.right,mid+1,b);
        }
    }
    static void insert(SegTree st1,SegTree st2,int a){
        //将数字a插入到st2中
        int l=st1.l,r=st1.r;
        st2.count=st1.count+1;
        if(l<r){
            int mid=(l+r)>>1;
            if(a<=mid){
                st2.left=new SegTree(l,mid);
                insert(st1.left,st2.left,a);
                st2.right=st1.right;
            }
            else{
                st2.right=new SegTree(mid+1,r);
                insert(st1.right,st2.right,a);
                st2.left=st1.left;
            }
        }
    }
    static void build(SegTree st){
        int l=st.l,r=st.r;
        st.count=0;
        if(l<r){
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left);
            build(st.right);
        }
    }
}
class SegTree{
    int l,r,count;
    SegTree left,right;
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

G 随机化游戏时间！

设定前缀和为前缀中小于等于幸运数的个数，那么差分约束分别正反求得最长路，之家的数字就是可能得幸运数，采用堆优化，时间复杂度O((m+n)log(m+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++){
            int n=sc.nextInt(),m=sc.nextInt();
            List<int[]> path[]=new List[n+5];
            for(int j=0;j<=n;j++){
                path[j]=new ArrayList<>();
                if(j>0){
                    path[j-1].add(new int[]{j,0});
                    path[j].add(new int[]{j-1,-1});
                }
            }
            for(int j=0;j<m;j++){
                int l=sc.nextInt(),r=sc.nextInt(),k=sc.nextInt();
                path[l-1].add(new int[]{r,k});
                path[r].add(new int[]{l-1,-k});
            }
            int min=Math.max(1,find(0,n,path)),max=Math.min(n,find(n,n,path));
            for(int j=min;j<=max;j++){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }
    static int find(int start,int n,List<int[]> path[]){
        int pre[]=new int[n+1];
        Arrays.fill(pre,-n-10);
        pre[start]=0;
        Queue<int[]> q=new PriorityQueue<>((a,b)->Integer.compare(b[1],a[1]));
        q.add(new int[]{start,0});
        while(!q.isEmpty()){
            int a[]=q.poll();
            if(pre[a[0]]>a[1]){
                continue;
            }
            for(int b[]:path[a[0]]){
                int d=a[1]+b[1];
                if(d>pre[b[0]]){
                    pre[b[0]]=d;
                    q.add(new int[]{b[0],d});
                }
            }
        }
        return pre[n]-pre[0];
    }
}