ZR2020 普及五连测 day1

Author： RainAir
发布时间：September 14, 2020
1006views
No comments
1384 words
Categories：题解

A

设 $f_i$ 表示长度为 $i$ 的答案。考虑开头的元素：首先它只能选择 $\{1,2\}$。如果选择了 $1$，那么变成了 $n-1$ 的子问题；如果选择了 $2$，那么第二个数必须选择 $1$，变成了 $n-2$ 的子问题。所以 $f_i = f_{i-1}+f_{i-2}$，注意到斐波那契数列的通项公式是 $f_n = \frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$，但是 $5$ 在 $998244353$ 下没有二次剩余，所以可以通过扩域解决：每个数字记成 $a+\sqrt{5}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 ha = 998244353;
const int inv = 499122177;

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;
}

struct Node{// x+sqrt(5)y
    int x,y;
    Node(int x=0,int y=0) : x(x),y(y) {}
    
    inline Node operator + (const Node &t) const {
        return Node((x+t.x)%ha,(y+t.y)%ha);
    }
    
    inline Node operator - (const Node &t) const {
        return Node((x+ha-t.x)%ha,(y+ha-t.y)%ha);
    }
    
    inline Node operator * (const Node &t) const {
        return Node((1ll*x*t.x%ha+5ll*y%ha*t.y%ha)%ha,(1ll*x*t.y%ha+1ll*y*t.x%ha)%ha);
    }
    
    inline Node inv(){
        int inv = (1ll*x*x%ha+ha-5ll*y%ha*y%ha)%ha;
        inv = qpow(inv);
        return Node(1ll*x*inv%ha,ha-1ll*y*inv%ha);
    }
}a,b;

inline Node qpow(Node a,LL n){
    Node res(1,0);
    while(n){
        if(n & 1) res = res*a;
        a = a*a;
        n >>= 1;
    }
    return res;
}

int main(){
    LL n;scanf("%lld",&n);++n;
    a = Node(inv,inv);b = Node(inv,ha-inv);
    a = qpow(a,n);b = qpow(b,n);
    a = a-b;
    Node c(0,1);
    a = a*c.inv();
    printf("%d\n",a.x);
    return 0;
}

B

假如说我们已经确定了走哪些点（一个连通块），我们对于连通块的边只能选择一条从 $1$ 开始的路径每条边贡献 $1$，其余贡献 $2$。于是求出来距离点 $1$ 深度最大值 $d$，如果 $m \leq d$ 答案就是 $m$，否则是 $d+\frac{m-d}{2}$ 。注意和 $n$ 取 $\min$。

#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 = 1e5 +5;
int n,m;
struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int dep[MAXN],mx;

inline void dfs(int v,int fa=0){
    mx = std::max(mx,dep[v]);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dep[e[i].to] = dep[v]+1;dfs(e[i].to,v);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    dfs(1);
    printf("%d\n",m <= mx ? m+1 : std::min(n,mx+((m-mx)>>1)+1));
    return 0;
}

C

先转化为对每一种颜色计算有这种颜色的路径条数，容斥后变成计算不经过这种颜色的方案数。

虽然这里可以通过虚树解决了但是不太好。

不经过某种颜色的意思就是把这些颜色的点删掉，求每个连通块大小 $\binom {sz}{2}$ 之类的东西。先考虑不包含根的连通块：我们在连通块的最上面的点的父亲统计答案（一定是这个颜色），所以我们现在转变成了对于每个点，求子树内没有和这个点一样颜色的极大连通块大小。其实就是要对于每个子树求出这个子树的所有最上面的这个颜色的点的子树大小和。一种可行的方法是使用链分治技巧：开个桶记录当前每种颜色在这个子树里所有最上面的点的子树大小和，轻重链剖分后首先递归处理轻儿子并每次清空桶，然后递归重儿子不清空桶，再扫一遍轻儿子将桶加上。这样复杂度是 $O(n \log n)$ 的；但是我们可以考虑使用差分：我们桶记录所有访问过的点的信息；在访问这个点子树前先记录下对应需要的值，dfs 处理完所有子树后再通过做差就可以求出这个子树的信息了。这个技巧在这个比赛的 C 题也有运用（然而我都不会）：
然后我们要计算跨过根的连通块大小。不难发现我们做完 dfs 后桶里的值就是所有颜色为 $i$ 为根的最上面的颜色大小，只需要用 $n-t_i$ 就可以算出包含根的没有颜色 $i$ 的连通块大小了。

#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 = 2e5 + 5;
int n,a[MAXN];

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

LL ans = 0;
int t[MAXN],sz[MAXN];

inline void dfs(int v,int fa=0){
    int gx = 0;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        int las = t[a[v]];
        dfs(e[i].to,v);sz[v] += sz[e[i].to];
        las = t[a[v]]-las;
        las = sz[e[i].to]-las;
        ans += 1ll*las*(las-1)/2;
        gx += las;
    }
    t[a[v]] += gx+1;
}

bool vis[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),vis[a[i]] = 1;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    dfs(1);
    // DEBUG(ans);
    int cnt = 0;
    // ans = -ans;
    FOR(i,1,n) if(vis[i]) ans += 1ll*(n-t[i])*(n-t[i]-1)/2,++cnt;
    printf("%lld\n",1ll*n*(n-1)*cnt/2-ans);
    return 0;
}

D

这种区间安排题目的 dp 状态我还没做过。。

放置区间的 dp 可以考虑设 $f_{i,j,k}$ 表示考虑了前 $i$ 个位置，已经放了 $j$ 个区间，当前有 $k$ 个区间还没有结尾，转移的时候枚举这一次有多少个区间结尾 $a$，多少个区间开头 $b$，转移 $\binom{k}{a} \binom{m-j}{b}f_{i,j,k} \to f_{i,j+b,j+b-a}$。

这样复杂度是 $O(n^5)$ 的，太慢了。

对于这种 dp 同时枚举多个物品的，我们可以拆开枚举：我们先去枚举有多少个结尾转移一下，再去枚举多少个开头转移一下。这样复杂度就是 $O(n^4)$。

#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 = 100+5;
const int ha = 998244353;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}
int f[2][MAXN][MAXN],now;
int fac[MAXN],inv[MAXN];
// 考虑前i个位置,已经使用了j个线段,当前还没结尾的有k个

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;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    prework();
    int n,m,t;scanf("%d%d%d",&n,&m,&t);
    f[now=0][0][0] = 1;
    FOR(i,1,n){
        CLR(f[now^1],0);
        FOR(j,0,m){// 用了几个线段
            FOR(k,0,std::min(j,t)){ // 现在有几个线段
                if(!f[now][j][k]) continue;
                FOR(a,0,m-j){
                    add(f[now^1][j+a][k+a],1ll*f[now][j][k]*C(m-j,a)%ha);
                }
                // FOR(a,0,m-j){// 开头几个
                    // FOR(b,0,k){// 结尾几个
                        // add(f[now^1][j+a][k-b+a],1ll*f[now][j][k]*C(m-j,a)%ha*C(k,b)%ha);
                    // }
                // }可以分两步转移!
            }
        }
        now ^= 1;
        CLR(f[now^1],0);
        FOR(j,0,m){
            FOR(k,0,std::min(j,t)){
                if(!f[now][j][k]) continue;
                FOR(b,0,k){
                    add(f[now^1][j][k-b],1ll*f[now][j][k]*C(k,b)%ha);
                }
            }
        }
        now ^= 1;
    }
    printf("%d\n",f[now][m][0]);
    return 0;
}

Last modification：September 14th, 2020 at 10:09 am

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

ZR2020 普及五连测 day1

RainAir • 2020 年 09 月 14 日

A

#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 ha = 998244353;
const int inv = 499122177;

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;
}

struct Node{// x+sqrt(5)y
    int x,y;
    Node(int x=0,int y=0) : x(x),y(y) {}
    
    inline Node operator + (const Node &t) const {
        return Node((x+t.x)%ha,(y+t.y)%ha);
    }
    
    inline Node operator - (const Node &t) const {
        return Node((x+ha-t.x)%ha,(y+ha-t.y)%ha);
    }
    
    inline Node operator * (const Node &t) const {
        return Node((1ll*x*t.x%ha+5ll*y%ha*t.y%ha)%ha,(1ll*x*t.y%ha+1ll*y*t.x%ha)%ha);
    }
    
    inline Node inv(){
        int inv = (1ll*x*x%ha+ha-5ll*y%ha*y%ha)%ha;
        inv = qpow(inv);
        return Node(1ll*x*inv%ha,ha-1ll*y*inv%ha);
    }
}a,b;

inline Node qpow(Node a,LL n){
    Node res(1,0);
    while(n){
        if(n & 1) res = res*a;
        a = a*a;
        n >>= 1;
    }
    return res;
}

int main(){
    LL n;scanf("%lld",&n);++n;
    a = Node(inv,inv);b = Node(inv,ha-inv);
    a = qpow(a,n);b = qpow(b,n);
    a = a-b;
    Node c(0,1);
    a = a*c.inv();
    printf("%d\n",a.x);
    return 0;
}

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 = 1e5 +5;
int n,m;
struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int dep[MAXN],mx;

inline void dfs(int v,int fa=0){
    mx = std::max(mx,dep[v]);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dep[e[i].to] = dep[v]+1;dfs(e[i].to,v);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    dfs(1);
    printf("%d\n",m <= mx ? m+1 : std::min(n,mx+((m-mx)>>1)+1));
    return 0;
}

C

先转化为对每一种颜色计算有这种颜色的路径条数，容斥后变成计算不经过这种颜色的方案数。

虽然这里可以通过虚树解决了但是不太好。

#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 = 2e5 + 5;
int n,a[MAXN];

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

LL ans = 0;
int t[MAXN],sz[MAXN];

inline void dfs(int v,int fa=0){
    int gx = 0;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        int las = t[a[v]];
        dfs(e[i].to,v);sz[v] += sz[e[i].to];
        las = t[a[v]]-las;
        las = sz[e[i].to]-las;
        ans += 1ll*las*(las-1)/2;
        gx += las;
    }
    t[a[v]] += gx+1;
}

bool vis[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),vis[a[i]] = 1;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    dfs(1);
    // DEBUG(ans);
    int cnt = 0;
    // ans = -ans;
    FOR(i,1,n) if(vis[i]) ans += 1ll*(n-t[i])*(n-t[i]-1)/2,++cnt;
    printf("%lld\n",1ll*n*(n-1)*cnt/2-ans);
    return 0;
}

D

这种区间安排题目的 dp 状态我还没做过。。

这样复杂度是 $O(n^5)$ 的，太慢了。

对于这种 dp 同时枚举多个物品的，我们可以拆开枚举：我们先去枚举有多少个结尾转移一下，再去枚举多少个开头转移一下。这样复杂度就是 $O(n^4)$。

#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 = 100+5;
const int ha = 998244353;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}
int f[2][MAXN][MAXN],now;
int fac[MAXN],inv[MAXN];
// 考虑前i个位置,已经使用了j个线段,当前还没结尾的有k个

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;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    prework();
    int n,m,t;scanf("%d%d%d",&n,&m,&t);
    f[now=0][0][0] = 1;
    FOR(i,1,n){
        CLR(f[now^1],0);
        FOR(j,0,m){// 用了几个线段
            FOR(k,0,std::min(j,t)){ // 现在有几个线段
                if(!f[now][j][k]) continue;
                FOR(a,0,m-j){
                    add(f[now^1][j+a][k+a],1ll*f[now][j][k]*C(m-j,a)%ha);
                }
                // FOR(a,0,m-j){// 开头几个
                    // FOR(b,0,k){// 结尾几个
                        // add(f[now^1][j+a][k-b+a],1ll*f[now][j][k]*C(m-j,a)%ha*C(k,b)%ha);
                    // }
                // }可以分两步转移!
            }
        }
        now ^= 1;
        CLR(f[now^1],0);
        FOR(j,0,m){
            FOR(k,0,std::min(j,t)){
                if(!f[now][j][k]) continue;
                FOR(b,0,k){
                    add(f[now^1][j][k-b],1ll*f[now][j][k]*C(k,b)%ha);
                }
            }
        }
        now ^= 1;
    }
    printf("%d\n",f[now][m][0]);
    return 0;
}

ZR2020 普及五连测 day1

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

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

CSP2019 游记

CF 1407 题解

单次询问的最长瓶颈路

「BZOJ 4788」[CERC2016]Bipartite Blanket

2020.09.26【NOIP提高组】模拟

此内容被密码保护

ZR2020 普及五连测 day1

A

B

C

D