随便写个标题吧。。算不算标题党？ 整理一下最近写的题目。 大连网络赛： To Miss Our Children Time 背包问题，排个序就行了，题目描述不清。。 Find Metal Mineral 树形动归，f[x][j]表示以x为根的树，前i个子树放j个机器人不回来的最小值，DFS的感觉。f[x][0]表示放一个再出来。做的第一个树形动归，参照别人的代码，很巧妙的写法嘛。刚才看题目忘了具体怎么写了= = void work(int x,int prev) { for (int i=head[x];i!=-1;i=edge[i].next) { if (edge[i].y==prev) continue; work(edge[i].y,x); for (int j=k;j>=0;j–) { f[x][j]+=f[edge[i].y][0]+edge[i].w*2; for (int l=0;l<j;l++) f[x][j]=min(f[x][j],f[x][l]+edge[i].w*(j-l)+f[edge[i].y][j-l]); } } } PS：原来这个叫做分组背包= = The Frog’s Games 比赛的时候以为是DP，结果就是个二分… The kth great number 最简单的办法就是弄一个最小堆，堆顶就是答案，priority_queue用起来很爽。 priority_queue <int, vector<int>, greater<int> > [...]
2011暑假做的ACM题目
去了北大那个暑期课程… 对于我来说还是难了点，我觉得还不如自己看PPT= =。早知道能找得到10年的PPT就预习一下了。。 发现不会的好多，慢慢学吧。 部分题目： 8.7 HDU 3836 Equivalent Sets Tarjan强连通分量 8.8 POJ 1273 Drainage Ditches 最简单的网络流 POJ 3436 ACM Computer Factory 把机器拆成两个点求最大流 POJ 2112 Optimal Milking Floyd求最短路，然后二分答案，求最大流判断是否满足 8.9 POJ 1149 PIGS 建图不好想 POJ 2396 Budget 建图也不好想，有流量限制的最大流，用邻接矩阵写得很痛苦= = //终于知道网络流是啥意思了。。感觉还得多做题 TopCoder SRM513 DIV2 第一题 这也算是我第一道TopCoder题 8.10 POJ 2135 Farm Tour 最小费用最大流，用SPFA选最短路增广 POJ 2318 TOYS POJ 2398 [...]
HDU3560一直TLE
冒个泡。。。这里几个月没更新了吧？= = http://acm.hdu.edu.cn/showproblem.php?pid=3560 是这个题。。一直TLE 看起来是个简单的并查集题目。。周日刚学的 昨晚开始写，参照是学长的union函数，今天看了CRLS上这一部分，改了改。 网上搜了几个程序，看起来和我的都差不多嘛，删删改改交了十几次都是TLE= = 似乎。。很少遇到这种情况啊。 这是TLE代码，求助= = #include <stdio.h> #include <stdlib.h> #define maxn 100005 int father[maxn],rank[maxn]; //father初始化为-1，<del datetime="2011-03-31T03:06:58+00:00">其实还不太理解rank为什么只在相等的时候加1</del>。懂了！“Maintain rank(x) as an upper bound on the depth of the tree rooted at x. ” 可以google一下 union by rank. 有个PPT int findfather(int a) { if (father[a]<0) return a; else { [...]
