pol放了套JSOI day1原题。。
本蒟蒻表示不明觉厉= =
T1 树形dp
看完描述顿时慌了，ZJOI day2的即视感orz。。再看输入格式，woc原来这是一棵su！！那不成水题了么。。
当时正在转C，进度仅30%。。打C没把握，只好默默转回P（转C转了一星期还没转完，仅一秒就转回了P……）。40分钟AC。笑看lyz、cgt两神(S)犇(B)自信写C然后滚粗→_→
题解：
可经过次数就是这个点能连接的子节点个数，所以取最优值大于0的最优的若干个子节点与之相连便可（sort+线扫）。
对于方案是否唯一，会有以下三种情况：
1、某个儿子的方案不唯一。
2、存在一个未选过的儿子，其最优值与某个选过的儿子的最优值相等。
3、有多余的可连边且儿子中有最优值为0的点。
---------------------------------------------------------------
T2 hash
码农题。膜衲姐hash 90分。
表示n^5懒得打。。（毕竟懒癌晚期……）
正解：
预处理出翻转、对称后的6个矩阵并求出hash值，枚举中心+二分，时间复杂度O(n^2logn)。取模可用unsigned int自然溢出，以防卡常。
---------------------------------------------------------------
T3 拓扑+hash
对同构表示不明觉厉。。
正解：
对于每棵su，先dfs去掉所有假节点，然后在新su上求hash值。
叶子节点的值为1，其余点的值为其叶子节点排序后hash出来的值。遍历可按照拓扑序。这样可以保证同构的su的hash值计算顺序相同。
标程见http://yyhslyz.is-programmer.com/posts/189446.html
评论 (0)
