2019 计蒜之道 初赛 第一场 （A-C）

心得

第一次做计蒜之道的比赛，莫名觉得这种比赛的题很难

可能是平时做裸题比较多，稍微变一下就不会了

凡神在旁边，“这个题不是很简单吗”，“你……一下不就好了”

他胡了两句我想了想敲了敲就A了，我大概是个没有脑子只有手的acmer

A.商汤的AI伴游小精灵(树形dp)

题目链接：https://nanti.jisuanke.com/t/39260

如果定义树上边为父->子的有向边，等价于统计两个出度最大的树上点之和

特别地，如果这两个点在树上相邻，答案会-1

所以siz[u]统计的是有多少棵直接子树，siz2[u]统计的是子树里最大的子树

搜一遍，对于u来说v都搜完了，在下面更新u的答案

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
vector<int>E[maxn];
int siz2[maxn],siz[maxn];
int n,x,y,ans;
void dfs(int u,int fa)
{
	for(int i=0;i<E[u].size();++i)
	{
		int v=E[u][i];
		if(v==fa)continue;
		dfs(v,u);
		siz[u]++;
		siz2[u]=max(siz2[u],siz[v]);
	}
	for(int i=0;i<E[u].size();++i)
	{
		int v=E[u][i];
		if(v==fa)continue;
		ans=max(ans,siz[u]+siz[v]-1);
		ans=max(ans,siz[u]+siz2[v]);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1,-1);
	printf("%d\n",ans);
	return 0;
}

B.商汤AI园区的n个路口（简单）（树形dp）

题目链接：https://nanti.jisuanke.com/t/39261

先给一棵树，u和v之间有权值w(w<=m)

给n个点(n<=m)安排1到m(m<=50)的点权，

使得u和v有w的边的前提下，u的点权U和v的点权V满足gcd(U,V)不等于w

dp[i][j]代表到i为根的这棵子树，i节点选j这个树的方案数，自己枚举1到m，子树枚举1到m，O(m^3)

注意到这题读入数据是条链，所以更好转移

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
typedef pair<int,int>P;
vector<P>E[55];
int n,m;
int u,v,w;
ll dp[55][55],ans;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
void dfs(int u,int fa)
{
    if(u==n)
    	for(int j=1;j<=m;++j)
    		dp[u][j]=1;
    for(int i=0;i<E[u].size();++i)
    {
        int v=E[u][i].first;
        int w=E[u][i].second;
        if(v==fa)continue;
        dfs(v,u);
        for(int j=1;j<=m;++j)
        {
            for(int k=1;k<=m;++k)
            {
                if(gcd(j,k)!=w)
                (dp[u][j]+=dp[v][k])%=mod;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        E[u].push_back(P(v,w));
        E[v].push_back(P(u,w));
    }
    dfs(1,-1);
    for(int j=1;j<=m;++j)
        (ans+=dp[1][j])%=mod;
    printf("%lld\n",ans);
    return 0;
}

C.商汤AI园区的n个路口（中等）（树形dp+前缀和）

题目链接：https://nanti.jisuanke.com/t/39262

问题同B题，m<=1e3，题目保证w不同

思路来源

https://www.cnblogs.com/qieqiemin/p/10951856.html

sum[i]为i为根的这棵子树的所有方案数，dp[i][j]同上，

那么，在统计i的子树贡献时，还是去枚举i这个点填什么值

先考虑子树j所有值sum[j]，再去枚举w的倍数，把gcd(i,j)==w的减去，由于w均摊的倍数复杂度O(mlogm)

所以总的复杂度应该是O(m²logm)

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e3+5;
typedef long long ll;
typedef pair<int,int> P;
int n,m,u,v,w;
ll dp[maxn][maxn];
ll sum[maxn];
vector<P>E[maxn];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
void dfs(int u,int fa)
{
	for(int i=0;i<E[u].size();++i)
    {
        int v=E[u][i].first;
        if(v==fa)continue;
        dfs(v,u);
    }
    for(int j=1;j<=m;++j)
    {
        ll num=1;
   	 	for(int i=0;i<E[u].size();++i)
   		{
        	int v=E[u][i].first;
       		int w=E[u][i].second;
       		if(v==fa)continue;
           	ll res=sum[v];
           	//printf("v:%d res:%lld\n",v,res); 
        	for(int p=w;p<=m;p+=w)
            if(gcd(j,p)==w)res=(res-dp[v][p]+mod)%mod;
            (num*=res)%=mod;
		}
        (dp[u][j]+=num)%=mod;
	}
    for(int j=1;j<=m;++j)
    (sum[u]+=dp[u][j])%=mod;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        E[u].push_back(P(v,w));
        E[v].push_back(P(u,w));
    }
    dfs(1,-1);
    printf("%lld\n",sum[1]);
    return 0;
}