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

A题：
对于区间加减，最后查询的题目一般想到差分+前缀和。
注意：这里不是全局变量，数组的初始值不为0，所以要memset一遍。
代码如下：

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

时间复杂度 O(max(n,m))

B题：
首先可以枚举第二个盘子和第三个盘子分别放多少个，问题就转化为求a+2b+5c=x的非负整数解的个数。
然后就和上一场的T2一样，打表找规律。
发现对于每个x，解的个数即为 round((x+4) (x+4) 20)。
注意：double的精确度不够，请使用long double
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long wwork(int n) {
        if(n==0)return 0;
        long long ans=0;
        for(long long i=0;i<=1;i++)
            for(long long j=0;j<=4;j++){
                long long s=n-i-j;
                if(s<0)continue;
                ans=ans+round((long double)(s+4)*(s+4)/20.0);
            }
        return ans;
    }
};

时间复杂度 O(1)

C题：
组合计数。
先对a数组排序，记录每个数的id（后面输出答案要用到）。
对于排序后的第i个数，它的概率就是C(i-1,k)/C(n,k)。
因为只能线性求取C(i-1,k)，所以需要把组合数的式子展开后线性求解。
同时p是质数，所以直接用费马小定理求逆元即可。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param k int整型 
     * @param Point int整型vector 
     * @return int整型vector
     */
    pair<long long,long long>f[200010];
    long long s[200010],p=(1e9)+7,ans[200010];
    vector<int>anss;
    long long power(long long x,long long y){
        long long ans=1;
        while(y){
            if(y&1)ans=ans*x%p;
            x=x*x%p;
            y>>=1;
        }
        return ans;
    }
    vector<int> city(int n, int k, vector<int>& Point) {
        s[k-1]=1;
        for(int i=k;i<=n;i++)
        s[i]=s[i-1]*i%p*power(i-k+1,p-2)%p;
        long long ss=1;
        for(int i=n-k+1;i<=n;i++)
            ss=ss*i%p;
        for(int i=1;i<=k;i++)
            ss=ss*power(i,p-2)%p;
        for(int i=1;i<=n;i++){
            f[i].first=Point[i-1];
            f[i].second=i;
        }
        sort(f+1,f+n+1);
        for(int i=k;i<=n;i++)
        ans[f[i].second]=(s[i-1]*power(ss,p-2)%p);
        for(int i=1;i<=n;i++)
            anss.push_back(ans[i]);
        return anss;
    }
};

时间复杂度 O(n log p)