Day4

GSRgsrgsr · 2023-07-27 21:43:27 · 个人记录

Day4

比赛题题解

T1

一边dfs处理出以i为根的子树点数siz[i],因为不包含自己所以减一，最后扫一遍判断都是否>=n/2即可。

复杂度O(n)。

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=3e5+5;
int siz[N];
vector<int> E[N];
void dfs(int nw,int fa){
    for(int i=0;i<E[nw].size();++i){
        int nxt=E[nw][i];
        if(nxt!=fa){
            dfs(nxt,nw);
            siz[nw]+=siz[nxt];
        }
    }
    siz[nw]++;
}
int main(){
    int n,ans=0,cnt;
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        scanf("%d",&cnt);
        E[cnt].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)if(siz[i]*2>=n+2)ans++;
    printf("%d",ans);
    return 0;
}

T2

一个奇妙的性质：\text{一个点}v\text{选到父亲为}u\text{的概率为}\frac{1}{u}。

感性理解：题目保证了只会向前跳，如果跳不到u就继续跳，显然就成了1~u中选到u的概率，即为\frac{1}{u}。显然相邻两个有病毒的点的概率是相互独立的，乘起来即可。

预处理出1-1e5的逆元，O(k_i)回答一次询问，总复杂度O(n+\sum_{i=1}^{q}k_i )。

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=3e5+5;
const int mod=998244353;
int fac[N],inv[N],a[N];
int qpow(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return ans;
}
int main(){
    int n,q,cnt,sum=1;
    scanf("%d%d",&n,&q);
    fac[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=1;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(int i=n;i>=1;--i)inv[i]=1ll*inv[i]*fac[i-1]%mod; 
    while(q--){
        int m,ans=1,maxx=0;
        scanf("%d",&m);
        for(int i=1;i<=m;++i){
            scanf("%d",&a[i]);
            maxx=max(maxx,a[i]);
        }
        for(int i=1;i<=m;++i)if(a[i]!=maxx)ans=1ll*ans*inv[a[i]]%mod;
        printf("%d\n",ans);
    }
    return 0;
}

T3

考虑如果m=n-1即树的情况。首先如果m为奇数，一定不可能；否则直接dfs,如果当前点可用边数为偶数，就全到i,将连向父亲的边标记为不可用，否则除了连向父亲的都到i,显然这样去调整一定是对的。对于不是树的情况，直接将非树边随便放到其中一个端点上即可。

总复杂度O(n+m)

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=3e5+5;
vector<int> E[N],V[N];
int ans[N];
bool vis1[N],vis2[N];
void dfs(int nw,int id){
    vis1[nw]=true;
    for(int i=0;i<E[nw].size();++i){
        int nxt=E[nw][i];
        if(!vis1[nxt])dfs(nxt,V[nw][i]);
    }
    int sum=0;
    for(int i=0;i<E[nw].size();++i){
        int cnt=V[nw][i];
        if(!vis2[cnt]&&cnt!=id){
            vis2[cnt]=true;
            ans[cnt]=nw;
            sum++;
        }
    }
    if(sum&1){
        vis2[id]=true;
        ans[id]=nw;
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
        V[u].push_back(i);
        V[v].push_back(i);
    }
    if(m&1){
        printf("NO");
        return 0;
    }
    for(int i=1;i<=n;++i)if(!vis1[i])dfs(i,0);
    printf("YES\n");
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}

T4

要用长剖，咕。