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

A题 牛牛浇树
可以使用差分，在a[l]++,在a[r+1]--,最后遍历一遍统计就行了。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回m天后高度为奇数的树的数量
     * @param n int整型 
     * @param m int整型 
     * @param l int整型vector 
     * @param r int整型vector 
     * @return int整型
     */

int a[500000];
  int oddnumber(int n, int m, vector<int>& l, vector<int>& r) {
        for(int i=0;i<m;i++)
        {
           a[l[i]]++;
           a[r[i]+1]--;
        }
        for(int i=1;i<=n;i++)
        a[0]=m;
        for(int i=1;i<=n;i++)
        a[i]+=a[i-1];
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]&1)
            ans++;
        }
        return ans;
    }
};

B题 挑选方案问题
我写了一个dfs打表找规律，发送n=3时 结果为 10. n等于4时 结果为15，符合二次函数sum=1/2*nn+3/2*n+1

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

C题 大逃离
先排序，每个点的概率为 因为有模运算，要采用逆元。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param k int整型 
     * @param Point int整型vector 
     * @return int整型vector
     */
typedef long long ll;
long long a[400000];
long long md = 1000000007;
struct node
{
    long long data;
    int id;
} b[400000];
static int cmp(node x, node y)
{
    return x.data < y.data;
}
long long c[400000];
ll ksm(ll x, ll y)
{
    ll sum = 1;
    while (y)
    {
        if (y & 1)
            sum = sum * x%md;
        y >>= 1;
        x = x * x%md;
    }
    return sum;
}
long long cxk(int x,int y)
{
    return a[y]*ksm(a[x]*a[y-x]%md,md-2)%md;
}
vector<int> city(int n, int k, vector<int> &Point)
{
    // write code here
    a[0] = 1;
    for (int i = 1; i <= 200000; i++)
    {
        a[i] = a[i - 1] * i % md;
    }
    for (int i = 0; i < n; i++)
    {
        b[i + 1].data = Point[i];
        b[i + 1].id = i + 1;
    }
    sort(b + 1, b + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        if (i < k)
        {
            c[b[i].id]=0;
        }
        else
        {
            c[b[i].id]=cxk(k-1,i-1)*ksm(cxk(k,n),md-2)%md;
        }

    }
    vector<int>f;
    for(int i=1;i<=n;i++)
    f.push_back(c[i]);
    return f;

}
};