2016.2.17测试总结

-------------------------------------------------------------------------------
 
先说下题意:
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位是否退位,下一位是否限制(大概是这样)
然后..然后我还没想清楚..
-------------------------------------------------------------------------------