| 题目 | 是否完成 | 题目分类 | 简要题解 |
| 没有上司的舞会(codevs1380) | Y | 树形dp |
dp[u][0]表示不包含此节点,dp[u][1]表示包含,转移方程为 dp[u][0]+=max(dp[v][1],dp[v][0]); dp[u][1]+=dp[v][0]; http://pastebin.ubuntu.com/23112271/ |
[bzoj1050]舒适的路线 |
Y | kruskal+贪心 |
排序边，然后枚举权值，往下加边，每次更新答案 http://pastebin.ubuntu.com/23112511/ |
[bzoj1003]物流运输 |
Y | 最短路+dp |
算出任意两天内都能走的最短路记为day[a][b] dp[i]表示以第i天结尾，运i天的最小消耗 dp[i]=min(dp[j]+day[j+1][i]*(i-j)+K,dp[i]);(1 < j < i ) http://pastebin.ubuntu.com/23120325/ |
[Usaco 2008 Oct]Watering Hole |
Y | kruskal |
把水池当成0，也就是要把0和其它点连在一起，最小生成树直接搞，建边注意输入的n个值连上0当成边就是了，矩阵也建边，然后跑最小生成树 BZOJ这题是权限题，但是在另一个oj上找到了 http://acm.hit.edu.cn/hoj/problem/view?id=2825 http://pastebin.ubuntu.com/23120537/ |
[bzoj1192]鬼谷子的钱袋 |
Y | 思维题 |
给定一个m要你分成不同的x份，使得能表示成小于等于m的所有数，问你x最小是多少。 那我们就能把m拆分成2进制来搞，最后一个不足最后一位的单独放或者分类讨论一下知道答案就是恰好大于m的2^x。 http://pastebin.ubuntu.com/23120571/ |
[bzoj1191]超级英雄Hero |
Y | 最大匹配 |
题目容易可以想到转化成二分图匹配，每道题对应两个锦囊，然后以此建图，直接匈牙利就行，但注意trick..假如到某一题答不出的时候，就不能答下一题了，需要break出去.因为这个GG了几发. http://pastebin.ubuntu.com/23120826/ |
[bzoj1303]中位数图 |
Y | 思维题 |
全排列中查询查询中位数为d的奇数子序列有多少个，比d小赋值为-1，比d大的赋值为1，然后从d往左边扫，从d往右边扫，左边加起来的前缀和，对应右边的相反数则可以构成这样一个子序列，修正一下负数，没有说数据范围。 http://pastebin.ubuntu.com/23120905/ |
[bzoj3039]玉蟾宫 |
Y | 单调栈 |
对于每个点，以这个点的高度，往左右拓展，更新一个最大值就是答案了。 可以用单调栈维护一下左右 权限题，不过可以在codevs找到 http://pastebin.ubuntu.com/23122670/ |
[bzoj1059]矩阵游戏 |
Y | 最大匹配 |
行列怎么换每一行每一列的数量都是一样的，所以只需要对应在每一行都找到不同列的就是Yes 转二分图，最大匹配。 http://pastebin.ubuntu.com/23122881/ |
[bzoj1202]狡猾的商人 |
Y | 并查集 |
用rank[x]表示x-fa[x]这段直接的和，其实就是关系，然后更新的时候一个是find()里面需要更新下去 rank[x]+=rank[fa[x]]这样下去，然后并的操作需要自己模拟一下比较好理解,范围的话把l,r改成l-1,r比较好更新因为你知道[1,2]和[3,6]就能合并起来[1,6]了。 http://pastebin.ubuntu.com/23123516/ |