夏季赛命题组
A. Simple A + B Problem
使用题述类型,读入两个整数并输出和即可。
B. LCA 的 LCA
考虑任选两点的 LCA 期望时可考虑每个点或以其为根的子树上的其他点为 LCA 的方案总数为以该点为根的子树大小的平方,进行简单容斥可得每个点为 LCA 的方案数。
回答原题时,可进一步的将平方改为四次方,也可以用两个点的 LCA 的方案总数作为权值再计算一遍两个点的 LCA 这个问题的解。
C. 简单计算
将火柴棒字符串转换为 Python 可计算的表达式,调用 eval 后将返回结果按要求转换回火柴棒字符串即可。
D. 简单的 N 皇后
对于每个棋子,在对应行、列(各视为节点)之间建一条边建图。对此图可以求最大流,也可以求二分图最大匹配,计算完成后 N−流量(或匹配数) 即为所求。
E. 取石子游戏
暴力的 DP 无法完成本题,但是可以发现最终答案在两条线附近,拟合这两条直线,在其邻域内暴搜即可。
F. 引爆炸弹
显然所建的图是一个基环森林,树上直接递推即可,环上可先倒推求出一个点的真实概率(由于节点不会被自己在传递后引爆),然后递推即可,注意 A→B 时,已知 B 未引爆对 A 的影响。
G. 破壳梦走
可对每个破壳梦维护三个并查集表示它本身属性集合和克制与被克制集合,合并时三个集合都对应合并,并对应进行检查即可。
也可以在并查集上每个节点加一个值表示到父节点的距离(0,1,2 分别表示相同,克制,被克制),路径压缩时将距离压缩为到根距离之和对 3 取模的结果即可。
H. 参观路线
无向连通偶度图是欧拉回路,即可以一笔画,所以每个点都经过一次,每条边都经过一次。所以答案即为点的愉悦值之和减去点的数量的求和后再减去边的数量的差。