月度归档:2017年09月

BZOJ 2152: 聪聪可可(点分治)

Description

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢。聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第1行包含1个正整数n。后面n-1行,每行3个整数x、y、w,表示x号点和y号点之间有一条边,上面的数是w。

Output

以即约分数形式输出这个概率(即“a/b”的形式,其中a和b必须互质。如果概率为1,输出“1/1”)。

Sample Input

5
1 2 1
1 3 2
1 4 1
2 5 3

Sample Output

13/25
【样例说明】
13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。

【数据规模】
对于100%的数据,n<=20000。

题目给的路径的定义非常良心,(1,2)和(2,1)视为两条路径。单点也视为一条路径。
点分治一下,每次分治的时候统计出来所有点到当前重心的距离膜3为1,2,0的路径条数。这个一遍dfs就可以了。。。
最后这一层的答案就是选择depth[1]这个集合中的一条边和depth[2]这个集合的一条边组合起来,以及从集合depth[0]这个集合中选两条边的和。注意这么做还是会有算错的答案,所以还是要扫一遍根的儿子们进行处理。

 

hihocoder 1424 Asa’s Chess Problem(带上下界的最小费用可行流)

题目链接

发现貌似没白点的什么事。。。

那么我们可以把行和列视为2*n个初始点,从超级源向这些点连上下界均为初始黑点的流量,费用为0的边。因为这么多流量是一定流入这个点的。然后把pair视为边,因为我们只考虑黑点的转换,而且他们只在同一行或者同一列,所以当两个点在同一行,A点原来为黑色,所以我们就从A的初始点连向B的最终点一条流量为1费用为1的边。最终点向汇点连接带题目给的上下界的边。然后跑个上下界费用流。

记得要检查非法。。。

 

hihocoder 1432 JiLi Number(打表)

题目链接

一开始觉得这样的数很少,然后打了个表发现应该只有83个了,然后打了个大一点的范围发现真的是这样。。。因为1的增长应该大于了数的增长了。。。但是感觉这样的题就很无语了。。。