「2019计蒜之道」初赛第一场题解 2019-05-27

A. 商汤的AI伴游小精灵

暴力枚举两个点,如果不是祖先-儿子关系,答案为相邻子节点个数和+1;

如果是祖先-儿子关系,答案为相邻子节点个数和+[两个点都不是1]-[两个点相邻]。

我的做法还是复杂了。题解做法:答案就是度数和-[两个点相邻]。

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=5e3+10;
vector<int>e[maxn];
int n,deg[maxn],dep[maxn],fa[maxn],top[maxn],sz[maxn];
IL void dfs(int x){
    sz[x]=1;dep[x]=dep[fa[x]]+1;
    for(int v:e[x])dfs(v),sz[x]+=sz[v];
}
IL void dfs(int x,int c){
    top[x]=c;
    int pos=0;
    for(int v:e[x])if(sz[v]>sz[pos])pos=v;
    if(!pos)return;
    dfs(pos,x);
    for(int v:e[x])if(v!=pos)dfs(v,v);
}
IL int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }return dep[x]>dep[y]?y:x;
}
int main(){
    n=gi();
    rep(i,1,n-1){
        int u=gi(),v=gi();
        deg[u]++;fa[v]=u;
        e[u].pb(v);
    }
    dfs(1);
    int ans=0;
    rep(i,1,n)rep(j,i+1,n){
        int u=i,v=j;
        if(dep[u]>dep[v])swap(u,v);
        if(LCA(u,v)==u){
            if(fa[v]!=u){
                chkmax(ans,deg[v]+(deg[u]+(u!=1)));
            }else{
                chkmax(ans,deg[v]+(deg[u]+(u!=1))-1);
            }
        }else {
            chkmax(ans,deg[u]+deg[v]+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

B. 商汤AI园区的n个路口(简单)

比赛时根本没看到链的条件,虽然也没什么用。不妨令\(f[u][i]\)表示\(u\)的子树中,\(u\)点选了\(i\)的答案。转移就枚举\(u\),枚举\(i\),枚举出边的点\(v\)的权值\(j\)\[ f[u][i]=\prod\sum_{(i,j)\neq w(u,v)}f[v][j] \]

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=55;
int n,m;
vector<pii>e[maxn];
int f[maxn][maxn];
IL void dp(int x,int fr){
    for(auto v:e[x]){
        if(v.fr==fr)continue;
        dp(v.fr,x);
    }
    rep(i,1,m){
        int cur=1;
        for(auto v:e[x]){
            if(v.fr==fr)continue;
      int total=0;
            for(int j=1;j<=m;j++){
                if(__gcd(i,j)!=v.se){
                    total=pls(total,f[v.fr][j]);
                }
            }
            cur=mul(cur,total);
        }
        f[x][i]=pls(f[x][i],cur);
    }
}
int main(){
    n=gi();m=gi();
    rep(i,1,n-1){
        int u=gi(),v=gi(),w=gi();
        e[u].pb(mp(v,w));
        e[v].pb(mp(u,w));
    }
    dp(1,0);
    int ans=0;
    rep(i,1,m)ans=pls(ans,f[1][i]);
    cout<<ans<<endl;
    return 0;
}

C. 商汤AI园区的n个路口(中等)

读题的时候就应该注意到一个性质:所有w不相等。

然后看看上一题的代码。发现枚举的\((i,j)\)必须满足\((i,j)\)不等于\(w(u,v)\)才计入贡献。但是由于\(m\)互不相同,\((i,j)\)等于m的数对的个数并不多,如果固定\(i\),那么对于所有点的\(j\)来说只有\(\sum_{i=1}^{m} \frac{m}{i}\)个。

算一个dp值的和,然后枚举有用的部分计算。复杂度\(O(nm\log m)\)

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=1005;
int n,m;
vector<pii>e[maxn];
int f[maxn][maxn],sum[maxn];
IL void dp(int x,int fr){
    for(auto v:e[x]){
        if(v.fr==fr)continue;
        dp(v.fr,x);
    }
    rep(i,1,m){
        int cur=1;
        for(auto v:e[x]){
            if(v.fr==fr)continue;
            int total=sum[v.fr];
            for(int j=v.se;j<=m;j+=v.se){h
                if(__gcd(i,j)==v.se){
                    total=dec(total,f[v.fr][j]);
                }
            }
            cur=mul(cur,total);
        }
        f[x][i]=pls(f[x][i],cur);
    }
    rep(i,1,m)sum[x]=pls(sum[x],f[x][i]);
}
int main(){
    n=gi();m=gi();
    rep(i,1,n-1){
        int u=gi(),v=gi(),w=gi();
        e[u].pb(mp(v,w));
        e[v].pb(mp(u,w));
    }
    dp(1,0);
    int ans=0;
    rep(i,1,m)ans=pls(ans,f[1][i]);
    cout<<ans<<endl;
    return 0;
}

D. 商汤AI园区的n个路口(困难)

反演。看了半天没看懂。留坑。