ZR 2020普转提七连测day2

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

A

根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_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 ha = 998244353;
const int MAXN = 1e7 + 5;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

int n;
int f[MAXN],sz[MAXN];
int inv[MAXN];

int main(){
    read(n);
    FOR(i,2,n) read(f[i]);
    ROF(i,n,2){
        sz[i]++;
        sz[f[i]] += sz[i];
    }
    sz[1]++;
    inv[1] = 1;
    FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    int ans = 0;
    FOR(i,1,n) (ans += inv[sz[i]]) %= ha;
//    ans = 1ll*ans*n%ha;
    printf("%d\n",ans);
    return 0;
}

B

这个题目挺难的。

我们注意 $\frac{n}{2}+1$，可以联想到是两两配对然后多输出一个。

于是按照第一维排序，考虑先选择第一个，然后从第二个和第三个中选择 $b$ 最大的，第四个和第五个中选择 $b$ 最大的，以此类推。。。可以证明答案一定是满足的：因为我们这个条件实际上是要求选出的大于没选出的，对于 $b$ 显然满足条件（每次选出的都是最大的），考虑 $a$ 的话我们假设最坏情况每次都选一个最小的，也会有 $a_1 \geq \max(a_2,a_3)$ ，$\min(a_2,a_3) \geq \max(a_4,a_5) \ldots$，选出来的和大于不选的和。所以就是合法的。

#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;
struct Node{
    int a,b,id;
    bool operator < (const Node &t) const {
        return a > t.a;
    }
}a[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i].a);
    FOR(i,1,n) scanf("%d",&a[i].b),a[i].id = i;
    std::sort(a+1,a+n+1);
    printf("%d\n",n/2+1);
    printf("%d",a[1].id);
    for(int i = 2;i <= n;i += 2){
        printf(" %d",std::max(MP(a[i].b,a[i].id),MP(a[i+1].b,a[i+1].id)).se);
    }
    puts("");
    return 0;
}

其实这个题暴力随机化也是能过的并且不会卡。。

C

我们考虑如果确定了答案 $k$，设一个点子树内选择的黑点个数为 $a_i$，最紧的 A 类限制是 $y1_v$，最紧的 B 类限制是 $y2_v$。有以下限制

$$ \begin{aligned} \sum_{y \in son_x}a_y \leq a_x &\leq 1+\sum_{y \in son_x}a_y\\ a_x &\geq y1_x\\ a_x &\leq k-y2_x\\ \end{aligned} $$

发现 $k$ 越大，答案越松，所以我们可以二分 $k$ 算出每个点的可行区间判断即可。

注意这里一定要判断 $l_1 \leq k \leq r_1$！自己还是有些细节想不好。

#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
#define int LL
const int MAXN = 1e5 + 5;

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

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 n;
int _y1[MAXN],_y2[MAXN];
int l[MAXN],r[MAXN],sz[MAXN];
int K;
bool flag;

inline void dfs(int v,int fa=0){
    l[v] = 0;r[v] = 1;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);sz[v] += sz[e[i].to];
        l[v] += l[e[i].to];r[v] += r[e[i].to];
    }
//    r[v]++;
    l[v] = std::max(l[v],_y1[v]);
    r[v] = std::min(r[v],sz[v]);
    r[v] = std::min(r[v],K-_y2[v]);
    flag &= l[v]<=r[v];
}

inline bool chk(int k){
    K = k;flag = 1;dfs(1);
    flag &= (l[1] <= k && k <= r[1]);
    return flag;
}

signed main(){
    scanf("%lld",&n);
    FOR(i,2,n){
        int u,v;scanf("%lld%lld",&u,&v);add(u,v);
    }
    int A;scanf("%lld",&A);
    FOR(i,1,A){
        int x,y;scanf("%lld%lld",&x,&y);
        _y1[x] = std::max(_y1[x],y);
    }
    int B;scanf("%lld",&B);
    FOR(i,1,B){
        int x,y;scanf("%lld%lld",&x,&y);
        _y2[x] = std::max(_y2[x],y);
    }
    int l = 0,r = n,ans = -1;
//    DEBUG(chk(2));
//    exit(0);
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

D

dp 状态完全想不到啊Orz...

首先我们如果有了状态如何判断？我们如果想判断 Alice 能走到的所有点肯定是允许走 Alice 的点所有的边和 Bob 指定的边。

如果我们去枚举一条重链，设这个叶子的值是 $(u,v)$，那么 Alice 和 Bob 就独立了：Alice 只需要保证这条链上她的点对应的另一棵子树满足答案怎么走都 $\leq u$，Bob 同理；

所以我们首先要预处理出 $g1_{v,i}$ 和 $g2_{v,i}$ 分别表示 $v$ 子树要求 Alice/Bob 的得分 $\leq i$ 的方案数（这里方案数指重链选择方案数和叶子权值方案数）。

转移我们只考虑 Alice（Bob转移是类似的），设 $v$ 的两个子树为 $lc,rc$ ，如果 Alice 在 Alice 点上：她需要保证这个点两个子树答案都是 $\leq i$，所以 $g1_{v,i} = 2\times g1_{lc,i} \times g1_{rc,i}$；如果 Alice 在 Bob 点上：她只能走 Bob 选择的一条边，另一个子树就可以瞎选了。预处理某个子树乱选的方案数 $c_i$，就有 $g1_{v,i} = g1_{lc,i} \times c_{rc} + g1_{rc,i} \times c_{lc}$.

然后我们现在在某个叶子上想知道 $f1_{v,i},f2_{v,i}$ 表示 Alice/Bob 从 $1 \to v$ 走过的所有自己的点对应的另一棵子树都 $\leq 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 ha = 998244353;
const int MAXN = 5000+5;

std::vector<int> G[MAXN];
int n,k;

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

int g1[MAXN][MAXN],g2[MAXN][MAXN],bin[MAXN];
// g:子树v,<=i得分的方案数 1:Alice ,2:Bob

inline void dfs1(int v,int t){
    if(G[v].empty()){
        FOR(i,1,k) g1[v][i] = g2[v][i] = 1ll*i*k%ha;
        bin[v] = 1ll*k*k%ha;
        return;
    }
    int lc = G[v][0],rc = G[v][1];
    dfs1(lc,t^1);dfs1(rc,t^1);
    bin[v] = 2ll*bin[lc]%ha*bin[rc]%ha;
    if(!t){ // Alice
        FOR(i,1,k){
            g1[v][i] = 2ll*g1[lc][i]%ha*g1[rc][i]%ha;// 左右两边都可以走,所以两边都要满足限制 边随便选
            g2[v][i] = (1ll*g2[lc][i]*bin[rc]%ha+1ll*g2[rc][i]*bin[lc]%ha)%ha; // Bob必须走Alice指定的边，另一个子树就没用了
        }
    }
    else{
        FOR(i,1,k){
            g1[v][i] = (1ll*g1[lc][i]*bin[rc]%ha+1ll*g1[rc][i]*bin[lc]%ha)%ha;
            g2[v][i] = 2ll*g2[lc][i]%ha*g2[rc][i]%ha;
        }
    }
}

int f1[MAXN][MAXN],f2[MAXN][MAXN];
// 走到v点,答案<=i
int ans;

inline void dfs2(int v,int t){
    if(G[v].empty()){
        int sm1=0,sm2=0;
        FOR(i,1,k) add(sm1,f1[v][i]),add(sm2,f2[v][i]);
        add(ans,1ll*sm1*sm2%ha);
        return;
    }
    int ls = G[v][0],rs = G[v][1];
    if(!t){
        FOR(i,1,k){
            f1[ls][i] = 1ll*f1[v][i]*g1[rs][i]%ha;
            f1[rs][i] = 1ll*f1[v][i]*g1[ls][i]%ha;
            f2[ls][i] = f2[v][i];
            f2[rs][i] = f2[v][i];
        }
    }
    else{
        FOR(i,1,k){
            f1[ls][i] = f1[v][i];
            f1[rs][i] = f1[v][i];
            f2[ls][i] = 1ll*f2[v][i]*g2[rs][i]%ha;
            f2[rs][i] = 1ll*f2[v][i]*g2[ls][i]%ha;
        }
    }
    dfs2(ls,t^1);dfs2(rs,t^1);
}

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,2,n){
        int f;scanf("%d",&f);G[f].pb(i);
    }
    dfs1(1,0);
    FOR(i,1,k) f1[1][i] = f2[1][i] = 1;
    dfs2(1,0);
    printf("%d\n",ans);
    return 0;
}

Last modification：September 14th, 2020 at 08:14 am

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

ZR 2020普转提七连测day2

RainAir • 2020 年 09 月 14 日

A

根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_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 ha = 998244353;
const int MAXN = 1e7 + 5;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

int n;
int f[MAXN],sz[MAXN];
int inv[MAXN];

int main(){
    read(n);
    FOR(i,2,n) read(f[i]);
    ROF(i,n,2){
        sz[i]++;
        sz[f[i]] += sz[i];
    }
    sz[1]++;
    inv[1] = 1;
    FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    int ans = 0;
    FOR(i,1,n) (ans += inv[sz[i]]) %= ha;
//    ans = 1ll*ans*n%ha;
    printf("%d\n",ans);
    return 0;
}

B

这个题目挺难的。

我们注意 $\frac{n}{2}+1$，可以联想到是两两配对然后多输出一个。

#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;
struct Node{
    int a,b,id;
    bool operator < (const Node &t) const {
        return a > t.a;
    }
}a[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i].a);
    FOR(i,1,n) scanf("%d",&a[i].b),a[i].id = i;
    std::sort(a+1,a+n+1);
    printf("%d\n",n/2+1);
    printf("%d",a[1].id);
    for(int i = 2;i <= n;i += 2){
        printf(" %d",std::max(MP(a[i].b,a[i].id),MP(a[i+1].b,a[i+1].id)).se);
    }
    puts("");
    return 0;
}

其实这个题暴力随机化也是能过的并且不会卡。。

C

我们考虑如果确定了答案 $k$，设一个点子树内选择的黑点个数为 $a_i$，最紧的 A 类限制是 $y1_v$，最紧的 B 类限制是 $y2_v$。有以下限制

$$ \begin{aligned} \sum_{y \in son_x}a_y \leq a_x &\leq 1+\sum_{y \in son_x}a_y\\ a_x &\geq y1_x\\ a_x &\leq k-y2_x\\ \end{aligned} $$

发现 $k$ 越大，答案越松，所以我们可以二分 $k$ 算出每个点的可行区间判断即可。

注意这里一定要判断 $l_1 \leq k \leq r_1$！自己还是有些细节想不好。

#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
#define int LL
const int MAXN = 1e5 + 5;

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

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 n;
int _y1[MAXN],_y2[MAXN];
int l[MAXN],r[MAXN],sz[MAXN];
int K;
bool flag;

inline void dfs(int v,int fa=0){
    l[v] = 0;r[v] = 1;sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);sz[v] += sz[e[i].to];
        l[v] += l[e[i].to];r[v] += r[e[i].to];
    }
//    r[v]++;
    l[v] = std::max(l[v],_y1[v]);
    r[v] = std::min(r[v],sz[v]);
    r[v] = std::min(r[v],K-_y2[v]);
    flag &= l[v]<=r[v];
}

inline bool chk(int k){
    K = k;flag = 1;dfs(1);
    flag &= (l[1] <= k && k <= r[1]);
    return flag;
}

signed main(){
    scanf("%lld",&n);
    FOR(i,2,n){
        int u,v;scanf("%lld%lld",&u,&v);add(u,v);
    }
    int A;scanf("%lld",&A);
    FOR(i,1,A){
        int x,y;scanf("%lld%lld",&x,&y);
        _y1[x] = std::max(_y1[x],y);
    }
    int B;scanf("%lld",&B);
    FOR(i,1,B){
        int x,y;scanf("%lld%lld",&x,&y);
        _y2[x] = std::max(_y2[x],y);
    }
    int l = 0,r = n,ans = -1;
//    DEBUG(chk(2));
//    exit(0);
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

D

dp 状态完全想不到啊Orz...

首先我们如果有了状态如何判断？我们如果想判断 Alice 能走到的所有点肯定是允许走 Alice 的点所有的边和 Bob 指定的边。

然后我们现在在某个叶子上想知道 $f1_{v,i},f2_{v,i}$ 表示 Alice/Bob 从 $1 \to v$ 走过的所有自己的点对应的另一棵子树都 $\leq 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 ha = 998244353;
const int MAXN = 5000+5;

std::vector<int> G[MAXN];
int n,k;

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

int g1[MAXN][MAXN],g2[MAXN][MAXN],bin[MAXN];
// g:子树v,<=i得分的方案数 1:Alice ,2:Bob

inline void dfs1(int v,int t){
    if(G[v].empty()){
        FOR(i,1,k) g1[v][i] = g2[v][i] = 1ll*i*k%ha;
        bin[v] = 1ll*k*k%ha;
        return;
    }
    int lc = G[v][0],rc = G[v][1];
    dfs1(lc,t^1);dfs1(rc,t^1);
    bin[v] = 2ll*bin[lc]%ha*bin[rc]%ha;
    if(!t){ // Alice
        FOR(i,1,k){
            g1[v][i] = 2ll*g1[lc][i]%ha*g1[rc][i]%ha;// 左右两边都可以走,所以两边都要满足限制 边随便选
            g2[v][i] = (1ll*g2[lc][i]*bin[rc]%ha+1ll*g2[rc][i]*bin[lc]%ha)%ha; // Bob必须走Alice指定的边，另一个子树就没用了
        }
    }
    else{
        FOR(i,1,k){
            g1[v][i] = (1ll*g1[lc][i]*bin[rc]%ha+1ll*g1[rc][i]*bin[lc]%ha)%ha;
            g2[v][i] = 2ll*g2[lc][i]%ha*g2[rc][i]%ha;
        }
    }
}

int f1[MAXN][MAXN],f2[MAXN][MAXN];
// 走到v点,答案<=i
int ans;

inline void dfs2(int v,int t){
    if(G[v].empty()){
        int sm1=0,sm2=0;
        FOR(i,1,k) add(sm1,f1[v][i]),add(sm2,f2[v][i]);
        add(ans,1ll*sm1*sm2%ha);
        return;
    }
    int ls = G[v][0],rs = G[v][1];
    if(!t){
        FOR(i,1,k){
            f1[ls][i] = 1ll*f1[v][i]*g1[rs][i]%ha;
            f1[rs][i] = 1ll*f1[v][i]*g1[ls][i]%ha;
            f2[ls][i] = f2[v][i];
            f2[rs][i] = f2[v][i];
        }
    }
    else{
        FOR(i,1,k){
            f1[ls][i] = f1[v][i];
            f1[rs][i] = f1[v][i];
            f2[ls][i] = 1ll*f2[v][i]*g2[rs][i]%ha;
            f2[rs][i] = 1ll*f2[v][i]*g2[ls][i]%ha;
        }
    }
    dfs2(ls,t^1);dfs2(rs,t^1);
}

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,2,n){
        int f;scanf("%d",&f);G[f].pb(i);
    }
    dfs1(1,0);
    FOR(i,1,k) f1[1][i] = f2[1][i] = 1;
    dfs2(1,0);
    printf("%d\n",ans);
    return 0;
}

ZR 2020普转提七连测day2

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

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

CSP2019 游记

强连通分量

「ZJOI2018」历史

「CF414E」Mashmokh's Designed Problem

无向图生成树计数

2018 EC Final B Mysterious … Host

ZR 2020普转提七连测day2

A

B

C

D