A题 牛牛浇树

使用差分即可。

因为不带操作过程中的查询，而只需要最后的序列，直接用差分即可，记住最后的序列都要加上m，然后局部变量一定要清零。

比赛AC代码:

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

     */int c[1000005],a[1000005];
    int oddnumber(int n, int m, vector<int>& l, vector<int>& r) {
        for(int i = 0 ; i < m ; i ++)
            c[l[i]] ++ , c[r[i] + 1] --;
        for(int i = 1 ; i <= n ; i ++)
            a[i] = a[i - 1] + c[i];
        int Ans = 0;
        for(int i = 1 ; i <= n ; i ++)
            if((a[i] + m) % 2 == 1) Ans ++;
        return Ans;
    }
};

B题 挑选方案问题

不难发现这是一个生成函数裸题。

跟提高组IOI周赛20还是21完全是一模一样的套路。

但是其实如果你追求更快的解题，实际上我们不难发现这是一个规律题：

输入1，输出3。
输入2，输出6。
输入3，输出10
输入4，输出15
输入5，输出21

大胆猜测，得到答案表达式为

记得要强制把 转化为 long long!太坑了。

比赛AC代码:

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

C题 大逃离

简单组合数 + 细节屑题。

不难发现，实际上我们可以把问题转化为：

求一个序列中，对于 来说有多少个长度为 的包含 的子序列的最大值为

不难发现做法其实就是把给定的 排序,然后假设从小到大排序后这个数的排名为 ，那么满足条件的长度为 的包含 的子序列的个数就是 , 然后除以总的方案数 就是这个数 的“概率”（意义如题目描述）。

对于求 显然不能在线求，于是预处理出阶乘数组然后O(1) 即可求出

还要注意如果比这个数小的数不足 个，那么这个点的概率就是

对于为什么求 也就是说，你必定要选当前这个数 ， 同时你要在比 小的数中 （也就是 ） 个数里面选择 个数，所以满足条件的长度为 的包含 的子序列的个数就是 .

模意义下的除法需要求乘法逆元。

于是这题就做完了。

比赛AC代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param k int整型 
     * @param Point int整型vector 
     * @return int整型vector
     */
    long long Mod = 1000000007;
    long long T[300005];
    struct Y {
        long long data,id,d;
    } a[500000];
    long long quickpow(long long x,long long y)
    {
        long long ans = 1 , op = x;
        while(y)
        {
            if(y & 1) ans *= op,ans %= Mod;
            op *= op , op %= Mod;
            y >>= 1;
        }
        return ans;
    }
    map <long long,int > mp;

    static bool cmp(Y A,Y B)
    {
        return A.data < B.data;
    }

    int C(long long n,long long k)
    {
        long long A = T[n],Q1 = T[n - k] ,Q2 = T[k];
        return  (A * quickpow((Q1 * Q2)% Mod,Mod - 2)) % Mod ;
    }
    int Ans[200005];
    vector <int> ans;
    vector<int> city(int n, int k, vector<int>& Point) {

        long long All = C(n,k);
        T[0] = 1ll;
        for(int i = 1 ; i <= 2e5 ; i ++) T[i] = T[i - 1] * i , T[i] %= Mod;
        for(int i = 0 ; i < n ; i ++) a[i + 1].data = Point[i],a[i + 1].id = i;
        sort(a + 1 , a + 1 + n , cmp);
        for(int i = 1 ; i <= n ; i ++)
        {
            if(i < k)
            Ans[a[i].id] = 0;
            else Ans[a[i].id] = (C(i - 1,k - 1) * quickpow(C(n,k),Mod - 2)) % Mod;
        }
        for(int i = 1 ; i <= n ; i ++)
            ans.push_back(Ans[i - 1]);
        return ans;
    }
};