2019 计蒜之道 初赛 第一场
题解：
疑似贪心；
1 vector<int >out[maxn];///out[x]:存x指出去的点 2 int in[maxn];///in[x]:x的入度
需要删除的骨牌满足的条件为：
[1]:出度最大；
[2]:出度相同判断有无入度；
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mem(a,b) memset(a,b,sizeof(a)) 4 #define ll long long 5 const int maxn=5e3+50; 6 7 int n; 8 vector<int >out[maxn]; 9 int in[maxn]; 10 bool vis[maxn]; 11 12 void Update() 13 { 14 int t=0; 15 for(int i=1;i <= n;++i) 16 { 17 if(vis[i] || out[i].size() < out[t].size()) 18 continue; 19 20 if(t == 0) 21 t=i; 22 if(out[i].size() > out[t].size() || in[i] > 0) 23 t=i; 24 } 25 for(int i=0;i < out[t].size();++i) 26 in[out[t][i]]--; 27 vis[t]=true; 28 } 29 int Solve() 30 { 31 mem(vis,false); 32 if(n <= 2) 33 return 0; 34 Update(); 35 Update(); 36 37 int ans=0; 38 for(int i=1;i <= n;++i) 39 if(!vis[i] && in[i] == 0) 40 ans++; 41 return ans; 42 } 43 int main() 44 { 45 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 46 scanf("%d",&n); 47 for(int i=1;i < n;++i) 48 { 49 int x,y; 50 scanf("%d%d",&x,&y); 51 out[x].push_back(y); 52 in[y]++; 53 } 54 printf("%d\n",Solve()); 55 56 return 0; 57 }
题意：
由 n(n ≤ 50) 个节点 n-1 条边 E 构成的带权树；
对于每个节点 i，你可以给节点 i 赋值为 ai=x(x ≤ m)；
求共有多少种赋值方式满足任意 (u,v) ∈ E,GCD(au,av) ≠ w[u][v]；
题解：
以①为根节点建树；
如下定义：
1 int w[maxn][maxn];///w[i][j]:节点i与节点j的权值 2 int fa[maxn];///fa[i]:节点i的父节点 3 int dp[maxn][maxn];///dp[i][j]:节点i取j所包含的总方案数
dp初始化为0；
由叶节点向上更新dp：
1 bool isSat(int u,int a) 2 { 3 /** 4 节点u可以取a当且仅当与节点u相连的所有节点v（包括其父节点） 5 满足存在b∈[1,m]使得GCD(a,b)≠w[u][v] 6 */ 7 for(int i=head[u];~i;i=G[i].next) 8 { 9 int v=G[i].to; 10 11 bool ok=false; 12 for(int b=1;b <= m;++b) 13 if(GCD(a,b) != w[u][v]) 14 ok=true; 15 16 if(!ok) 17 return false; 18 } 19 return true; 20 } 21 void F(int u,int a)///更新叶节点的dp 22 { 23 bool ok=false;///判断节点u是否为叶节点 24 for(int i=head[u];~i;i=G[i].next) 25 if(G[i].to != fa[u]) 26 ok=true; 27 if(!ok) 28 { 29 for(int b=1;b <= m;++b) 30 if(GCD(a,b) != w[fa[u]][u]) 31 dp[u][b]=1; 32 } 33 } 34 void DFS(int u) 35 { 36 for(int i=head[u];~i;i=G[i].next) 37 { 38 int v=G[i].to; 39 if(v == fa[u]) 40 continue; 41 DFS(v); 42 } 43 ///从叶节点向上更新dp 44 if(vis[u] || u == 1) 45 return ; 46 47 int v=fa[u]; 48 for(int a=1;a <= m;++a)///父节点v取a 49 { 50 if(!isSat(v,a))///判断v节点是否可以取a 51 continue; 52 53 for(int i=head[v];~i;i=G[i].next) 54 { 55 int to=G[i].to; 56 if(to == fa[v]) 57 continue; 58 59 vis[to]=true; 60 F(to,a);///如果to为叶节点，单独更新叶节点的dp； 61 62 for(int b=1;b <= m;++b)///儿子节点to取b 63 if(GCD(a,b) != w[v][to])///更新节点v的dp 64 dp[v][a]=(dp[v][a]+dp[to][b])%mod; 65 } 66 } 67 }
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define GCD(a,b) __gcd(a,b) 4 #define mem(a,b) memset(a,b,sizeof(a)) 5 #define memF(a,b,n) for(int i=0;i <= n;a[i]=b,++i); 6 #define ll long long 7 const int mod=1e9+7; 8 const int maxn=100; 9 10 int n,m; 11 int num; 12 int head[maxn]; 13 int w[maxn][maxn]; 14 struct Edge 15 { 16 int to; 17 int next; 18 }G[maxn<<1]; 19 void addEdge(int u,int v) 20 { 21 G[num]=Edge{v,head[u]}; 22 head[u]=num++; 23 } 24 int fa[maxn];///fa[i]:节点i的父节点 25 int dp[maxn][maxn];///dp[i][j]:节点i取j所包含的总方案数 26 bool vis[maxn]; 27 bool isSat(int u,int a) 28 { 29 /** 30 节点u可以取a当且仅当与节点u相连的所有节点v（包括其父节点） 31 满足存在b∈[1,m]使得GCD(a,b)≠w[u][v] 32 */ 33 for(int i=head[u];~i;i=G[i].next) 34 { 35 int v=G[i].to; 36 37 bool ok=false; 38 for(int b=1;b <= m;++b) 39 if(GCD(a,b) != w[u][v]) 40 ok=true; 41 42 if(!ok) 43 return false; 44 } 45 return true; 46 } 47 void F(int u,int a)///更新叶节点的dp 48 { 49 bool ok=false;///判断节点u是否为叶节点 50 for(int i=head[u];~i;i=G[i].next) 51 if(G[i].to != fa[u]) 52 ok=true; 53 if(!ok) 54 { 55 for(int b=1;b <= m;++b) 56 if(GCD(a,b) != w[fa[u]][u]) 57 dp[u][b]=1; 58 } 59 } 60 void DFS1(int u,int f) 61 { 62 fa[u]=f; 63 for(int i=head[u];~i;i=G[i].next) 64 { 65 int v=G[i].to; 66 if(v == f) 67 continue; 68 DFS1(v,u); 69 } 70 } 71 void DFS(int u) 72 { 73 for(int i=head[u];~i;i=G[i].next) 74 { 75 int v=G[i].to; 76 if(v == fa[u]) 77 continue; 78 DFS(v); 79 } 80 ///从叶节点向上更新dp 81 if(vis[u] || u == 1) 82 return ; 83 84 int v=fa[u]; 85 for(int a=1;a <= m;++a)///父节点v取a 86 { 87 if(!isSat(v,a))///判断v节点是否可以取a 88 continue; 89 90 for(int i=head[v];~i;i=G[i].next) 91 { 92 int to=G[i].to; 93 if(to == fa[v]) 94 continue; 95 96 vis[to]=true; 97 F(to,a);///如果to为叶节点，单独更新叶节点的dp； 98 99 for(int b=1;b <= m;++b)///儿子节点to取b 100 if(GCD(a,b) != w[v][to])///更新节点v的dp 101 dp[v][a]=(dp[v][a]+dp[to][b])%mod; 102 } 103 } 104 } 105 ll Solve() 106 { 107 DFS1(1,1); 108 109 mem(dp,0); 110 memF(vis,false,n); 111 DFS(1); 112 113 ll ans=0;///统计答案 114 for(int i=1;i <= m;++i) 115 ans += dp[1][i]; 116 return ans%mod; 117 } 118 void Init() 119 { 120 num=0; 121 memF(head,-1,n); 122 } 123 int main() 124 { 125 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 126 scanf("%d%d",&n,&m); 127 Init(); 128 for(int i=1;i < n;++i) 129 { 130 int u,v,c; 131 scanf("%d%d%d",&u,&v,&c); 132 addEdge(u,v); 133 addEdge(v,u); 134 w[u][v]=w[v][u]=c; 135 } 136 printf("%lld\n",Solve()); 137 138 return 0; 139 }