因为有我(你)，所以你(我)快乐

文章列表

2008-07-17 21:12

http://acm.pku.edu.cn/JudgeOnline/problem?id=2926

这道题是火鸡大牛在群里说的。:-) 我百度了一下，原来是多维点对的最远曼哈顿距离。以前没有遇到过，记一下下。^_^

讲解摘自：http://www.blog.edu.cn/user2/lower/archives/2006/1519018.shtml
1. 最远曼哈顿距离：
即在N个点中求两点i和j使得|xi-xj|+|yi-yj|的值最大

阅读全文>>

类别：搜索 | 评论(0) | 浏览()

pku 1063 Gangsters 动态规划

2008-07-14 12:28

http://acm.pku.edu.cn/JudgeOnline/problem?id=1036

这道题好hdu 1176 免费馅饼很像，可惜我按这个方法作一直MLE。
请教了Mcfaddan_b 后，发现原来只要用一位数组就可以了。佩服

“最优值仅和选定的进旅馆的土匪集合有关，而与土匪进旅馆的顺序无关”。所以，我们可以先按进旅馆的时间t降序排。然后就可以dp了。设 f[i]表示以

阅读全文>>

类别：动态规划 | 评论(0) | 浏览()

pku 1015 Jury Compromise 经典动态规划

2008-07-11 14:11

http://acm.pku.edu.cn/JudgeOnline/problem?id=1015

这道题从昨天下午就开始想。不过由于智商有限，最后还是没有想通，期间写了又删，删了又写。原来我对DP根本没有理解，一开始就当成背包来做(这题按背包方法，没有最优子结构的。55555 ). 后来 "和谐论坛"里的一位热心的大牛给了我她的代码，仔细看才发现她定义的状态才是对的。不过我还是没看懂她的代码，只有一个朦胧的概念。后来不得不去寻找标程去了。标程和她的状态定义的

阅读全文>>

类别：动态规划 | 评论(0) | 浏览()

pku 1185 炮兵阵地第一道状态压缩的dp

2008-07-07 10:03

http://acm.pku.edu.cn/JudgeOnline/problem?id=1185

这道题是周伟《状态压缩》论文里的例题，我就依葫芦画瓢了。。^_^
特别感谢 javaman 和 sunny_fable

偶的丑陋代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxsnum=65;
const int maxn=105, maxm=15;
int a[maxm], s[maxsnum], c[maxsnum], no[maxn];

阅读全文>>

类别：动态规划 | 评论(2) | 浏览()

今天遇到彩虹了. ^_^

2008-07-03 00:54

今天发生了好多 unexpected 的事情，看到彩虹算是一件吧。还是双重的彩虹。

手机拍的，很不清晰。不知道能不能看到另外一条比较淡的彩虹。:-)

类别：随记 | 评论(1) | 浏览()

Murphy's Laws of Combat

2008-07-01 23:06

Murphy's Laws of Combat
http://sff.net/paradise/combat.html

1. You are not Superman.

2. If it's stupid but it works, it isn't stupid.

3. Never draw fire; it irritates everyone around you.

4. Odd or conspicuous objects attract fire. Never lurk behind one.

5. Armored vehicles are bullet magnets.

6. Incoming fire has the right of way.

7. It's not the one with your name on it;

阅读全文>>

类别：Wisdom | 评论(0) | 浏览()

数据库考试，太惨烈了. 原来我们都被华东师大的老师惯坏了.

2008-06-30 18:08

时间： 2008年6月30日18:05:44，刚考完数据库。

我被华东师大的老师惯坏了。

刚考完数据库，完全没想到那个老师这样出题。比期中操作系统的题BT过甚。

考完感觉：不后悔上课没听讲（因为听了也不会做，老师上课讲的和这个完全不是一个水平）。真后悔平时没怎么交作业，实验报告也还欠了1次，期末项目没怎么做。更倒霉的是，被老师点到2次（一次是迟到1分钟，被算了旷课，她总共就点了4次 =_=）我的平时成绩啊。谁偷了我的平时成绩。

反思：我被华东师大软件学院的老师惯坏了。

阅读全文>>

类别：随记 | 评论(2) | 浏览()

eoj 1894 游戏最小割

2008-06-19 01:36

http://202.120.80.191/problem.php?problemid=1894
这是ECNU练习11的一道题目，我很弱，一直不知道怎么做。今天在 javaman 大牛的帮助下，总算知道了。
跟 McFn 说的一样，这题是pku 3041的加强版。^_^

阅读全文>>

类别：图 | 评论(0) | 浏览()

值得纪念的一个凌晨-荷兰淘汰世界杯冠亚军

2008-06-14 04:52

今天凌晨做了几道二分图最大匹配，终于把pku做到100了。赶在2点45看了荷兰和法国的欧洲杯小组赛。^_^，绝对经典，不输给A米和利物浦的欧冠决赛。

足球，瞬息万变~~
2-0， 2-1， 3-1， 4-1. 世界杯亚军就这样被屠了。
死亡之组大概要弄死世界杯冠亚军了. 要知道，荷兰06年世界杯外围赛就被淘汰了啊。
戏剧，喜剧。。。。。。。。。。。。。

1274, 1469(最大匹配);
1325(点覆盖:m)
1422, 2060, 3215 (路径覆盖:n-m)
1466(点独立. 区分男女:n-m/2);

类别：默认分类 | 评论(0) | 浏览()

ecnu 2149 华丽的队列堆？STL 真的很好很强大

2008-06-10 23:01

我放这里了。。(*^__^*) 嘻嘻……
http://hi.baidu.com/%5Fkop/blog/item/1392e12ce9a10ae98a1399a3.html

类别：stl 算法+容器 | 评论(1) | 浏览()

:-) 转向团队的 _kop 空间

2008-05-18 01:31

哈哈哈~~

Unit, We Stand .
校赛加油·~
http://hi.baidu.com/_kop

类别：默认分类 | 评论(4) | 浏览()

关于最长上升、下降子序列

2008-05-16 12:45

注意二分的写法，我的写的比较难看，=_=
http://202.120.80.191/problem.php?problemid=2106
最长下降
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn =100001;
const int INFI =0x3fffffff;
struct Node{
int x, y;
bool operator < ( co

阅读全文>>

类别：动态规划 | 评论(0) | 浏览()

hdu 1692 Destroy the Well of Life 优先队列

2008-05-13 21:01

http://acm.hdu.edu.cn/showproblem.php?pid=1692

教训：
1、对题意挖掘不够。真的像张佳说的那样：要理清思路。^_^

这时杭电比赛的题目。比赛的时候和队友讨论半天也没有一个好方法。到最后，本来想去敲一下(N^2)的naive的算法，结果被理智的队友拒绝了(N可是10万啊~~)。呵呵。总之，没有做出来~~
后来请教了alpc(alpc真的很强大)，说要维护一个优先队列。不过我当时没听懂~~

回来后，又和张佳讨论

阅读全文>>

类别：比赛 | 评论(1) | 浏览()

pku 2186 Popular Cows 强连通子图SCC

2008-05-06 21:51

http://acm.pku.edu.cn/JudgeOnline/problem?id=2186

题目的discuss里面讨论的好清楚，而且还给出了证明。先贴过来一下·~ 呵呵..

问题是，我的代码跑的相当地慢。因为我检查收缩成的点是否是出度为0的点时，扫描了原来所有的边。而且dfs 的时候用了一个 check检查是否为同一强分支中的点。确实很慢·~ 看那些牛人都是几十ms过的，更有大牛0ms，膜拜一下. 不知道有什么高效的方法，暂时没想出来。谁知道的话

阅读全文>>

类别：图 | 评论(0) | 浏览()

pku 1463 zju 1134 Strategic game 树形DP ？？？单纯DFS ？？

2008-05-05 19:51

http://acm.pku.edu.cn/JudgeOnline/problem?id=1463

http://acm.zju.edu.cn/show_problem.php?pid=1134

这是一系列树形dp中的最简单的一道。我认为这道题没有用到dp，只是dfs而已。因为没有重叠子问题。它只满足最有子结构。

关于树形dp的题目和讲解。我推荐两人的博客·~：

阅读全文>>

类别：树 | 评论(0) | 浏览()