弃坑
计数菌:
39/70
省选前做点省选题
【BZOJ1975】A* k短路
【BZOJ2834】虚树DP
【BZOJ3124】为什么我总是在想点分治……dfs就够了……
【BZOJ1879】\(f[i][S]\)表示匹配到i,匹配集合为S的方案数
【BZOJ2282&&1999】显然答案在直径上,算出直径,统计直径上的每个点不过直径上的点的最长链,然后枚举一个端点,另一个端点单调,用平衡树维护当前链上的max
【BZOJ2707】显然DAG可以直接dp,显然点数小的时候可以高斯消元，题目都说了强连通分量小于100所以显然缩点,拓扑序联通分量里Gauss.有点奇怪的是INF的判断是存在一个点s可到达它但它不能到达t,所以对于类似s->t->other的图要输出INF
【BZOJ2726】斜率优化,cdq分治维护凸壳
【BZOJ2285】sd为什么总是一题当两题考= =，很显然答案是最小割，很显然点权要二分+最短路来算
2015年3月20日 13:03
2726满足单调性，所以没必要分治
2015年3月20日 15:57
@sublinekelzrip: 那个题我要来数据发现时间有负的……没有单调性吧
2015年3月20日 21:49
@sublinekelzrip: 题目什么数据范围都没给,就当最坏情况考虑的……
2015年3月21日 18:23
就算没单调性也用不着分治啊。。感觉就没有多少题必须用分治的，离线写起来这么麻烦，只要不是必须分治我就不写@kzoacn:
2015年3月21日 19:32
@sublinekelzrip: 平衡树维护凸壳太蛋疼，我个人还是更喜欢分治
2015年3月21日 22:00
神犇你看看1974可不可做啊。。。
2015年3月22日 21:51
@xindubawukong: 我有官方题解……
2015年3月28日 22:08
vset维护啊，dp反正都是在最后添加，就像今年noi第二天第三题，还有2285那个题目二分不是mlogmn1的复杂度，难道不会tle吗？@kzoacn:
2015年3月29日 17:17
前来orz zky
2015年3月30日 10:05
@orzzky: 什么鬼- -