Codeforces #329 div2

代码:

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/Codeforces/%23329(Div%202)

A 2Char

题意:

给你一堆单词,然你选一些出来,使得选出来的最多含有两种不同的字母,并且要让总长最长

题解:

直接暴力选出来的字母是什么,然后统计答案就好。

B Anton and Lines

题意:

给你一堆直线,问你在$(L,R)$这个区间是否有交点。

题解:

这是一个经典的逆序对问题,可以参考我以前的做法:
http://harryguo.me/2015/11/03/ZOJ_3157-Weapon/
不过这道题很简单,不用统计有几个交点,所以就不用维护树状数组了,排个序就能知道答案。

D Happy Tree Party

题意:

给你一棵树,树的每条边上都有个权值。现在有一个操作是改变某条边的权值,有种询问是从节点a到节点b的所有的边权,依次除y,结果是什么。

题解:

要做这道题,首先你要明白,$ y/a/b/c=y/(abc) $,接下来就很简单了,就是个树链剖分的问题。不过这道题是个非常恶心的题目,其数据范围一不小心就会爆long long,所以应当使用对数来特判乘积。