hdu 6249 Alice’s Stamps DP

先删除所有被完全包含的区间。

然后对区间按照右端点排序。

dp[i][j]表示考虑前i个区间中选j个的最大覆盖面积。

然后三个转移。

dp[i][j] = dp[i – 1][j]

起传递作用

如果在i处有结尾的区间,长为l

dp[i][j] = dp[i[……]

Read more

HDU6223 Infinite Fraction Path 递推

就是给一个数字序列,从0开始。

从第i位可以跳到(i^2 + 1) % n位。

稳得到一个长度为n的序列,这个序列最大是多少。

我们就递推就下就好了,求出每层最大可能的取值,一层层往下推。记得去一下重。然后i^2可能炸int,调了好久。。
[crayon-5bcf4b7b45ad[……]

Read more

POJ 1470 Closest Common Ancestors tarjan LCA

题目没写多case,然而却是多case题,坑死了…

POJ 1330 Nearest Common Ancestors 倍增LCA

POJ 1330 Nearest Common Ancestors ST表LCA

POJ 1637 Sightseeing tour 混合图欧拉回路 网络流

先考虑联通性,不连通则无解。

再给所有双向边钦点一个方向,和单向边一样记录入度出度。

然后我们考虑,对于一个点,把一条双向边的方向改变,入度-出度的奇偶性是不变的,这样子我们看一下,所有点的入度-出度,如果为奇数,则无解。

然后我们对于每个点,如果其出度大于入度,则从s到i连一条流[……]

Read more

hdu 6393Traffic Network in Numazu 基环外向树 LCA 树

题意就是,给你一个基环外向树,然后问任意两点间最短路,有修改边权,nlogn做法。

然后就在环上随便删一个遍,然后我们lca求最短路,再看经过删掉的边的距离,取个min就好了。这题数据很有趣,最后一条边一定在环上,可以少写一个dfs……

然后怎么修改边权,线段树按照dfs序维护一[……]

Read more

BZOJ 2199 && luguoP3007 [USACO11JAN]大陆议会The Continental Cowngress 2-sat

对板子有了更深刻的理解,只要2-sat存在,那么dfs函数求出的一个方案一定是一个合法解的子集。

BZOJ 1823 1823: [JSOI2010]满汉全席 2-sat

对这套2-sat板子又有了更深刻的理解。现在感觉kuangbin这套板子真的很妙,应该可以处理所有的2-sat问题。

POJ 3683 Priest John’s Busiest Day 2-sat

就是两个时间段必须选一个,依旧用的kuangbin的那套理论。现在我觉得这套理论可能只支持两个只能选一个情况。还在研究。