牛客编程巅峰赛S2第11场 - 钻石&王者 做题记录

t1 差分数组

    public int oddnumber (int n, int m, int[] l, int[] r) {
        // write code here
        int[] book = new int[n+2];
        book[0]=m;
        for(int i=0;i<l.length;++i){
            book[l[i]]++;
            book[r[i]+1]--;
        }
        int ans =0;

        int sum = book[0];
        for(int i=1;i<book.length-1;++i){
            sum +=book[i];
            if((sum &1) ==1){
                ans++;
            }
        }
        return ans;
    }

t2 找规律+隔板法
x+y+z+2a+5b
y<=1
z<=4
分组 x + (2a+y) + (5b+z) 为三个任意整数之和
题目转化为三个任意整数之和为n 有几种情况

    public long wwork (int n) {
        // write code here
        return ((long)(n+2))*(n+1)/2;
    }

t3 带预处理的乘法逆元求组合数

    int mod =1000000007;
    long[] fac;
    public int[] city (int n, int k, int[] Point) {
        // write code here
        fac=new long[n+1];
        fac[1] = 1;
        for(int i = 2; i <= n; i++){
            fac[i] = fac[i - 1] * 1L * i % mod;
        }


        long max = inv(c(n,k));
        //按照位置  第i高的 出现 C(n-i,k-1)次
        long[] res = new long[n+1];
        for(int i=k;i<=n;++i){ //C(i-1,k-1)
            res[i]=c(i-1,k-1);
        }

        int[] paiming = Arrays.copyOf(Point, Point.length);
        Arrays.sort(paiming);
        Map<Integer,Integer> map = new HashMap<>();
        int mingci=1;
        for(int i= paiming.length-1;i>=0;--i){
            map.put(paiming[i],mingci++);
        }

        int[] ans = new int[n];
        for(int i=0;i<ans.length;++i){
            ans[i]=(int)((res[n-map.get(Point[i])+1]*max)%mod);
        }
        return ans;
    }

    public long c(int n, int m)
    {
        if(m > n || m < 0) return 0l;
        if(m == 0 || m == n) return 1l;
        long res = fac[n] * quickPow((fac[m] * fac[n - m]) % mod, mod - 2) % mod;
        return res;
    }
    public long quickPow(long base,long power){
        long result = 1;
        while(power>0){
            if( (power&1) ==1 ){
                result = (result*base)%mod;
            }
            power = power/2;
            base = (base*base )%mod;
        }
        return result;
    }

    public  long inv(long a){
        return quickPow(a,mod-2);
    }