「ZR 18 省选 3」题解

Author： RainAir
发布时间：December 6, 2020
956views
One comment
538 words
Categories：题解

A. 树的染色

如果确定了某个点的颜色，我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。

我们设 $f_v$ 表示钦定 $v$ 是白色，子树内是黑色的点的权值和的最小值。

合并子树的时候钦定当前的根是白色，如果儿子 $x$ 和根同色子树和贡献 $a_x$，答案贡献 $f_x$；否则子树和贡献 $f_x$，答案贡献 $a_x$，背包合并即可。复杂度 $O(nm)$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000+5;
const int MAXM = 5000+5;

std::vector<int> G[MAXN];
int n,a[MAXN];
int f[MAXN];
// 和 v 颜色不同的最小代价 (钦定 v 颜色为 0)
int g[2][MAXM];
bool flag;

inline void dfs(int v){
    if(G[v].empty()){
        f[v] = 0;
        return;
    }
    for(auto x:G[v]) dfs(x);
    int now = 0;CLR(g[now],0x3f);g[now][0] = 0;
    for(auto x:G[v]){
        CLR(g[now^1],0x3f);
        FOR(i,0,MAXM){
            if(i+a[x] < MAXM) g[now^1][i+a[x]] = std::min(g[now^1][i+a[x]],g[now][i]+f[x]);
            if(i+f[x] < MAXM) g[now^1][i+f[x]] = std::min(g[now^1][i+f[x]],g[now][i]+a[x]);
        }
        now ^= 1;
    }
    f[v] = 0x3f3f3f3f;
    FOR(i,0,a[v]) f[v] = std::min(f[v],g[now][i]);
    if(f[v] == 0x3f3f3f3f) flag = 0;
}

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) G[i].clear();
    FOR(i,2,n){
        int f;scanf("%d",&f);G[f].pb(i);
    }
    FOR(i,1,n) scanf("%d",a+i);
    flag = 1;dfs(1);
    puts(flag?"POSSIBLE":"IMPOSSIBLE");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

B. 树形图求和

以某个点 $r$ 为根的内向树/外向树计数就是出度矩阵/入度矩阵（可以记成根的度数为 $0$ 的那个）减邻接矩阵，删掉第 $r$ 行第 $r$ 列的行列式。

如何求一条边的出现次数呢？用总次数减掉这条边不出现的次数，于是相当于要每次修改矩阵上的两个点（在同一行），然后求一下行列式。设这个矩阵为 $A$，记 $|A|$ 表示矩阵 $A$ 的行列式。

做法 1：伴随矩阵

记矩阵 $A$ 的代数余子式 $C_{i,j}$ 为删掉第 $i$ 行第 $j$ 列的行列式乘上 $(-1)^{i+j}$。

那么 $A$ 的伴随矩阵 $adj(A)=C^T$。

伴随矩阵有一个性质：$adj(A^{-1}) = \frac{A}{|A|}$，所以可以得到 $adj(A) = \frac{A^{-1}}{|A^{-1}|} = |A|A^{-1}$。（因为有 $|A|*|A^{-1}| = 1$）。

所以我们只需要写个矩阵求逆就能求出伴随矩阵了。

考虑我们如果修改了第 $i$ 行的某些值，如何快速计算新矩阵的行列式？暴力算是单次 $O(n^3)$ 的。

根据拉普拉斯展式，可以得到：

$$ \forall i ,|A| = \sum_{j=1}^n C_{i,j}A_{i,j} $$

所以我们就可以 $O(n)$ 求出来某行修改后的行列式；但是注意到这里只修改了 $O(1)$ 个位置，我们算一下增量就可以 $O(1)$ 求出修改某个位置后的矩阵行列式是啥了。

复杂度 $O(n^3+m)$。

做法 2：多项式

发现 $\sum_{i=1}^n w_i$ 其实就是 $\prod_{i=1}^n (1+w_ix)$ 的一次项系数，所以我们在 $\pmod {x^2}$ 的意义下做多项式运算就好了。

比较难定义的是除法，其实我们就是要求 $ax+b$ 的逆，设逆为 $cx+d$，可以得到 $(ax+b)(cx+d) = 1$，解方程可得 $c=-\frac{a}{b^2},d = \frac{1}{b}$，也就是说 $ax+b$ 的逆是 $-\frac{a}{b^2}x+\frac{1}{b}$，这样就可以转化为乘法了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 300+5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int a[MAXN][MAXN],n,m;
int A[MAXN][MAXN],b[MAXN][MAXN];
// b: 伴随矩阵
// A: 原矩阵
// a: 消元用

struct Edge{
    int u,v,w;
    Edge(int u=0,int v=0,int w=0) : u(u),v(v),w(w) {}
}e[200000+5];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int Gauss(){
    FOR(i,1,n) b[i][i] = 1;
    int ans = 1;
    FOR(i,1,n){
        int t = -1;
        FOR(j,i,n) if(a[j][i]){t = j;break;}
        if(t != i) std::swap(a[i],a[t]),ans = ha-ans,std::swap(b[i],b[t]);
        ans = 1ll*ans*a[i][i]%ha;
        int inv = qpow(a[i][i]);
        FOR(j,1,n) a[i][j] = 1ll*a[i][j]*inv%ha,b[i][j] = 1ll*b[i][j]*inv%ha;
        FOR(j,1,n){
            if(j == i) continue;
            int t = a[j][i];
            FOR(k,1,n){
                add(a[j][k],ha-1ll*a[i][k]*t%ha);
                add(b[j][k],ha-1ll*b[i][k]*t%ha);
            }
        }
    }
    FOR(i,1,n) FOR(j,1,n) b[i][j] = 1ll*b[i][j]*ans%ha;
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);e[i] = Edge(u,v,w);
        add(a[u][v],ha-1);
        add(a[u][u],1);
    }
    FOR(i,1,n) a[n][i] = a[i][n] = 0;
    --n;
    FOR(i,1,n) FOR(j,1,n) A[i][j] = a[i][j];
    Gauss();
    int ans = 0;
    FOR(i,1,m){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        if(u == n+1) continue;
        int c = (b[u][u]+ha-b[v][u])%ha;
        /*
        add(c,ha-b[u][u]);
        if(v != n+1){
            add(c,b[u][v]);
        }
        c = ha-c;add(c,all);*/
        add(ans,1ll*c*w%ha);
    }
    printf("%d\n",ans);
    return 0;
}

C. 波波老师

建后缀自动机，只出现一次的节点一定是后缀树上的叶子节点。

考虑对于后缀 $i$ ，我们求出最小的 $f_i$，满足 $[i,i+f_i-1]$ 是这个点所代表的区间，相当于我们要对区间 $[i,i+f_i-1]$ 对 $f_i$ 取 $\min$，然后对 $[i+f_i,n]$ 对 $f_{i}+1,f_{i}+2,\ldots$ 这个等差数列取 $\min$。

发现我们可以先做完对 $[i,i+f_i-1]$ 取 $\min$，然后再一遍递推过来（$ans_{i}$ 与 $ans_{i-1}+1$ 取 $\min$），现在相当于只需要快速实现区间对一个数取 $\min$。

线段树可以得到 $O(n \log n)$ 的复杂度。

桶排+并查集可以得到 $O(n \alpha(n))$ 的复杂度。

如果你发现对于 $i<j$，一定有 $f_i \leq f_j$，那么就可以用单调队列维护这个东西，复杂度 $O(n)$。

注意 SAM 数组要开 2 倍空间（

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;

int ch[MAXN<<1][5],fail[MAXN<<1],len[MAXN<<1],tot = 1,las = 1;
int id[MAXN];
char str[MAXN];
bool vis[MAXN<<1];
int n;

inline int insert(int c){
    int p = las,np = las = ++tot;len[np] = len[p]+1;
    for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np;
    if(!p) fail[np] = 1;
    else{
        int q = ch[p][c];
        if(len[q] == len[p]+1) fail[np] = q;
        else{
            int nq = ++tot;FOR(i,0,4) ch[nq][i] = ch[q][i];len[nq] = len[p]+1;fail[nq] = fail[q];
            fail[q] = fail[np] = nq;
            for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq;
        }
    }
    return np;
}

int ans[MAXN];
int f[MAXN];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    ROF(i,n,1) id[i] = insert(str[i]-'a');
    FOR(i,1,tot) vis[fail[i]] = 1;
    FOR(i,1,n){
        if(vis[id[i]]) f[i] = 1e9;
        else f[i] = len[fail[id[i]]]+1;
//        DEBUG(f[i]);
    }
    std::deque<int> q;
    FOR(i,1,n) ans[i] = 1e9;
    FOR(i,1,n){
        while(!q.empty() && f[q.back()] >= f[i]) q.pop_back();
        q.pb(i);
        ans[i] = f[q[0]];
        while(!q.empty() && q[0]+f[q[0]]-1 <= i) q.pop_front();
    }
    FOR(i,2,n) ans[i] = std::min(ans[i],ans[i-1]+1);
    LL res = 0;FOR(i,1,n) res += ans[i];
    printf("%lld\n",res);
    return 0;
}

Last modification：December 6th, 2020 at 09:54 pm

如果觉得我的文章对你有用，请随意赞赏

One comment

QAQ
January 10th, 2021 at 04:32 pm

太无敌了

Reply

「ZR 18 省选 3」题解

RainAir • 2020 年 12 月 06 日

A. 树的染色

如果确定了某个点的颜色，我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。

我们设 $f_v$ 表示钦定 $v$ 是白色，子树内是黑色的点的权值和的最小值。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000+5;
const int MAXM = 5000+5;

std::vector<int> G[MAXN];
int n,a[MAXN];
int f[MAXN];
// 和 v 颜色不同的最小代价 (钦定 v 颜色为 0)
int g[2][MAXM];
bool flag;

inline void dfs(int v){
    if(G[v].empty()){
        f[v] = 0;
        return;
    }
    for(auto x:G[v]) dfs(x);
    int now = 0;CLR(g[now],0x3f);g[now][0] = 0;
    for(auto x:G[v]){
        CLR(g[now^1],0x3f);
        FOR(i,0,MAXM){
            if(i+a[x] < MAXM) g[now^1][i+a[x]] = std::min(g[now^1][i+a[x]],g[now][i]+f[x]);
            if(i+f[x] < MAXM) g[now^1][i+f[x]] = std::min(g[now^1][i+f[x]],g[now][i]+a[x]);
        }
        now ^= 1;
    }
    f[v] = 0x3f3f3f3f;
    FOR(i,0,a[v]) f[v] = std::min(f[v],g[now][i]);
    if(f[v] == 0x3f3f3f3f) flag = 0;
}

inline void Solve(){
    scanf("%d",&n);FOR(i,1,n) G[i].clear();
    FOR(i,2,n){
        int f;scanf("%d",&f);G[f].pb(i);
    }
    FOR(i,1,n) scanf("%d",a+i);
    flag = 1;dfs(1);
    puts(flag?"POSSIBLE":"IMPOSSIBLE");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

B. 树形图求和

以某个点 $r$ 为根的内向树/外向树计数就是出度矩阵/入度矩阵（可以记成根的度数为 $0$ 的那个）减邻接矩阵，删掉第 $r$ 行第 $r$ 列的行列式。

做法 1：伴随矩阵

记矩阵 $A$ 的代数余子式 $C_{i,j}$ 为删掉第 $i$ 行第 $j$ 列的行列式乘上 $(-1)^{i+j}$。

那么 $A$ 的伴随矩阵 $adj(A)=C^T$。

伴随矩阵有一个性质：$adj(A^{-1}) = \frac{A}{|A|}$，所以可以得到 $adj(A) = \frac{A^{-1}}{|A^{-1}|} = |A|A^{-1}$。（因为有 $|A|*|A^{-1}| = 1$）。

所以我们只需要写个矩阵求逆就能求出伴随矩阵了。

考虑我们如果修改了第 $i$ 行的某些值，如何快速计算新矩阵的行列式？暴力算是单次 $O(n^3)$ 的。

根据拉普拉斯展式，可以得到：

$$ \forall i ,|A| = \sum_{j=1}^n C_{i,j}A_{i,j} $$

复杂度 $O(n^3+m)$。

做法 2：多项式

发现 $\sum_{i=1}^n w_i$ 其实就是 $\prod_{i=1}^n (1+w_ix)$ 的一次项系数，所以我们在 $\pmod {x^2}$ 的意义下做多项式运算就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 300+5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int a[MAXN][MAXN],n,m;
int A[MAXN][MAXN],b[MAXN][MAXN];
// b: 伴随矩阵
// A: 原矩阵
// a: 消元用

struct Edge{
    int u,v,w;
    Edge(int u=0,int v=0,int w=0) : u(u),v(v),w(w) {}
}e[200000+5];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int Gauss(){
    FOR(i,1,n) b[i][i] = 1;
    int ans = 1;
    FOR(i,1,n){
        int t = -1;
        FOR(j,i,n) if(a[j][i]){t = j;break;}
        if(t != i) std::swap(a[i],a[t]),ans = ha-ans,std::swap(b[i],b[t]);
        ans = 1ll*ans*a[i][i]%ha;
        int inv = qpow(a[i][i]);
        FOR(j,1,n) a[i][j] = 1ll*a[i][j]*inv%ha,b[i][j] = 1ll*b[i][j]*inv%ha;
        FOR(j,1,n){
            if(j == i) continue;
            int t = a[j][i];
            FOR(k,1,n){
                add(a[j][k],ha-1ll*a[i][k]*t%ha);
                add(b[j][k],ha-1ll*b[i][k]*t%ha);
            }
        }
    }
    FOR(i,1,n) FOR(j,1,n) b[i][j] = 1ll*b[i][j]*ans%ha;
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);e[i] = Edge(u,v,w);
        add(a[u][v],ha-1);
        add(a[u][u],1);
    }
    FOR(i,1,n) a[n][i] = a[i][n] = 0;
    --n;
    FOR(i,1,n) FOR(j,1,n) A[i][j] = a[i][j];
    Gauss();
    int ans = 0;
    FOR(i,1,m){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        if(u == n+1) continue;
        int c = (b[u][u]+ha-b[v][u])%ha;
        /*
        add(c,ha-b[u][u]);
        if(v != n+1){
            add(c,b[u][v]);
        }
        c = ha-c;add(c,all);*/
        add(ans,1ll*c*w%ha);
    }
    printf("%d\n",ans);
    return 0;
}

C. 波波老师

建后缀自动机，只出现一次的节点一定是后缀树上的叶子节点。

发现我们可以先做完对 $[i,i+f_i-1]$ 取 $\min$，然后再一遍递推过来（$ans_{i}$ 与 $ans_{i-1}+1$ 取 $\min$），现在相当于只需要快速实现区间对一个数取 $\min$。

线段树可以得到 $O(n \log n)$ 的复杂度。

桶排+并查集可以得到 $O(n \alpha(n))$ 的复杂度。

如果你发现对于 $i<j$，一定有 $f_i \leq f_j$，那么就可以用单调队列维护这个东西，复杂度 $O(n)$。

注意 SAM 数组要开 2 倍空间（

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;

int ch[MAXN<<1][5],fail[MAXN<<1],len[MAXN<<1],tot = 1,las = 1;
int id[MAXN];
char str[MAXN];
bool vis[MAXN<<1];
int n;

inline int insert(int c){
    int p = las,np = las = ++tot;len[np] = len[p]+1;
    for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np;
    if(!p) fail[np] = 1;
    else{
        int q = ch[p][c];
        if(len[q] == len[p]+1) fail[np] = q;
        else{
            int nq = ++tot;FOR(i,0,4) ch[nq][i] = ch[q][i];len[nq] = len[p]+1;fail[nq] = fail[q];
            fail[q] = fail[np] = nq;
            for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq;
        }
    }
    return np;
}

int ans[MAXN];
int f[MAXN];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    ROF(i,n,1) id[i] = insert(str[i]-'a');
    FOR(i,1,tot) vis[fail[i]] = 1;
    FOR(i,1,n){
        if(vis[id[i]]) f[i] = 1e9;
        else f[i] = len[fail[id[i]]]+1;
//        DEBUG(f[i]);
    }
    std::deque<int> q;
    FOR(i,1,n) ans[i] = 1e9;
    FOR(i,1,n){
        while(!q.empty() && f[q.back()] >= f[i]) q.pop_back();
        q.pb(i);
        ans[i] = f[q[0]];
        while(!q.empty() && q[0]+f[q[0]]-1 <= i) q.pop_front();
    }
    FOR(i,2,n) ans[i] = std::min(ans[i],ans[i-1]+1);
    LL res = 0;FOR(i,1,n) res += ans[i];
    printf("%lld\n",res);
    return 0;
}

「ZR 18 省选 3」题解

A. 树的染色

B. 树形图求和

做法 1：伴随矩阵

做法 2：多项式

C. 波波老师

One comment

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「JZOJ6281」串

CF 1407 题解

「JLOI2016」成绩比较

简单数论公式

此内容被密码保护

「ZR 18 省选 3」题解

A. 树的染色

B. 树形图求和

做法 1：伴随矩阵

做法 2：多项式

C. 波波老师