2016.2.17测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------------------------
先说下题意：
T1:三个问：
第一问求大小为n的无根树数量，限制是每个点的度数最多为4
第二问求大小为n的有根树数量，限制是每个点的度数最多为4，根的度数最多为3
第三问求一个有一个大小为m的环且去掉这个环后，每个连通块都一棵大小在1到n之间的树的图的数量
两个树（或图）同构当且仅当他们可以通过重标号以及在三维空间中旋转、对称得到另一个
70分 n<=200
100分n<=2000
T2：
有一棵大小为n的有根树，用1~n给这个树的点标号，要求：
①一个子树的编号排序后连续
②儿子的大小大于父亲的大小
说一个编号方案的价值为每个点的编号乘以这个点的度数之和
两个问：
第一问求这棵树的价值最大的方案的价值
第二问求这棵树前i个生成子树的最大方案的价值（1<=i<=n）
第一问n<=1000000
第二问n<=100000
T3:
给定α，p，A，求有多少个二元组(k,n)满足1<=k<=n<=A且在α进制下n-k作了至少p次进位
30分A<=1000
100分A<=10^1000
-------------------------------------------------------------------------------
T1:
先考虑第二问，设n=n'时第二问答案为f(n')
显然有：
f(n) = ∑((i,j,k),i+j+k=n-1且i<=j<=k)f'(i,j,k)
其中f'(i,j,k) =
{
(C(f(j),3) + C(f(j),2) + C(f(j),1)) (i ＝ j ＝ k)
(C(f(j),2) + C(f(j),1)) * f(k) (i ＝ j ≠ k)
(C(f(j),2) + C(f(j),1)) * f(i) (i ≠ j ＝ k)
f(i)*f(j)*f(k) (i ≠ j ≠ k)
}
(另外,C(a,k)+C(a,k-1)+...+C(a,1)等于C(a+k-1,k))
这样是n^3的过不了，然后考虑背包：
g(i,j)表示有i棵子树，总大小为j的答案，显然有f(i)=g(3,i-1)
然后考虑用f(i)去更新g(j,k):
枚举f(i)选的个数p
有 g(j+p,k+p*i) += g(j,k)*C(f(i)+l-1,l)
(这里要注意：k要倒着枚举，以及j枚举到3就够了)
这就是n^2的了
然后考虑第三问：
令Q=∑（i=1,n)f(i)
于是答案是用Q种颜色给一个M元环染色的本质不同的方案数
考虑polya计数定理:
答案r=(∑(g∈G)Q^m(g))/|G|,其中G是置换集合,m(g)表示g的循环节个数
有两种置换：右移k位、绕某个位置对称对称
对称分奇偶讨论一下，很容易
且显(da)然(biao)有右移k位的循环节个数为gcd(k,n)，这一部分的答案为(∑(i=1,m)Q^gcd(i,n)),这等于(∑(d|m)phi(d)*Q^(m/d))
然后是第一问：
把重心当做根然后跟第一问一样的算就好，然后注意只用i<=n/2的f(i)更新f(n),并且在n=输入的n的时候,根可以有四个儿子
注意n是偶数的时候重心有两个,会算重复,因此减去算重的部分C(f[n/2],2)
-------------------------------------------------------------------------------
T2:
只会第一问...
第一问:
设f(i)表示若i的编号是1，i这棵子树的最大价值
贪心，每次优先给size比较小的子树编号，容易证明正确性...
O(n)
-------------------------------------------------------------------------------
T3:
数位DP
退位α次的意思是化成p进制数后n有α个后缀小于对应位置k的后缀
因此考虑DP
f(i,j,i1,i2,i3)表示低i位，退了j次位,第i位是否退位，第i+1位是否退位,下一位是否限制（大概是这样）
然后..然后我还没想清楚..
-------------------------------------------------------------------------------
评论 (0)
