Codeforces Round #268

作为tester没什么好说的。
实际上也没做什么贡献。
就是对着题解写代码然后对拍。
不过这场的整体成绩会这样也是没有料到。

sol

div2AB

div1A
容易发现对于n<=3则无解。
n=4的时候有1*2*3*4=24。
n=5的时候有(3+5-2)*4*1=24
然后n>5的话,如果为偶数,那么我们就不停凑n-(n-1)=1,凑出若干个1,再用前4个数拼出24即可。
是奇数也类似。
(解法不唯一)
div1B
容易发现x,a-x,b-x一定在同一个集合里面。并查集维护一下。
div1C
two point扫一扫就能弄出解。
不用高精度。
(解法不唯一)
div1D
把重心当成根,然后保证i和pi的lca是根,就能最大化那个式子。
然后要求最小字典序匹配,根据hall定理要时刻保证每个子树在二分图左边的点数+右边的点数<=还未匹配的点数。
用线段树/set保证这一点即可
div1E
不知道积和式和二分图关系的可以去看wiki。
然后注意到就是一个只连了不超过50条边的二分图。
如果一个联通块的点数很小 然后对小的那一部分进行2^18的状态压缩dp就能计算出这个联通块选x条边匹配的所有方案的权值之和。
否则那么对这个联通块求生成树,生成树的边数一定>=35。。因为联通块大小不超过51。(k+1)
那么我们可以保证非树边的边数不会太多。
暴力2^(51-35)枚举哪些非树边匹配,用树dp算,然后容斥一下,算出这个联通块x条边匹配的所有方案权值之和。
然后再dp合并所有联通块:
dp[i][j]表示前i个联通块中,选了j条边匹配的所有方案权值之和。
加入第i+1个联通块转移的时候。
枚举一下,新增的匹配,有多少条边是第i+1个联通块里的内部匹配,有多少条边是第i+1个联通块连向前i个联通块(权值为1)
然后就能算了。
复杂度看似很高但能接受。

据说还有复杂度靠谱的乱搞做法。

Comments

comments powered by Disqus