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

A

使用差分来维护，最后特判即可

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回m天后高度为奇数的树的数量
     * @param n int整型 
     * @param m int整型 
     * @param l int整型vector 
     * @param r int整型vector 
     * @return int整型
     */
    int sum[200050];
    int oddnumber(int n, int m, vector<int>& l, vector<int>& r) {
        // write code here
        memset(sum,0,sizeof(sum));
        for(int i=0;i<l.size();i++){
            sum[l[i]]++;
            sum[r[i]+1]--;
        }
        sum[0]=m;
        for(int i=0;i<=n;i++){
            sum[i]+=sum[i-1];
        }
        int x = 0;
        for(int i=1;i<=n;i++){
            if(sum[i]&1)x++;
        }
        return x;
    }
};

B

生成函数的题目，根据题意得到下面五个函数
进行麦克劳林展开得到n的系数为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long wwork(int n) {
        // write code here
        return 1ll*(n+1)*(n+2)/2;
    }
};

C

总共有个选择方案，假设有m个数必a[i]小，那么概率为

#define ll long long 
const int mod = 1e9+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param k int整型 
     * @param Point int整型vector 
     * @return int整型vector
     */
    static const int N = 2E5+10;
    int fac[N],Inv[N];
    ll quick_pow(ll x,int y){
        ll res = 1;
        while(y){
            if(y&1)res=res*x%mod;
            x=x*x%mod;
            y>>=1;
        }
        return res;
    }
    void init(){
        memset(fac,0,sizeof(fac));
        memset(Inv,0,sizeof(Inv));
        fac[0]=1;
        for(int i=1;i<N;i++){
            fac[i]=1ll*i*fac[i-1]%mod;
        }
        Inv[N-1]=quick_pow(fac[N-1],mod-2);
        for(int i=N-2;i>=0;i--)Inv[i]=1ll*Inv[i+1]*(i+1)%mod;
    }
    ll C(int n,int m){
        if(m>n)return 0;
        return 1ll*fac[n]*Inv[n-m]%mod*Inv[m]%mod;
    }
    vector<pair<int,int>>vp;
    vector<int> city(int n, int k, vector<int>& Point) {
        // write code here
        init();
        for(int i=0;i<Point.size();i++){
            vp.push_back({Point[i],i});
        }
        sort(vp.begin(),vp.end());
        vector<int>ans(Point.size(),Point.size());
        ll fm = quick_pow(C(n,k),mod-2);
        for(int i=0;i<vp.size();i++){
            auto s = vp[i];
            ll fz = C(i,k-1);
            ans[s.second] = fz*fm%mod;
        }
        return ans;
    }
};