hihocoder60

题目1 : hohahola
二分

package l601;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt(),z=sc.nextInt();
        long lo=0,hi=n;
        while(lo+1<hi) {
            long mid=lo+(hi-lo)/2;
            if(ok(n,x,y,z,mid))
                lo=mid;
            else
                hi=mid-1;
        }
        if((x-y)*hi<=z*(n-hi))
            System.out.println(hi);
        else
            System.out.println(lo);
    }

    private static boolean ok(long n, long x, long y, long z, long mid) {
        if(z>=y) return n*z>=mid*x;
        return (x-y)*mid<=z*(n-mid);
    }
}

题目2 : 最大顺子
比赛思路是DP，但是MLE
答案是遍历数组，考虑以当前位置的数开始能不能做成顺子，至于能不能就二分

package l602;

import java.util.Arrays;
import java.util.Scanner;

public class Copy_3_of_Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        Arrays.sort(a);
        int[][]dp1=new int[n][m+1];
        
        // 难道要用TreeMap保存结果？
        for(int j=0;j<=m;j++) dp1[0][j]=Math.max(1, a[0]-j);
        for(int i=1;i<n;i++) {
            for(int j=0;j<=m;j++) {
                if(j>=(a[i]-a[i-1]-1)) 
                    dp1[i][j] = dp1[i-1][j-(a[i]-a[i-1]-1)];
                else
                    dp1[i][j] = a[i]-j;
            }
        }
        
        int res=-1;
        
        int[]dp21=new int[m+1], dp22=new int[m+1];
        for(int j=0;j<=m;j++) {
            dp21[j]=a[n-1]+j;
            int left = dp1[n-1][m-j], right=dp21[j];
            if(right-left+1>=k)
                res=Math.max(res, right);
        }
        for(int i=n-2;i>=0;i--) {
            for(int j=0;j<=m;j++) {
                if(j>=(a[i+1]-a[i]-1)) 
                    dp22[j] = dp21[j-(a[i+1]-a[i]-1)];
                else
                    dp22[j] = a[i]+j;
            }
            
            for(int j=0;j<=m;j++) {
                int left = dp1[i][m-j], right=dp22[j];
                if(right-left+1>=k)
                    res=Math.max(res, right);
            }
            
            int[] tmp=dp21;
            dp21=dp22;
            dp22=tmp;
        }
        
        System.out.println(res);
    }
}

package l602;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        Arrays.sort(a);
        int res=-1;
        
        for(int i=0;i<n;i++) {
            int tmp = a[i]+k-1;
            int p = Arrays.binarySearch(a, tmp);
            if(p<0) p=-(p+1)-1;
            if(p-i+1+m>=k) res=Math.max(res, a[i]+k-1);
        }
        System.out.println(res);
    }
}

题目3 : 路径包含问题
思路就是先求LCA，判断一个是不是另外一个的root，然后分类讨论
可能是因为数字版的dfs，所以下一次就感觉有点难，其实如果熟悉了数字版的，这就跟树的遍历一样。
因为是数字，其实还更好求LCA这些，我是记录path，然后复制试一下，但是这样MLE了，别人是先构造好数组，然后控制index直接填，可能更高效。搞OI的人还是太屌了

package l603;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        List<Integer>[]ms=new List[n+1];
        for(int i=1;i<=n;i++) ms[i]=new ArrayList<Integer>();
        for(int i=1;i<n;i++) {
            int x=sc.nextInt(),y=sc.nextInt();
            ms[x].add(y);
        }
        
        int[] sz=new int[n+1], dep=new int[n+1];
        List<Integer>[]paths=new List[n+1];
        List<Integer>path=new ArrayList<Integer>();
        path.add(1);
        dfs(1, 0, sz, dep, ms, paths, path);
        
        while(m-->0) {
            int a=sc.nextInt(),b=sc.nextInt();
            int lca = getLCA(paths[a], paths[b]);
            if(lca==a) System.out.println(sz[b]*(n-sz[getExtra(paths[b], a)]));
            else if(lca==b) System.out.println(sz[a]*(n-sz[getExtra(paths[a], b)]));
            else System.out.println(sz[a]*sz[b]);
        }
    }

    private static int getExtra(List<Integer> l, int b) {
        int i=0;
        while(l.get(i)!=b) i++;
        return l.get(i+1);
    }

    private static int getLCA(List<Integer> a, List<Integer> b) {
        int i=0;
        for(;i<a.size()&&i<b.size();i++){
            if(a.get(i)!=b.get(i)) break;
        }
        return a.get(i-1);
    }

    private static void dfs(int x, int d, int[] sz, int[] dep, List<Integer>[] ms, List<Integer>[] paths, List<Integer> path) {
        paths[x]=new ArrayList<Integer>(path);
        sz[x]=1;
        dep[x]=d;
        for(int i=0;i<ms[x].size();i++) {
            int to = ms[x].get(i);
            path.add(to);
            dfs(to, d+1, sz, dep, ms, paths, path);
            path.remove(path.get(path.size()-1));
            sz[x] += sz[to];
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,mod=323232323,inf=0x3f3f3f3f;
int n,m,k,t,fa[20][maxn],sz[maxn],dep[maxn],last;
vector<int>e[maxn];
void dfs(int x,int y=0)
{
    dep[x]=dep[y]+1;
    for(int i=1;fa[i-1][fa[i-1][x]];++i)
        fa[i][x]=fa[i-1][fa[i-1][x]];
    sz[x]=1;
    for(auto z:e[x])
    {
        if(z==y)continue;
        fa[0][z]=x;
        dfs(z,x);
        sz[x]+=sz[z];
    }
}
int lca(int x,int y)
{
    if(dep[x]>dep[y])
        swap(x,y);
    for(int i=19;i>=0;i--)
    {
        if(dep[fa[i][y]]>dep[x])
            y=fa[i][y];
    }
    if(fa[0][y]==x)
    {
        last=y;
        return x;
    }
    if(dep[fa[0][y]]>=dep[x])
        y=fa[0][y];
    for(int i=19;i>=0;i--)
    {
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],
            y=fa[i][y];
    }
    return fa[0][x];
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=2;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int fa=lca(x,y);
        if(fa==x)
            printf("%lld\n",(long long)(n-sz[last])*sz[y]);
        else if(fa==y)
            printf("%lld\n",(long long)(n-sz[last])*sz[x]);
        else printf("%lld\n",(long long)sz[x]*sz[y]);
    }
    return 0;
}