2019ICPC上海区域赛 补题（12/13）& 总结

前言：

个人的 $ICPC$ 第一站，还是值得记录一下的（虽然咕到现在才记录），总体而言体验很不错，比赛兼旅游。这套题总体印象就是树树树图，作为队里数据结构兼图论选手，这次也确实写了大部分题目（明示下次几乎爆零），但也因为我属于慢热型，题目都是中后期连着开，前期猛跪，罚时炸裂。

现场赛最先看了 $D$ 题，想了十来分钟没思路，跟 $zzy$ 换了 $K$ 题，然后 $xbx$ 喂了 $B$ 题，很快跟榜过了。然后就是卡了半小时 $K$ 题才出思路，交了喜提 $TLE$，卡到大概 $2h$ 的时候才过（$vector$ 存图被卡了，邻接矩阵比较快），此时从铁牌区上升到铜牌区。然后 $zzy$ 成功过掉 $D$，接着与 $xbx$ 证明了下 $H$ 也成功上机 $1A$，这时候大约 $3.5h$，此时应该是银末。不久 $zzy$ 与 $xbx$ 讨论完 $E$ 题，上机敲，封榜后不久成功过了（然而应该是险过，没有用基数排序，小常过了），这时候已经稳在银牌区，看了下再过一题有机会进金末。最后就全力开 $F$ 题，队友帮忙验了下式子、看取模，剩 $20mins$ 的 $2$ 发过了，按封榜前的榜估摸着直接上升到 $rk20$ 左右，然后就是快乐吃饭时间。

前 $2h$ 仅过两道签到，后面一路从铁牌区上去也是挺刺激的。滚榜看着被滚出金牌区，虽然遗憾但最后 $rk37$ 也挺满意了，本来小目标便是拿个银。最后很意外拿到 $EC$ 名额，也是后面才知道的，那就是我个人爆零的另一段故事了（什么时候会记录呢？

这次借着计算思维课程，把这场补题计划作为课程作业，也一举两得。队友 $xbx$ 一起选修了这门课，队长 $zzy$ 擅长数学、数论（但没选上这门课），$C$ 题组合数学我俩实在推不来，就留着吧。

重现赛链接：https://ac.nowcoder.com/acm/contest/4370

两人完成的，所以码风会不同，以下为参考题解（长文预警）：
 

A - Mr. Panda and Dominoes

问题简述：

平面上有 $n$ 个黑格子，求有多少个外围是黑色格子的 $1:2$ 或 $2:1$ 的 矩形。

所需知识点：

离散化，树状数组。

问题形式化描述：

二维平面 $[1, 10^9] × [1, 10^9]$ 上给定 $n$ 个黑点，求有多少矩形 $(x, y),(x + L - 1, y + W - 1)$（两点表示），满足 $L:W = 1:2$ 或 $L:W = 2:1$ 且矩形四条边上全为黑点。

解题思路：

将 $xy$ 坐标旋转一下就可以把 $2:1$ 的情况转为 $1:2$ 的情况，接下来仅考虑 $1:2$ 的情况。

由于外围黑格子需要连续，先离散化，预处理出每个黑格子向四个方向最长延伸距离是多少。考虑枚举每一条斜率为 $2$ 的直线，在该直线上枚举矩形的右上角，统计有多少个黑格子可作为该矩形的左下角，满足条件是这个点的最上延长能够到达枚举的右上角。

问题就转化为一个数轴上（就是枚举的直线上），有若干个原有区间（矩形左下角的点），需要查询区间 $[ l ,r ]$ 中有多少个原有区间满足左端点在 $[ l, r ]$ 内， 右端点在 $r$ 右面。 我们可以把询问区间拆成两个询问区间 $[ 1, r ]$ 和 $[ 1, l -1]$ 的差，扫描线加树状数组维护即可。

总时间复杂度为 $O(T * nlogn)$，需要注意常数优化。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+9;
const ll base = 2e9;
struct Point{
    int x,y;
    bool ri;
}p[N];
struct Option{
    int l , r;
    int ty;
    bool operator < (const Option& b)const{
        return l == b.l ? ty < b.ty : l < b.l;
    }
};
bool test;
int n;
int tr[2*N];
int X[2*N];
vector<Point> vec[2*N];
vector< Option > opt;
vector<int> use;
struct HashTable{
    const static int md = 2000003;
    struct Edge{
        ll key; int val, nxt;
    } edge[2*N];
    int head[md], rub[2*N], cnt, top;
    void init(){
 
        while(top) head[rub[top--]] = 0;
        cnt = 0;
    }
    void add(ll key, int val){
 
        int u = abs(key % md);
        edge[++cnt] = {key, val, head[u]}; head[u] = cnt;
        rub[++top] = u;
    }
    int fin(ll key){
 
        int u = abs(key % md);
        for(int i = head[u]; i; i = edge[i].nxt){
 
            if(edge[i].key == key) return edge[i].val;
        }
        return 0;
    }
    void ins(ll key, int val){
 
        if(!fin(key)) add(key, val);
    }
} le,ri,up,dw,mp;
bool cmpx(Point &a,Point &b){
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmpy(Point &a,Point &b){
    return a.y == b.y ? a.x < b.x : a.y < b.y;
}
//树状数组
void add(int x,int v,int mx){
    for(int i = x;i;i-=i&-i) tr[i] += v;
}
void clear(int x,int mx){
    for(int i = x;i<=mx;i+=i&-i) tr[i] = 0;
}
int query(int x,int mx){
    int res =0 ;
    for(int i = x;i<=mx;i += i&-i) res += tr[i];
    return res;
}
//处理每个黑格点向四个方向的最长延长多少
void init(){
    le.init() ; ri.init();
    up.init() ; dw.init();
    mp.init();
    sort(p+1,p+1+n,cmpx);
    for(int i = 1;i<=n;++i){
        if( int tmp = le.fin((p[i].x-1) * base + p[i].y) ) le.ins(p[i].x*base+p[i].y, tmp + 1);
        else le.ins(p[i].x * base + p[i].y, 1);
    }
    for(int i = n;i>=1;--i){
        if( int tmp = ri.fin((p[i].x+1)*base+p[i].y) ) ri.ins(p[i].x*base+p[i].y, tmp + 1);
        else ri.ins(p[i].x*base+p[i].y, 1);
    }
    sort(p+1,p+1+n,cmpy);
    for(int i = 1;i<=n;++i){
        if( int tmp = dw.fin(p[i].x*base+p[i].y-1) ) dw.ins(p[i].x*base+p[i].y, tmp + 1);
        else dw.ins(p[i].x*base+p[i].y, 1);
    }
    for(int i = n;i>=1;--i){
        if( int tmp = up.fin(p[i].x*base+p[i].y+1) ) up.ins(p[i].x*base+p[i].y, tmp + 1);
        else up.ins(p[i].x*base+p[i].y, 1);
    }
}
//计算每一条直线的答案
ll work(vector<Point> &vec){
    opt.clear();
    int cnt = 0;
    for(auto it : vec){
        ll x = it.x , y = it.y;
        //假如该点是某个格点的右上角
        if( it.ri ){
            int nle = le.fin(x*base+y); int ndw = dw.fin(x*base+y);
            Option tem;
            int len = min(nle,ndw/2);
            tem.l = x - len -1 ; tem.r = x ; tem.ty = -1;
            opt.push_back(tem);
  
            tem.l = x - 1; tem.r = x; tem.ty = 1;
            opt.push_back(tem);
        } 
        else{
            int nri = ri.fin((x+1)*base+y+1); int nup = up.fin((x+1)*base+y+1);
            int len = min(nri,nup/2);
            Option tem;
            tem.l = x; tem.r = x + len; tem.ty = -2;
            opt.push_back(tem);
        } // 左下角
          
  
    }
    for(auto& it : opt){
        X[++cnt] = it.l; X[++cnt] = it.r;
    }
    sort(X+1,X+1+cnt);
    cnt = unique(X+1,X+1+cnt) - X - 1;
    for(auto& it : opt){
        it.l = lower_bound(X+1,X+1+cnt,it.l) - X;
        it.r = lower_bound(X+1,X+1+cnt,it.r) - X;
    }
    ll res = 0;
    use.clear();
    sort(opt.begin(),opt.end());
    for(auto it : opt){
        int l = it.l , r = it.r , ty = it.ty;
        if( ty == -2){
            add(it.r,1,cnt);
            use.push_back(it.r);
        }
        else{
            int tem = query(it.r,cnt);
            res += ty*tem;
        }
    }
    for(auto it : use){
        clear(it,cnt);
    }
    return res;
}
ll solve(){
    ll res = 0; int tot = 0;
    init();
    for(int i = 1;i<=n;++i){
        Point tem = p[i];
        tem.ri = 1;
        ll val = tem.y - 2ll * tem.x;
        if(!mp.fin(val)) mp.ins(val, ++tot);
        vec[mp.fin(val)].push_back(tem);
        --tem.x; --tem.y;
        tem.ri = 0;
        val = tem.y - 2ll * tem.x;
        if(!mp.fin(val)) mp.ins(val, ++tot);
        vec[mp.fin(val)].push_back(tem);
    }
    for(int i = 1; i <= tot; ++i) res += work(vec[i]), vec[i].clear();
    return res;
}
const int maxs = 1e6 + 5;
char buf[maxs], *p1 = buf, *p2 = buf;
inline char fr(){
 
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, maxs, stdin)) == p1 ? -1 : *p1++;
}
#define gc fr()
inline void read(int &x){
 
    char ch; while(!isdigit(ch = gc)); x = ch ^ 48;
    while(isdigit(ch = gc)) x = x * 10 + (ch ^ 48);
}
int main(){
    int T; read(T);
    for(int cas = 1;cas <= T; ++cas){
        read(n);
        ll ans = 0; int x, y;
        for(int i = 1;i<=n;++i){
            read(p[i].x), read(p[i].y);
        }
        ans += solve();
        //旋转xy坐标来统计2:1的情况
        for(int i = 1;i<=n;++i){
            int tx = p[i].x,ty = p[i].y;
            p[i].x = -ty;
            p[i].y = tx;
        }
        ans += solve();
        printf("Case #%d: %lld\n",cas,ans);
    }
    return 0;
}

B - Prefix Code

问题简述：

给定 $n$ 个长度最多为 $10$ 的数字字符串，问是否存在某个字符串是另一个字符串的前缀。

所需知识点：

字典树。

问题形式化描述：

给定 $n$ 个字符串 $s_i(|s_i| \leq 10, \Sigma = \{0, 1, \cdots, 9\})$，求是否存在 $i, j(i \neq j)$，使得 $s_i \in prefix(s_j)$。

解题思路：

先对给定的 $n$ 个字符串建立字典树，并且对每个字符串的末尾节点的值加 $1$，即每一个节点维护有多少个字符串以当前节点为结尾。

对每一个字符串 $s_i$，在字典树上遍历，假如当前字符串遍历的节点（除了末节点）当中存在值不是 $0$ 的节点，则 $\exists j \neq i,~s_j \in prefix(s_i)$；或者末尾节点的值大于 $1$， 则 $\exists j \neq i, s_i \in prefix(s_j)$。

总时间复杂度为 $O(T*10n)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+9;
string a[N];
struct Node{
    int v;
    int son[11];
}tr[N*10];
int tot;
void ins(string s){
    int n = s.size();
    int now = 1;
    for(int i = 0;i<n;++i){
        int w = s[i] - '0';
        if(tr[now].son[w] == 0) tr[now].son[w] = ++tot;
        now = tr[now].son[w];
    }
    tr[now].v++;
}
bool que(string s){
    int n = s.size();
    int now = 1;
    for(int i = 0;i<n-1;++i){
        int w = s[i] - '0';
        now = tr[now].son[w];
        if(tr[now].v) return 0;
    }
    now = tr[now].son[s[n-1]-'0'];
    if(tr[now].v>1) return 0;
    return 1;
}
int main(){
    int T; cin>>T;
    for(int cas = 1;cas<=T;++cas){
        tot = 1;
        int n; cin>>n;
        for(int i = 1;i<=n;++i) cin>>a[i];
        for(int i = 1;i<=n;++i) ins(a[i]);
        bool ok = 1;
        for(int i = 1;i<=n && ok;++i){
            if(!que(a[i])) ok = 0;
        }
        cout<<"Case #"<<cas<<": "<<(ok?"Yes":"No")<<endl;
        for(int i = 1;i<=tot;++i){
            for(int j = 0;j<=9;++j) tr[i].son[j] = 0;
            tr[i].v = 0;
        }
    }
    return 0;
}

C - Maze

D - Spanning Tree Removal

问题简述：

给定 $n$ 个顶点的完全图 $G$，每次选择任意生成树，将生成树边删去，问最多能删几次生成树。

所需知识点：

生成树、构造。

问题形式化描述：

给定完全图 $G = (V, E)$，求最大的 $k$，使得 $\forall i, 1 \leq i \leq k, G_i = (V, E_i)$ 为 $G$ 的生成树，且 $\forall i, j, 1 \leq i \lt j \leq k, G_i \bigcap G_j = (V, \emptyset)$。

解题思路：

由度数易得 $ans(n)$ 的一个上界为 $\lfloor \cfrac{n}{2}\rfloor$，猜想 $ans(n) = \lfloor \cfrac{n}{2}\rfloor$。
使用数学归纳法证明当 $n = 2k(k \geq 1)$，$ans(n) = \cfrac{n}{2}~$ 。

当 $n = 2$，显然 $ans(2) = 1$，$G_1 = (\{1, 2\},\{(1, 2)\})$。

假设对 $n = 2k(k \geq 1)$，$ans(n) = k$，当 $n = 2(k + 1)$，新增边集 $\Delta E = \{(u, v) \mid 2k + 1 \leq u \leq 2k + 2, 1 \leq v \lt u\}$。

对 $G_i(i \leq k)$，都需要额外添加两条边 $(2k + 1, v_i), (2k + 2, v_j)$，对于新增的 $G_{k + 1}$，需要添加 $n - 1$ 条，令 $E_{k + 1} = \{(2k + 1, v) \mid 1 \leq v \leq k\} \bigcup \{(2k + 2, v) \mid k + 1 \leq v \leq 2k + 1 \}$ ，剩余的 $\{(2k + 1, v) \mid k + 1 \leq v \leq 2k\} \bigcup \{(2k + 2, v) \mid 1 \leq v \leq k \}$ 恰能分成 $k$ 组 $(2k + 1, v_i), (2k + 2, v_j)$ 分配到 $G_i(1 \leq i \leq k)$，故 $ans(n) = \cfrac{n}{2}$ 成立。

综上，当 $n = 2k(k \geq 1), ans(n) = \cfrac{n}{2}$ 。
当 $n = 2k + 1(k \geq 1)$，只需对 $G_i$ 添加边 $(n, i)$ 即可，$ans(n) = \lfloor \cfrac{n}{2}\rfloor$。
综上，得到一种方案使得 $ans(n) = \lfloor \cfrac{n}{2}\rfloor$，且为上确界。

时间复杂度 $O(T * n^2)$。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
const int maxn = 1e3 + 5;

vector<pii> ans[maxn];
int n;

int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){

        cin >> n;
        int ret = n / 2;
        for(int i = 1; i <= ret; ++i){

            ans[i].clear();
        }
        for(int i = 2; i <= n; i += 2){

            for(int j = 1; j <= i / 2 - 1; ++j){

                ans[j].pb({i, j});
                ans[j].pb({i - 1, j + i / 2 - 1});
                ans[i / 2].pb({i - 1, j});
            }
            for(int j = i / 2; j < i; ++j){

                ans[i / 2].pb({i, j});
            }
        }
        if(n & 1){

            for(int i = 1; i <= ret; ++i){

                ans[i].pb({n, i});
            }
        }
        cout << "Case #" << ++cas << ": " << ret << "\n";
        for(int i = 1; i <= ret; ++i){

            for(auto &e : ans[i]) cout << e.first << " " << e.second << "\n";
        }
    }
    return 0;
}

E - Cave Escape

问题简述：

给定 $n × m$ 的方格图，每个格子都有魔法值，第 $i$ 行第 $j$ 列的值为 $V_{ij} = X_{(i-1) * m + j}$，其中 $X_i​=(A*X_{i−1}​+B*X_{i−2}​+C)~mod~P$。从 $(i, j)$ 能移动到相邻格子 $(x, y)$，且当 $(x, y)$ 此前未访问则获得 $V_{i,j}*V_{x,y}$ 的魔法值。给定起点和终点，问从起点走到终点可获得的最大魔法值，格子可重复经过。

所需知识点：

并查集，最小生成树 $Kruskal$ 算法。

问题形式化描述：

给定图 $G=(V, E)$，$V = \{a_{i,j} \mid 1 \leq i \leq n, 1 \leq j \leq m\}$，$E = \{(a_{i,j}, a_{x,y}, V_{i,j}*V_{x,y}) \mid |i - x| + |j - y| = 1\}$，求从顶点 $a_{s_x,s_y}$ 沿边走到 $a_{t_x, t_y}$ 可获得的最大价值，沿边 $(a_{i,j}, a_{x,y}, w)$ 走时，当且仅当 $a_{x,y}$ 第一次被访问时获得价值 $w$。

解题思路：

每个顶点仅当被作为边终点经过时，获得该边价值，至多可获得 $nm - 1$ 次，即寻找图 $G$ 的最大生成树。

对所有边按照边权从大到小排序，从大到小枚举每一条边。假如当前边关联的两个顶点不在同一个集合，就把这条边的边权加进答案，并合并两顶点所在集合。

由于 $P \leq 100$，$V_{i,j} \lt 10000$，可以使用基数排序将排序复杂度降为 $O(nm)$。

使用 $std::sort$，总时间复杂度为 $O(T*nmlog(nm))$，也可通过本题。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+9;
ll X[N];
struct Edge{
    int u,v;
    ll w;
    bool operator < (const Edge& b)const{
        return w > b.w;
    }
}e[N*2];
int f[N];
int find(int x){
    if(x==f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    int T; scanf("%d",&T);
    for(int cas = 1;cas<=T;++cas){
        int n,m,sr,sc,tr,tc; scanf("%d %d %d %d %d %d",&n,&m,&sr,&sc,&tr,&tc);
        ll A,B,C,P;
        scanf("%lld %lld %lld %lld %lld %lld",&X[1],&X[2],&A,&B,&C,&P);
        f[1] = 1; f[2] = 2;
        for(int i = 3;i<=n*m;++i){
            X[i] = ( A * X[i-1] + B * X[i-2] + C) % P;
            f[i] = i;
        }
        int cnt = 0;
        for(int i=  1;i<=n;++i){
            for(int j = 1;j<m;++j){
                int s = (i-1)*m + j;
                int t = (i-1)*m+j+1;
                e[++cnt] = (Edge){ s,t,X[s]*X[t]};
            }
        }
        for(int j=  1;j<=m;++j){
            for(int i = 1;i<n;++i){
                int s = (i-1)*m + j;
                int t = i*m + j;
                e[++cnt] = (Edge){ s,t,X[s]*X[t]};
            }
        }
        sort(e+1,e+1+cnt);
        int now = n*m;
        ll ans = 0;
        for(int i = 1;i<=cnt && now > 1;++i){
            int fu = find(e[i].u),fv = find(e[i].v);
            if(fu==fv) continue;
            ans += e[i].w;
            f[fu] = fv;
            --now;
        }
        printf("Case #%d: %lld\n",cas,ans);
    }
    return 0;
}

F - A Simple Problem On A Tree

问题简述：

给定 $n$ 个结点的树，结点带点权 $W_i$，$q$ 次操作，每次对 $u, v$ 之间的链上结点进行，分别为点权赋值 $W$、点权增加 $W$，点权乘上 $W$、询问 $\sum_xW_x^3$。

所需知识点：

线段树、重链剖分。

问题形式化描述：

使用数据结构动态维护树链结点权值三次方和，支持赋值、加、乘操作。

解题思路：

重链剖分将树链操作转化为 $O(logn)$ 次序列操作，用线段树维护序列三次方和，赋值 $W$ 操作可视为乘 $0$ 再加 $W$，故只需要乘法标记 $mul$ 和加法标记 $add$，线段树结点还需要分别维护一次方和 $sum_1$、二次方和 $sum_2$ 以及三次方和 $sum_3$，每次修改操作 $(M, A)$ 表示乘 $M$ 再加 $A$，

对于标记维护，有：
$mul' * x + add' = (mul * x + add) * M + A = mul * M + add * M + A \\ ~ \\ mul' = mul * M, ~add' = add * M + A$
对于和维护，记 $len = r - l + 1$，先乘：
$sum_1 = \sum\limits_{i = l}^{r} x_i,~sum_2 = \sum\limits_{i = l}^{r} x_i^2,~sum_3 = \sum\limits_{i = l}^{r} x_i^3 \\ ~ \\ x_i' = x_i * M \\ ~ \\ sum_1' = \sum\limits_{i = l}^{r} x_i' = \sum\limits_{i = l}^{r} (x_i * M) = M * \sum\limits_{i = l}^{r} x_i = M * sum_1 \\ ~ \\ sum_2' = M^2 * sum_2, ~ sum_3' = M^3 * sum_3$
后加：
$x_i' = x_i + A \\ ~ \\ sum_1' = \sum\limits_{i = l}^{r} x_i' = \sum\limits_{i = l}^{r} (x_i + A) = \sum\limits_{i = l}^{r} x_i + len * A = sum_1 + len * A \\ sum_2' = \sum\limits_{i = l}^{r} (x_i + A)^2 = sum_2 + 2 * A * sum_1 + len * A^2 \\ sum_3' = sum_3 + 3 * A * sum_2 + 3 * A^2 * sum_1 + len * A^3$
时间复杂度 $O(T * (n + qlognlogn))$。

参考代码：

#include<bits/stdc++.h>
  
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(a) ((int)a.size())
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
 
vector<int> G[maxn];
int siz[maxn], son[maxn], dep[maxn];
int fa[maxn], top[maxn], dfn[maxn], rk[maxn];
int a[maxn];
int n, q, tim;
 
struct SegTree{
 
    ll sum1[maxn << 2], sum2[maxn << 2], sum3[maxn << 2];
    ll add[maxn << 2], mul[maxn << 2];
    void pushUp(int rt){
 
        sum1[rt] = (sum1[lson] + sum1[rson]) % mod;
        sum2[rt] = (sum2[lson] + sum2[rson]) % mod;
        sum3[rt] = (sum3[lson] + sum3[rson]) % mod;
    }
    void build(int l, int r, int rt){
 
        add[rt] = 0, mul[rt] = 1;
        if(l == r){
 
            ll tmp = a[rk[l]];
            sum1[rt] = tmp % mod;
            sum2[rt] = sum1[rt] * tmp % mod;
            sum3[rt] = sum2[rt] * tmp % mod;
            return;
        }
        int mid = gmid;
        build(l, mid, lson);
        build(mid + 1, r, rson);
        pushUp(rt);
    }
    void pushDown2(int rt, int son, int len){
 
        ll M = mul[rt], A = add[rt];
        mul[son] = mul[son] * M % mod;
        add[son] = add[son] * M % mod;
        add[son] = (add[son] + A) % mod;
 
        sum3[son] = sum3[son] * M % mod * M % mod * M % mod;
        sum2[son] = sum2[son] * M % mod * M % mod;
        sum1[son] = sum1[son] * M % mod;
 
        sum3[son] = (sum3[son] + 3 * A % mod * sum2[son] % mod 
        			+ 3 * A % mod * A % mod * sum1[son] % mod
        			+ len * A % mod * A % mod * A % mod) % mod;
        			
        sum2[son] = (sum2[son] + 2 * A % mod * sum1[son] % mod 
        			+ len * A % mod * A % mod) % mod;
        			
        sum1[son] = (sum1[son] + len * A % mod) % mod;
    }
    void pushDown(int l, int r, int rt){
 
        int mid = gmid;
        pushDown2(rt, lson, mid - l + 1);
        pushDown2(rt, rson, r - mid);
        mul[rt] = 1, add[rt] = 0;
    }
    void update(int l, int r, int rt, int L, int R, ll M, ll A){
 
        if(l >= L && r <= R){
 
            mul[0] = M, add[0] = A;
            pushDown2(0, rt, r - l + 1);
            return;
        }
        int mid = gmid;
        pushDown(l, r, rt);
        if(L <= mid) update(l, mid, lson, L, R, M, A);
        if(R > mid) update(mid + 1, r, rson, L, R, M, A);
        pushUp(rt);
    }
    ll query(int l, int r, int rt, int L, int R){
 
        if(l >= L && r <= R) return sum3[rt];
        int mid = gmid; ll ret = 0;
        pushDown(l, r, rt);
        if(L <= mid) ret += query(l, mid, lson, L, R);
        if(R > mid) ret += query(mid + 1, r, rson, L, R);
        return ret % mod;
    }
} tr;
 
void dfs1(int u, int f){
 
    dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1, son[u] = 0;
    for(auto &v : G[u]){
 
        if(v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        son[u] = siz[v] > siz[son[u]] ? v : son[u];
    }
}
 
void dfs2(int u, int t){
 
    top[u] = t, dfn[u] = ++tim, rk[tim] = u;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(auto &v : G[u]){
 
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
 
void update(int u, int v, ll M, ll A){
 
    while(top[u] != top[v]){
 
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        tr.update(1, n, 1, dfn[top[u]], dfn[u], M, A);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    tr.update(1, n, 1, dfn[v], dfn[u], M, A);
}
 
ll query(int u, int v){
 
    ll ret = 0;
    while(top[u] != top[v]){
 
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ret += tr.query(1, n, 1, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    ret += tr.query(1, n, 1, dfn[v], dfn[u]);
    return ret % mod;
}
 
int main(){
  
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){
 
        cin >> n;
        tim = 0;
        for(int i = 1; i <= n; ++i){
 
            G[i].clear();
        }
        for(int i = 1; i < n; ++i){
 
            int u, v; cin >> u >> v;
            G[u].pb(v), G[v].pb(u);
        }
        for(int i = 1; i <= n; ++i){
 
            cin >> a[i];
        }
        dfs1(1, 0);
        dfs2(1, 1);
        tr.build(1, n, 1);
        cout << "Case #" << ++cas << ":\n";
        cin >> q;
        while(q--){
 
            int opt, u, v, w; cin >> opt >> u >> v;
            if(opt == 1){
 
                cin >> w;
                update(u, v, 0, w);
            }
            else if(opt == 2){
 
                cin >> w;
                update(u, v, 1, w);
            }
            else if(opt == 3){
 
                cin >> w;
                update(u, v, w, 0);
            }
            else{
 
                ll ret = query(u, v);
                cout << ret << "\n";
            }
        }
    }
    return 0;
}

G - Play the game SET

问题简述：

一种 $SET$ 卡牌游戏，每张卡牌 $4$ 种属性，每种属性有 $3$ 种可能情况，三种卡牌组成一个 $set$ 当且仅当同种属性都相同、或都不同。给出 $n$ 张卡牌，求能组成最多的 $set$ 数。

所需知识点：

最大独立集、最大团 $Bron-Kerbosch$ 算法。

问题形式化描述：

给出 $n$ 个四位的三进制数 $a_{i3}a_{i2}a_{i1}a_{i0}$，定义 $A = \{a_i(1 \leq i \leq n)\}$，
$f(A) = \begin{cases} 1, & \mid A\mid = 3,~\sum\limits_{i = 0}^{3} (a_{0i} + a_{1i} + a_{2i}) = 0 \\ 0, & otherwise \end{cases}$
求一种划分 $A_1A_2...A_k$ 使得 $ans = \sum\limits_{i = 1}^{k} f(A_i)$ 最大。

解题思路：

对所有 $A_i \subseteq A$ 且 $f(A_i) = 1$ 建立顶点 $v_i$，连边 $(v_i, v_j)$ 当且仅当 $A_i \bigcap A_j \neq \emptyset$，则该图的最大独立集就是答案。由于是一般图且顶点数为 $C(n, 3)$ 上万个，无法在规定时限得到答案，需要进一步优化。

注意到若 $f(A_i) = 1$，只需两个元素 $a_0, a_1$ 即可唯一确定 $a_2$，于是只需要尝试 建立 $C(n, 2)$ 个顶点。一般图 $G$ 的最大独立集问题转为最大团问题，即建立补图 $G'$，答案为 $G'$ 的最大团，使用 $Bron-Kerbosch$ 算法求解。

虽然此算法理论复杂度为指数级，但在此特殊图中可以很快迭代得到答案。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
const int maxn = 2e3 + 5;
 
unordered_map<string, int> mp;
int G[maxn][maxn], num[maxn], tp[maxn], pi[maxn];
int a[maxn], id[maxn], b[maxn][3];
int n, tot, ans, lim;

// 由 a0, a1 可确定 a2
int cal(int x, int y){
 
    int z[4];
    for(int i = 0; i < 4; ++i){
 
        int tx = x % 3, ty = y % 3;
        z[3 - i] = tx == ty ? tx : 3 - tx - ty;
        x /= 3, y /= 3;
    }
    return z[0] * 27 + z[1] * 9 + z[2] * 3 + z[3];
}
 
int check(int x, int y){
 
    for(int i = 0; i < 3; ++i){
 
        for(int j = 0; j < 3; ++j) if(b[x][i] == b[y][j]) return 0;
    }
    return 1;
}
 
void build(){
 
    for(int i = 0; i < 81; ++i) id[i] = 0;
    for(int i = 1; i <= n; ++i) id[a[i]] = i;
    tot = 0;
    for(int i = 1; i <= n; ++i){
 
        for(int j = i + 1; j <= n; ++j){
 
            int k = id[cal(a[i], a[j])];
            if(k <= j) continue;
            b[++tot][0] = i;
            b[tot][1] = j, b[tot][2] = k;
        }
    }
    // 补图
    for(int i = 1; i <= tot; ++i){
 
        for(int j = i + 1; j <= tot; ++j) G[i][j] = G[j][i] = check(i, j);
    }
    lim = n / 3, n = tot;
}
 
int dfs(int *a, int n, int cnt){
 
    if(ans == lim) return 1;
    int ta[maxn], tn;
    if(!n){
 
        if(cnt > ans){
             
            ans = cnt;
            for(int i = 1; i <= ans; ++i) pi[i] = tp[i];
            return 1;
        }
        return 0;
    }
    for(int i = 1; i <= n; ++i){
 
        if(cnt + n - i + 1 <= ans || cnt + num[a[i]] <= ans) return 0;
        tn = 0;
        for(int j = i + 1; j <= n; ++j) if(G[a[i]][a[j]]) ta[++tn] = a[j];
        tp[cnt + 1] = a[i];
        if(dfs(ta, tn, cnt + 1)) return 1;
    }
    return 0;
}
 
int BK(){
 
    int ta[maxn], tn; ans = 0;
    for(int i = n; i >= 1; --i){
 
        tn = 0;
        for(int j = i + 1; j <= n; ++j) if(G[i][j]) ta[++tn] = j;
        tp[1] = i;
        dfs(ta, tn, 1);
        num[i] = ans;
    }
    return ans;
}
 
int main(){
  
    ios::sync_with_stdio(0); cin.tie(0);
    mp["one"] = 10, mp["two"] = 11, mp["three"] = 12;
    mp["diamond"] = 20, mp["squiggle"] = 21, mp["oval"] = 22;
    mp["solid"] = 30, mp["striped"] = 31, mp["open"] = 32;
    mp["red"] = 40, mp["green"] = 41, mp["purple"] = 42;
    int t, cas = 0; cin >> t;
    while(t--){
 
        cin >> n;
        string s; int tmp[4];
        for(int i = 1; i <= n; ++i){
 
            cin >> s;
            for(int j = 0; j < 4; ++j){
 
                int p = s.find(']');
                tmp[j] = mp[s.substr(1, p - 1)];
                if(p + 1 < sz(s)) s = s.substr(p + 1, sz(s) - p - 1);
            }
            sort(tmp, tmp + 4);
            a[i] = 0;
            for(int j = 0; j < 4; ++j) a[i] = a[i] * 3 + tmp[j] % 10;
        }
        build();
        int ret = BK();
        cout << "Case #" << ++cas << ": " << ret << "\n";
        for(int i = 1; i <= ret; ++i){
 
            cout << b[pi[i]][0] << " " << b[pi[i]][1] << " " << b[pi[i]][2] << "\n";
        }
    }
    return 0;
}

H - Tree Partition

问题简述：

给定 $n$ 个结点的树，结点带权，给定一个数 $k$，要求把这棵树分成 $k$ 个部分，使得每部分的结点权值和中的最大值最小，求该最小值。

所需知识点：

二分法，贪心，动态规划。

问题形式化描述：

给定 $n$ 个结点的树 $T = (V, E)$，结点 $v_i$ 带权 $w(v_i)$，将其划分为 $k$ 个连通块 $T_i = (V_i, E_i)(i \in [1, k])$，定义 $w(T_i) = \sum\limits_{v_j \in V_i} w(v_j)$，求 $\min\{\max\limits_{i = 1,\cdots, k}\{w(T_i)\}\}$。

解题思路：

要使得最大值最小，可以二分最大值 $lim$，问题变成判断能否划分出 $k - 1$ 个连通块使得最大值不超过 $lim$， 亦即判定划分连通块权值不超过 $lim$ 的连通块个数是否小于等于 $k$，即割去的边数小于 $k$。

我们可以考虑动态规划来解决。$dp[u]$ 代表以 $u$ 为根结点的子树，划分出尽可能少的连通块后，$u$ 结点所在的子树的点权和。由于需要最少划分，就是需要贪心合并，所以递归处理子树后， 对所有与 $u$ 相连的结点 $v$，按 $dp[v]$ 从小到大进行合并，最后返回割掉的边数。

总时间复杂度为 $O(T*nlog(\sum w_i))$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+9;
int n,k;
ll val[N];
vector<int> G[N];
ll dp[N];
void init(){
    for(int i = 1;i<=n;++i){
        dp[i] = 0;
        G[i].clear();
    }
}
int dfs(int u,int fa,ll lim){
    dp[u] = val[u];
    vector<ll> sondp;
    int res = 0;
    for(auto v : G[u]){
        if(v==fa) continue;
        res += dfs(v,u,lim);
        sondp.push_back(dp[v]);
    }
    sort(sondp.begin(),sondp.end());
    for(int i = 0;i<sondp.size();++i){
        if( dp[u] + sondp[i] <= lim) dp[u] += sondp[i];
        else{
            res += sondp.size() - i;
            break;
        }
    }
    return res;
}
bool judge(ll x){
    return dfs(1,0,x) <= k-1;
}
int main(){
    int T; scanf("%d",&T);
    for(int cas = 1;cas<=T;++cas){
        scanf("%d %d",&n,&k);
        init();
        for(int i = 1;i<n;++i){
            int u,v; scanf("%d %d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        ll sum = 0 , mx = -10;
        for(int i =1;i<=n;++i){
            scanf("%lld",val+i);
            sum += val[i];
            mx = max(mx,val[i]);
        }
        ll l = mx, r = sum , res;
        while(l<=r){
            ll m = (l+r)>>1;
            if(judge(m)){
                res = m;
                r = m-1;
            }
            else l = m + 1;
        }
        printf("Case #%d: %lld\n",cas,res);
    }
    return 0;
}

I - Portal

问题简述：

在一个广场上有两个人，然后有两道传送门（可以视为传送门之间距离为 $0$），现在让你安排这两个人的位置，使得一个人走到另一个人的位置的最短距离最大。

所需知识点：

计算几何，三分法。

问题形式化描述：

二维平面 $[0, A] × [0, B]$ 上，定义某两个点 $Q_1(X_1, Y_1),Q_2(X_2, Y_2)$ 之间距离是 $0$，即 $|Q_1Q_2| = 0$，两点 $P_1, P_2$ 距离为：
$dis(P_1, P_2) = \min\{|P_1P_2|,~|P_1Q_1| + |P_2Q_2|,~|P_1Q_2| + |P_2Q_1|\}$
求 $R_1, R_2$，最大化 $dis(R_1, R_2)$。

解题思路：

可知，要使得两点之间距离最短距离最大，其中一个点就要在矩阵的顶点，另一个点要在矩阵的边界上。

枚举四个顶点作为第一个点 $R_1$，再枚举另一个点是 $R_2$ 在矩形的哪一条边上，易知 $Q_1, Q_2$ 会把这一条边分成三部分，而从 $R_1$ 到 $R_2$ 要么经过 $Q_1, Q_2$，要么不经过，而这两种方式 $dis(R_1, R_2)$ 在每一部分是递增或递减的，可以用三分算法来找到极值，枚举所有情况取 $max$ 即得到答案。

总时间复杂度为 $O(T*log(\max\{A, B\}))$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
struct Point{
    double x,y;
    Point operator - (const Point& b)const{
        return (Point){x-b.x,y-b.y};
    }
    Point operator + (const Point& b)const{
        return (Point){x+b.x,y+b.y};
    }
    Point operator / (const double& b)const{
        return (Point){x/b,y/b};
    }
    Point operator * (const double& b)const{
        return (Point){x*b,y*b};
    }
}p0,ans1,ans2,p[20];
double dist(Point a,Point b){
    return (sqrt)( (a.x - b.x) * (a.x-b.x) + (a.y - b.y) * (a.y - b.y));
}
double ans;
double A,B,xa,ya,xb,yb;
double f(Point a,Point b,Point tar,bool show = 0){
    double t1 = dist(p0,tar);
    double t2 = dist(p0,a) + dist(b,tar);
    double t3 = dist(p0,b) + dist(a,tar);
    // if(show) cerr<<t1<<" "<<t2<<" "<<t3<<"ttt"<<endl;
    return min(t1,min(t2,t3) );
}
void work(Point p1,Point p2,Point le,Point ri){
    Point testl = le;
    Point testr = ri;
    for(int i = 1;i<=100;++i){
        Point fml = (ri+le*2)/3;
        Point fmr = (ri*2 + le)/3;
        if(f(p1,p2,fml) > f(p1,p2,fmr)){
            ri = fmr;
        }
        else le = fml;
    }
    if(f(p1,p2,le) > ans){
        ans = f(p1,p2,le);
        ans1 = p0;
        ans2 = le;
    }
}
void solve(){
    Point pt1 = (Point){xa,ya};
    Point pt2 = (Point){xb,yb};
    double d1 = dist(p0,pt1);
    double d2 = dist(p0,pt2);
    for(int i = 0;i<=11;++i){
        work(pt1,pt2,p[i],p[(i+1)%12]);
    }
}
int main(){
    int T; scanf("%d",&T);
    for(int cas = 1;cas<=T;++cas){
        scanf("%lf %lf %lf %lf %lf %lf",&A,&B,&xa,&ya,&xb,&yb);
        double mix = min(xa,xb);
        double miy = min(ya,yb);
        double mxx = max(xa,xb);
        double mxy = max(ya,yb);
        p[0] = (Point){0,0};
        p[1] = (Point){mix,0};
        p[2] = (Point){mxx,0};
        p[3] = (Point){A,0};
        p[4] = (Point){A,miy};
        p[5] = (Point){A,mxy};
        p[6] = (Point){A,B};
        p[7] = (Point){mxx,B};
        p[8] = (Point){mix,B};
        p[9] = (Point){0,B};
        p[10] = (Point){0,mxy};
        p[11] = (Point){0,miy};
        ans = -1;
        p0 = (Point){0,0};
        solve();
        p0 = (Point){0,B};
        solve();
        p0 = (Point){A,B};
        solve();
        p0 = (Point){A,0};
        solve();
        printf("Case #%d:\n",cas);
        printf("%.8f %.8f\n%.8f %.8f\n",ans1.x,ans1.y,ans2.x,ans2.y);
        // cerr<<ans<<"!"<<endl;
    }
}

J - Bob’s Poor Math

问题简述：

定义本题加法为不进位加法，初始给定 $n$ 个数，后有 $m$ 次操作，每次操作为 ① 加入某个数；② 将已有数除以 $10$；③ 询问 $a_i \oplus x$ 的最大值；④ 询问介于 $L$ 到 $R$ 的 $a_i$ 的和。

所需知识点：

字典树。

问题形式化描述：

要求设计一个数据结构，维护十进制下的数插入、所有数右移位、最大的异或 $x$ 的值、区间异或和。（定义十进制下的异或、移位为十进制不进位加法、整除 $10$）

解题思路：

动态插入、异或最大值，考虑使用字典树维护。建立十叉的字典树，将数从高位到低位插入到字典树中，高位不足则补 $0$，此处最大位数为 $10$，则实现了插入操作。其次为异或最大值，在字典树上贪心选择分支走即可。然后是移位操作，添加一个新根，则等效于所有数右移一位。为了支持求和操作，需要额外维护子树和，将查询 $sum[L, R]$ 分解为 $sum[1, R + 1) - sum[1, L)$，其中，若查询 $sum[1, L)$，则沿着 $L$ 在字典树上走，逐位考虑贡献添加进答案。

时间复杂度 $O(T * (10^2n + 10^3m))$。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
const int maxn = 1e4 + 5;
const int maxm = 2e5 + 5;

char sum[maxm][10], s[10], ss[10], ret[10];
int nxt[maxm][10], laz[maxm];
int a[maxn];
int n, m, cnt;

int add(){

    ++cnt, memset(nxt[cnt], 0, sizeof nxt[cnt]);
    memset(sum[cnt], '0', sizeof sum[cnt]), laz[cnt] = 0;
    return cnt;
}

void conv(int x, char *s){

    int n = 10;
    for( ; x; x /= 10) s[--n] = x % 10 + '0';
    while(n > 0) s[--n] = '0';
}

ll ston(char *s){

    ll ret = 0;
    for(int i = 0; i < 10; ++i) ret = ret * 10 + (s[i] - '0');
    return ret;
}

void pluss(char *s1, char *s2){

    for(int i = 0; i < 10; ++i){

        s1[i] = s1[i] + s2[i] - '0';
        if(s1[i] > '9') s1[i] -= 10;
    }
}

void subtract(char *s1, char *s2){

    for(int i = 0; i < 10; ++i){

        s1[i] = s1[i] - s2[i] + '0';
        if(s1[i] < '0') s1[i] += 10;
    }
}

void divide(int p, int d){

    d = min(d, 10);
    for(int i = 9; i >= d; --i) sum[p][i] = sum[p][i - d];
    for(int i = 0; i < d; ++i) sum[p][i] = '0';
}

void pushDown(int p){

    if(laz[p]){

        for(int i = 0; i < 10; ++i){

            int v = nxt[p][i];
            if(!v) continue;
            laz[v] += laz[p];
            divide(v, laz[p]);
        }
        laz[p] = 0;
    }
}

void insert(char *s){

    int p = 0; pushDown(p);
    for(int i = 0; i < 10; ++i){

        int t = s[i] - '0';
        if(!nxt[p][t]) nxt[p][t] = add();
        pluss(sum[p], s);
        p = nxt[p][t];
        pushDown(p);
    }
    pluss(sum[p], s);
}

void shift(){

    int p = 0, np = add();
    divide(p, 1);
    memcpy(nxt[np], nxt[p], sizeof nxt[p]);
    memcpy(sum[np], sum[p], sizeof sum[p]);
    laz[np] = laz[p] + 1;
    memset(nxt[p], 0, sizeof nxt[p]);
    nxt[p][0] = np;
    laz[p] = 0;
}

void queryMax(char *x, char *ret){

    int p = 0; pushDown(p);
    for(int i = 0; i < 10; ++i){

        int ch = x[i] - '0', t = -1;
        for(int j = 9; j >= 0; --j){

            t = (j - ch + 10) % 10;
            if(nxt[p][t]) break;
        }
        ret[i] = (t + ch) % 10 + '0';
        p = nxt[p][t];
        pushDown(p);
    }
}

void querySum(char *x, char *ret){

    memset(ret, '0', 10);
    int p = 0; pushDown(p);
    for(int i = 0; i < 10; ++i){

        int t = x[i] - '0';
        for(int j = 0; j < t; ++j){

            int v = nxt[p][j];
            if(!v) continue;
            pluss(ret, sum[v]);
        }
        p = nxt[p][t];
        if(!p) break;
        pushDown(p);
    }
}

void init(){

    cnt = -1; add();
}

int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){

        cin >> n >> m;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        init();
        for(int i = 1; i <= n; ++i){

            conv(a[i], s);
            insert(s);
        }
        cout << "Case #" << ++cas << ":\n";
        while(m--){

            char opt[10]; int x, y; cin >> opt;
            if(opt[2] == 'd'){

                cin >> x;
                conv(x, s);
                insert(s);
            }
            else if(opt[2] == 'i'){

                shift();
            }
            else if(opt[2] == 'e'){

                cin >> x;
                conv(x, s);
                queryMax(s, ret);
                ll ans = ston(ret);
                cout << ans << "\n";
            }
            else{

                cin >> x >> y;
                conv(++y, s);
                querySum(s, ret);
                conv(x, s);
                querySum(s, ss);
                subtract(ret, ss);
                ll ans = ston(ret);
                cout << ans << "\n";
            }
        }
    }
    return 0;
}

K - Color Graph

问题简述：

给定 $n$ 个顶点、$m$ 条边的简单无向图，初始边全为白边，求能染的最多的红边，使得红边不构成奇环。

所需知识点：

二进制枚举、二分图定义。

问题形式化描述：

给定简单无向图 $G = (V, E)$，求生成子图 $G' = (V' = V, E' \subseteq E)$ 使得 $\mid E' \mid$ 最大，且该 $G'$ 为二分图。

解题思路：

$n$ 很小，二进制枚举二分图 $G'$ 左部顶点 $V_1$，可以唯一确定右部顶点 $V_2$ 以及边集 $E'$，记录最大答案即可，时间复杂度 $O(T*2^nm)$。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
const int maxn = 1e2 + 5;

int G[maxn][maxn], tag[maxn];
int n, m;

int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){

        cin >> n >> m;
        for(int i = 0; i < n; ++i){

            for(int j = 0; j < n; ++j) G[i][j] = 0;
        }
        while(m--){

            int u, v; cin >> u >> v; --u, --v;
            G[u][v] = G[v][u] = 1;
        }
        int ret = 0, lim = 1 << (n - 1); // 对称性优化，not (1 << n)
        for(int i = 1; i < lim; ++i){

            for(int j = 0; j < n; ++j) tag[j] = (i >> j) & 1;
            int tmp = 0;
            for(int j = 0; j < n; ++j){

                if(tag[j]) continue;
                for(int k = 0; k < n; ++k) tmp += G[j][k] && tag[j] != tag[k];
            }
            ret = max(ret, tmp);
        }
        cout << "Case #" << ++cas << ": " << ret << "\n";
    }
    return 0;
}

M - Blood Pressure Game

问题简述：

给出坐过山车过程的 $n$ 个转折点高度 $a_i$，则坐过山车血压值增加量为 $\sum\limits_{i = 1}^{n - 1} \mid a_i - a_{i + 1} \mid$。给出 $m$ 个可新增的转折点高度 $b_i$，每个 $a_i$ 间至多插入一个 $b_j$，特殊的，$a_1$ 前与 $a_n$ 后也可作为插入点，血压值增加量仍按相邻转折点高度差之和计算。问插入 $1, 2, \cdots, m$ 个转折点时能获得的最大血压增量为多少。

所需知识点：

最小费用流。

问题形式化描述：

给定二分图 $G$，左部顶点 $b_i$ 共 $m$ 个，右部顶点 $c_i$ 共 $n + 1$ 个，边 $(b_i, c_j)$ 权重为 $\mid b_i - a_j \mid + \mid b_i - a_{j - 1}\mid - \mid a_j - a_{j - 1}\mid (1 \leq i \leq m, 2 \leq j \leq n)$，特殊的，边 $(b_i, c_1)$ 权重为 $\mid b_i - a_1\mid$，边 $(b_i, c_{n + 1})$ 权重为 $\mid b_i - a_n \mid$，分别求匹配数为 $1, 2, \cdots, m$ 时最大权匹配。

解题思路：

转化为二分图最大权 $k$ 匹配后，用网络流建模，匹配数限制为流量，最大权重转化为最小费用，则求最小费用最大流，由于流量递增，只需跑一次流量为 $m$ 的费用流，记录中间结果即可。

将 $m$ 视为 $n$ 同阶，时间复杂度为 $O(T * n^4)$，由于使用的是 $SPFA$ 增广，随机图下期望复杂度为 $O(T * n^3)$，可通过本题。

参考代码：

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
const int maxn = 2e3 + 5;
const ll inf = 1ll << 60;
 
template<class ll>
struct Dinic{
 
    struct Edge{ int v, rev; ll cap, cot; };
    vector<Edge> G[maxn];
    ll dis[maxn];
    int cur[maxn], vis[maxn], n, sp, tp;
    void init(int nn){
 
        n = nn;
        for(int i = 1; i <= n; ++i) G[i].clear();
    }
    void add(int u, int v, ll cap, ll cot){
 
        G[u].pb({v, sz(G[v]), cap, cot});
        G[v].pb({u, sz(G[u]) - 1, 0, -cot});
    }
    int bfs(){
 
        queue<int> q;
        for(int i = 1; i <= n; ++i) dis[i] = inf, vis[i] = 0;
        dis[sp] = 0, q.push(sp), vis[sp] = 1;
        while(!q.empty()){
 
            int u = q.front(); q.pop(); vis[u] = 0;
            for(Edge &e : G[u]){
 
                if(e.cap && dis[e.v] > dis[u] + e.cot){
 
                    dis[e.v] = dis[u] + e.cot;
                    if(!vis[e.v]) q.push(e.v), vis[e.v] = 1;
                }
            }
        }
        return dis[tp] != inf;
    }
    ll dfs(int u, ll flow){
 
        if(u == tp || !flow) return flow;
        ll ret = 0, tmp; vis[u] = 1;
        for(int &i = cur[u]; i < sz(G[u]); ++i){
 
            Edge &e = G[u][i];
            if(!vis[e.v] && dis[e.v] == dis[u] + e.cot && (tmp = dfs(e.v, min(e.cap, flow - ret)))){
 
                ret += tmp, e.cap -= tmp, G[e.v][e.rev].cap += tmp;
                if(ret == flow) { vis[u] = 0; return ret; }
            }
        }
        if(!ret) vis[u] = 1;
        return ret;
    }
    pair<ll, ll> solve(int s, int t, ll ans[]){
 
        sp = s, tp = t;
        ll mf = 0, mc = 0;
        while(bfs()){
 
            for(int i = 1; i <= n; ++i) cur[i] = 0;
            ll tmp = dfs(sp, inf);
            for(int i = 1; i <= tmp; ++i) // 流量递增，统计费用
            	ans[i + mf] = ans[i + mf - 1] + dis[tp];
            mf += tmp, mc += tmp * dis[tp];
        }
        return {mf, mc};
    }
};
 
Dinic<ll> dn;
ll ans[maxn];
int a[maxn], b[maxn];
int n, m;
 
int main(){
  
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){
 
        cin >> n >> m;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 1; i <= m; ++i) cin >> b[i];
        cout << "Case #" << ++cas << ":\n";
        ll base = 0;
        for(int i = 1; i < n; ++i) base += abs(a[i] - a[i + 1]);
        int S = m + n + 2, T = S + 1;
        dn.init(T);
        for(int i = 1; i <= m; ++i) dn.add(S, i, 1, 0);
        for(int i = 1; i <= n + 1; ++i) dn.add(m + i, T, 1, 0);
        for(int i = 1; i <= m; ++i){
 
            dn.add(i, m + 1, 1, -abs(b[i] - a[1]));
            dn.add(i, m + n + 1, 1, -abs(b[i] - a[n]));
            for(int j = 2; j <= n; ++j){
 
                int dt = abs(b[i] - a[j - 1]) + abs(b[i] - a[j]) 
                		- abs(a[j] - a[j - 1]);
                dn.add(i, m + j, 1, -dt);
            }
        }
        dn.solve(S, T, ans);
        for(int i = 1; i <= m; ++i) cout << base - ans[i] << " ";
        cout << "\n";
        for(int i = 1; i <= n + 1; ++i){
 
            int p = 0;
            for(auto &e : dn.G[m + i]){
 
                if(e.v == T || !e.cap) continue;
                p = e.v; break;
            }
            if(p) cout << b[p] << " ";
            if(i <= n) cout << a[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

L - Light It Down

问题简述：

给定 $n$ 个结点的树，边带权，有 $m$ 个关键点上各有一个亮或暗的灯泡，起始点为非关键点 $S$，每次两结点间跳转沿树上最短路径移动。在关键点时等概率向非关键点跳转；在非关键点时等概率向所有点跳转，且若目标结点是关键点，则切换其灯泡状态。问在 $S$ 开始，使得所有关键点灯泡全暗的期望移动距离。

所需知识点：

树形 $dp$，概率与期望，高斯消元。

问题形式化描述：

定义新图 $G = (V, E')$，原树上的跳转 $u \rightarrow v$ 均对应 $G$ 上一条带权单向边 $(u, v, dis(u, v))$，设关键点 $v_1, v_2, \cdots, v_m$，各灯泡状态 $s_1, s_2, \cdots, s_m(s_i \in \{0, 1\})$，图 $G$ 上，从 顶点 $S$ 出发，等概率向邻接顶点移动，求经过 $v_i$ 次数的奇偶性为 $s_i$ 时的期望移动距离。

解题思路：

记非关键点为 $u_i(i \in [1, n - m])$，关键点为 $v_i(i \in [1, m])$，特殊的，$S = u_1$。依照跳转双方分为三种情况：① $S \rightarrow v$；② $v \rightarrow u(同 u \rightarrow v)$；③ $u \rightarrow u$。

忽略 ①，假定 $u_i$ 等概率成为 $S$，只需在考虑完 ②③ 后，将其中一次 $u \rightarrow v$ 的跳转期望距离改为 $S \rightarrow v$ 的期望距离。

考虑 ②，当前起点为 $u$，若 $s_i = s_j$，则 $v_i, v_j$ 与 $u$ 间的期望跳转次数相同。记 $f[i][0/1](i \in [0, m - 1])$ 为 $\sum\limits_{k = 2}^{m} s_k = i，$$s_1 = 0/1$ 时，$v_1$ 与 $u$ 间期望的跳转次数，有：
$f[i][j] = \begin{cases}\cfrac{1}{m}(f[i][j\oplus1] + 2) + \cfrac{i}{m}f[i - 1][j] + \cfrac{m - i - 1}{m}f[i + 1][j], ~i \gt 1 \\ ~ \\ 0, ~i = 0, j = 0 \\ ~ \\\cfrac{1}{m}(f[0][0] + 1) + \cfrac{m - 1}{m}f[1][1], ~i = 0, j = 1 \end{cases}$
得到 $2m$ 个方程，可以用高斯消元 $O(m^3)$ 得到解，但效率太低。

注意到这是 $2*m$ 网格图上开关灯模型，对 $n * m$ 的网格图采取主元递推的方式再进行高斯消元，可以做到 $O(nm*\min\{n, m\})$，那么这里可以做到 $O(m)$，具体为：

设 $f[m - 1][0] = x, f[m - 1][1] = y$，递推表示 $f[m - 2][0/1], \cdots, f[0][0/1]$，再对 $f[0][0], f[0][1]$ 两个方程进行高斯消元得到 $x, y$，回代得到所有解。

至此，得到 $v_i$ 与 $u$ 的期望跳转次数 $num_i$，预处理 $v_i$ 到 $u$ 的平均距离，则可得到 ② 部分的答案。

考虑 ③，令 $tot\_num = \sum\limits_{i = 1}^{m} num_i$，则跳转期间 $v \rightarrow u$ 的次数为 $\cfrac{tot\_num - 1}{2}$，考虑单次 $u \rightarrow u$ 自身连续跳转的期望次数 $X$，易知 $X$ 服从几何分布，易得 $E(X) = \frac{1}{\frac{m}{n}} - 1 = \cfrac{n}{m} - 1$，预处理 $u$ 到 $u$ 的平均距离，则可得到 ③ 部分的答案。

回过头计算出 $S \rightarrow v$ 这一次跳转的期望距离，替换掉 ② 部分某次 $u \rightarrow v$，则得到最终答案。

上述单次 $S \rightarrow v, v_i \rightarrow u, u \rightarrow u$ 的期望移动距离均可通过树形 $dp$ 在 $O(n)$ 预处理得到。

$O(n)$ 预处理 $1\cdots n$ 的逆元，考虑高斯消元过程中的一次快速幂求逆元，总时间复杂度为 $O(T*(n + logP))$，其中 $P$ 为模数 $10^9 + 7$。

参考代码：

#include<bits/stdc++.h>

using namespace std;
#define sz(a) ((int)a.size())
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

struct Node{
	int a, b, c;
	Node(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {}
	Node operator * (const int &o) const{
		return Node(a * 1ll * o % mod, b * 1ll * o % mod, c * 1ll * o % mod);
	}
	Node operator - (const int &o) const{
		return Node(a, b, (c - o + mod) % mod);
	}
	Node operator - (const Node &o) const{
		return Node((a - o.a + mod) % mod, (b - o.b + mod) % mod, (c - o.c + mod) % mod);
	}
	int get(int x, int y){
		return (a * 1ll * x + b * 1ll * y + c) % mod;
	}
} f[maxn][2];
vector<pii> G[maxn];
int inv[maxn], pos[maxn], sta[maxn], tag[maxn], siz[maxn][2];
ll dis[maxn][2], num[maxn];
int n, m, rt, tot;

void dfs1(int u, int f){

	siz[u][tag[u]] = 1, siz[u][tag[u] ^ 1] = 0;
	dis[u][0] = dis[u][1] = 0;
	for(auto &e : G[u]){

		int v = e.second, w = e.first;
		if(v == f) continue;
		dfs1(v, u);
		for(int i = 0; i < 2; ++i){

			siz[u][i] += siz[v][i];
			dis[u][i] = (dis[u][i] + dis[v][i] + siz[v][i] * 1ll * w) % mod;
		}
	}
}

void dfs2(int u, int f){

	for(auto &e : G[u]){

		int v = e.second, w = e.first;
		if(v == f) continue;
		for(int i = 0; i < 2; ++i){

			dis[v][i] += dis[u][i] - (dis[v][i] + siz[v][i] * 1ll * w) 
			       		 + (siz[rt][i] - siz[v][i]) * 1ll * w;
			dis[v][i] = (dis[v][i] % mod + mod) % mod;
		}
		dfs2(v, u);
	}
}

ll qpow(ll a, ll b){

	ll ret = 1;
	while(b){

		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

// Ax + By = C
// Dx + Ey = F
pii cal(int A, int B, int C, int D, int E, int F){

	int det = (A * 1ll * E % mod - B * 1ll * D % mod + mod) % mod;
	int invd = qpow(det, mod - 2);
	int x = (C * 1ll * E % mod - B * 1ll * F % mod + mod) * invd % mod;
	int y = (A * 1ll * F % mod - C * 1ll * D % mod + mod) * invd % mod;
	return {x, y};
}

int main(){

	ios::sync_with_stdio(0); cin.tie(0);
	inv[0] = inv[1] = 1;
	for(int i = 2; i < maxn; ++i){

		inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
	}
	int t, cas = 0; cin >> t;
	while(t--){

		cin >> n >> m >> rt;
		tot = 0;
		for(int i = 1; i <= n; ++i){

			G[i].clear();
			tag[i] = 0;
		}
		for(int i = 1; i < n; ++i){

			int u, v, w; cin >> u >> v >> w;
			G[u].pb({w, v});
			G[v].pb({w, u});
		}
		for(int i = 1; i <= m; ++i){

			cin >> pos[i] >> sta[i];
			tag[pos[i]] = 1;
			tot += sta[i];
		}
		cout << "Case #" << ++cas << ": ";
		if(!tot){

			cout << "0\n";
			continue;
		}

		// dis[i][0]：点 i 到所有非关键点的距离之和
		// dis[i][1]：点 i 到所有关键点的距离之和
		dfs1(rt, 0);
		dfs2(rt, 0);

		// f[i][0/1]：除当前点外还有 i 个关键点，当前关键点 sta = 0/1 时，
		//  		  当前关键点 <-> 非关键点跳转的期望次数
		if(m == 1){

			num[1] = sta[1] ? 1 : 0;
		}
		else{

			f[m - 1][0] = Node(1, 0, 0);
			f[m - 1][1] = Node(0, 1, 0);
			for(int i = m - 1; i; --i){

				for(int j = 0; j < 2; ++j){

					// f[i][j] = 1/m*(f[i][j^1]+2) + i/m*f[i-1][j] + (m-i-1)/m*f[i+1][j]
					// => f[i-1][j] = m/i*f[i][j] - 1/i*f[i][j^1] - 2/i - (m-i-1)/i*f[i+1][j]

					f[i - 1][j] = (f[i][j] * (m * 1ll * inv[i] % mod)) 
					              - (f[i][j ^ 1] * inv[i]) - (2 * inv[i] % mod);
					if(i + 1 <= m - 1){
					
						f[i - 1][j] = f[i - 1][j] - (f[i + 1][j] * ((m - i - 1) * 1ll * inv[i] % mod));
					}
				}
			}

			// f[0][0] = 0

			// f[0][1] = 1/m*(f[0][0]+1) + (m-1)/m*f[1][1]
			// => f[0][1] - 1/m*(f[0][0]+1) + (m-1)/m*f[1][1] = 0
			
			Node equ0 = f[0][0];
			Node equ1 = f[0][1] - (f[1][1] * ((m - 1) * 1ll * inv[m] % mod)) - inv[m];
			pii ret = cal(equ0.a, equ0.b, mod - equ0.c, equ1.a, equ1.b, mod - equ1.c);
			for(int i = 1; i <= m; ++i){

				if(sta[i]) num[i] = f[tot - 1][1].get(ret.first, ret.second);
				else num[i] = f[tot][0].get(ret.first, ret.second);
			}
		}

		// tot_num：关键点间跳转经过的非关键点次数
		ll tot_num = 0;
		for(int i = 1; i <= m; ++i){

			tot_num = (tot_num + num[i]) % mod;
		}
		tot_num = (tot_num - 1 + mod) * inv[2] % mod;

		// avg00：单次连续的非关键点 <-> 非关键点跳转的期望距离
		// avg01：单次关键点 -> 非关键点（或非关键点 -> 关键点）跳转的期望距离
		ll avg00 = 0, avg01 = 0;
		for(int i = 1; i <= n; ++i){

			if(tag[i]) continue;
			avg00 = (avg00 + dis[i][0]) % mod;
			avg01 = (avg01 + dis[i][1]) % mod; 
		}
		avg00 = avg00 * inv[n - m] % mod * inv[n - m] % mod;
		avg00 = avg00 * (n * 1ll * inv[m] % mod - 1 + mod) % mod;
		avg01 = avg01 * inv[m] % mod * inv[n - m] % mod;

		// avgS1：起始点 -> 第一个关键点跳转的期望距离
		ll avgS1 = 0;
		avgS1 = (dis[rt][0] + dis[rt][1]) * inv[n] % mod;
		avgS1 = (avgS1 + (n - m) * 1ll * inv[n] % mod * (avg00 + avg01) % mod) % mod;

		ll ans = 0;

		// 关键点 <-> 非关键点
		for(int i = 1; i <= m; ++i){

			ans = (ans + num[i] * dis[pos[i]][0] % mod * inv[n - m] % mod) % mod;
		}
		
		// 起始点 -> 第一个关键点
		ans = (ans - avg01 + avgS1 + mod) % mod;

		// 非关键点 <-> 非关键点
		ans = (ans + tot_num * avg00 % mod) % mod;

		cout << ans << "\n";
	}
	return 0;
}

转载：https://blog.csdn.net/weixin_44059127/article/details/105909698