牛客多校第二场

把一些没时间写的和没时间想的还有不会做的补一下...

G

题意

给定$n$个区间，将这些区间分为$k$组，要求每组之间有交，使得每一组区间的交的和最大

题解

对于一个确定的区间组而言，我们往其中添加一个区间，答案显然是不增的

特别的，如果这个区间组中存在着被其完全包含的区间，那么我们就可以无视这个区间

因此，对于包含其余区间的区间而言，要么我们选择无视它，要么选择将其单独归为一组

我们考虑去除这些区间后，剩下的区间，它们互相之间没有包含关系，也就是说，它们的右端点随左端点递增而递增

此时，将左端点相邻的区间分在一组是较为优秀的

设$f_{i,j}$表示对于前$i$个区间，分出了$j$组的方案数，转移考虑最后一段区间即可，注意到合法的转移点是一段左端点不降的区间，可以用单调队列优化

#include <bits/stdc++.h>
using namespace std;

#define rep(io, st, ed) for(int io = st; io <= ed; io ++)

const int sid = 5e3 + 5;

int n, K;
struct segment {
    int l, r;
    segment() {}
    segment(int l_, int r_) : l(l_), r(r_) {}
    friend bool operator < (segment a, segment b) { 
        if(a.l != b.l) return a.l < b.l;
        return a.r < b.r;
    }
} p[sid], t[sid];

int tn, vn;
int f[sid][sid], v[sid], q[sid];

int main() {
    cin >> n >> K;
    for(int i = 1; i <= n; i ++) cin >> p[i].l >> p[i].r;
    p[n + 1].l = -1; 
    sort(p + 1, p + n + 1);
    
    for(int i = 1, j = i; i <= n; i = j) {
        while(p[j].l == p[i].l) j ++;
        p[++ tn] = p[i];
        for(int k = i + 1; k < j; k ++) v[++ vn] = p[k].r - p[k].l;
    }
    int tmp = 0;
    for(int i = 1; i <= tn; i ++) {
        bool flag = 0;
        for(int j = 1; j <= tn; j ++) 
            if(i != j && p[i].l <= p[j].l && p[j].r <= p[i].r)
                flag = 1;
        if(!flag) t[++ tmp] = p[i];
        else v[++ vn] = p[i].r - p[i].l;
    }
    tn = tmp;
    sort(v + 1, v + vn + 1);
        
    rep(i, 0, n) rep(k, 0, K) f[i][k] = (i || k) ? -1e9 : 0;

    for(int k = 1; k <= K; k ++) {
        int fr = 1, to = 0;
        q[++ to] = 0;
        for(int i = 1; i <= tn; i ++) {
            while(fr <= to && t[q[fr] + 1].r <= t[i].l) fr ++;
            #define pre q[fr]
            if(fr <= to) f[i][k] = f[pre][k - 1] + t[pre + 1].r - t[i].l;
            while(fr <= to && f[i][k - 1] + t[i + 1].r >= f[q[to]][k - 1] + t[q[to] + 1].r) to --;
            q[++ to] = i;
        }
    }
    
    int ans = 0, suf = 0;
    for(int k = K, lst = vn; k >= 0 && (~lst); k --, lst --) {
        if(f[tn][k]) ans = max(ans, f[tn][k] + suf);
        suf += v[lst];
    }
    printf("%d\n", ans);
    return 0;
}

J

题解

sb卡常出题人

L

题意

给定$n$个点，$m$条边，每次操作为增加一个点的点权

对于每个点，询问有多少次操作后，这个点的点权比其所有相邻点多大

题解

分块，设$B=\sqrt{m}$，称$\le B$的点为小点，而$>B$的点为大点

对于小点而言，其邻点只有$B$个，随意暴力

对于大点而言，其大点的邻居可以不用考虑

取大点为研究对象，考虑其小点邻居，我们直接分权值，存下其邻居中的小点冠军，当权值增加时，我们把相应的小点冠军给取消

这个题中可以利用权值比较小的条件，权值较大时离散化一下即可...

A

题意

给定序列$a_i$，求满足排序后是等差数列的子区间的数量

$1\le n\le {10}^5$

题解

这里有一个引理？

• 对于序列$b_i$，如果排序后为等差数列，那么公差$d=gcd(b_2-b_1,...,b_n-b_{n-1})$

要证明这个引理，我们只需要考虑证明交换相邻两个数的位置不改变这个式子的值

Case1：我们交换了$1,2$，那么只需证明$gcd(b_2-b_1,b_3-b_2)=gcd(b_2-b_1,b_3-b_1)$，由$gcd(x,y)=gcd(x,x+y)$，这个是正确的，交换$n,(n-1)$时同理

Case2：不妨假设我们交换了$i,i+1(i\ne 1,i+1\ne n)$，那么我们只要证明$gcd(b_{i+2}-b_{i+1},b_{i+1}-b_i,b_i-b_{i-1})=gcd(b_{i+2}-b_i,b_i-b_{i+1},b_{i+1}-b_{i-1})$，这一点则由$gcd(x,y,z)=gcd(x+y,y,z+y)$得出

我们只需要计数满足$max-min=d\ast (r-l)$的区间个数即可

对$r$进行扫描线，$max$和$min$的变化都只有$O(n)$段，而每个$l$而言，$gcd(b_{l+1}-b_l,...,b_r-b_{r-1})$至多改变$\log$次，因此可以每次对$l$进行逐个单点修改

注意到排序后满足$gcd$为$d$的$max-min$极小的序列就是等差数列，因此我们有$max-min\ge d\ast (r-l)$，即$max-min+d\ast l\ge d\ast r$，而$gcd$对同一个$r$至多$log$段，对于每一段维护最小值及个数即可

E

题意

给定一棵树，经过边$e$将花费$w_e$升油，而到达$i$号点将得到$x_i$升油

$q$次询问，每次询问给定$x,d,p$，表示从$x$号点，初始有$d$升油，不能经过$p$号的情况下，有多少点是可达的

吐槽

虽然思路很平凡，但是没人翻译，估计也没啥人愿意写...

题解

点分治，之后我们可以强制$x$走到根节点，往下走到其他点

对于每个点预处理出根节点走到它最少需要多少油，计算贡献时，去除$p$及自己所在的子树，在$dfn$序上将对应连续的三段，差分之后，扫描线维护树状数组即可

B

题意

给定一个$2$行的棋盘，第一行有$a$个炮，第二行有$b$个炮，对$k=0,1,...,a+b-4$求发生$k$个炮吃炮事件的方案数

特别的，你还需要输出第一行吃炮事件完全优先于第二行吃炮事件发生的方案数

吐槽

感觉也就这样...

题解

显而易见，一个含有$x$枚棋子的行吃炮的方案数为$2(x-2)$，一个含有$x$枚棋子的行吃$m$个炮的方案数为$2^m(x-2)(x-3)(x-m+1)=2^m(x-2{)}_m$

一般的，输出$2_{i+j=k}^k(a-2{)}_i(b-2{)}_j$；

对于特别的情况，输出$2^k\sum _{i+j=k}(a-2{)}_i(b-2{)}_j$

而$2^k\sum _{i+j=k}(a-2{)}_i(b-2{)}_j{C}_k^i=2^{k}k!\sum _{i+j=k}{C}_i^{a-2}{C}_j^{b-2}=2^{k}k!C_k^{a+b-4}$

且$2^k\sum _{i+j=k}(a-2{)}_i(b-2{)}_j=2^k\frac{(a-2)!(b-2)!}{(a+b-4-k)!}\sum _{i+j=k}{C}_{a-2-i}^{a+b-4-k}$

后面是一个组合数列和，可以求