Archive for the ‘ Programming Infinity ’ Category
这或许是我近一段时间以来获知的最近动人心的消息了。作为一个算法爱好者，这感觉就像是见证了上帝的存在一样。
激动之情难以言表。这里就先贴几个链接吧。
cnBeta报道 http://cnbeta.com/articles/118835.htm
维基百科 http://zh.wikipedia.org/zh-cn/P/NP问题
论文我传了一份上来，在这里 http://everdebug.in/wp-content/uploads/2010/08/35539144-pnp12pt.pdf
因为以前是OI出来的，很少用到STL（竞赛大纲禁止使用绝大部分STL容器和算法）。最近为了ACM训练重新开始刷POJ的时候，才慢慢认识到这个东西的强大~
比如，给出一个排列，求按照字典序，它前面或者后面的第K个排列。
这种东西要是自己去写会显得很麻烦，而且很容易出错。而有了可爱的STL之后，只需要这样两行代码（假设排列存放在string对象arr中）
for (i=1; i<=K; i++)
prev_permutation(arr.begin(), arr.end());
这是何等的爽啊啊啊啊~~~有了这个之后瞬间秒掉了POJ3359，代码只有40行出头 （好吧我承认这道题其实是水题= =）
容器部分就更不用说了，AVL应该比我自己写的Splay快，priority_queue什么的用起来也很方便。
准备这两天找点资料，好好学一下STL。毕竟比赛里这东西用好了能省下很多时间的~
#include
#define maxint 0x3fffffff
#define maxn 3000
#define S 1
#define T N
//链表存图，使用反向弧指针
typedef struct Edge {
int vtx, cap, flow;
Edge *rev, *next;
Edge (){}
Edge (int vertex, int capacity, Edge* pt){
vtx = vertex; cap = capacity; flow = 0;
rev = NULL; next = [......]
做了五个小时A了3题= =。又一次深刻地认识了自己有多水。
Prob.A Ancient Printer
水题，最开始想着字典序排下来就可以了，但是后来发现仅仅按照字典序是不行的，字典序靠前的串可能很长，造成出现原本不必要的删除操作。
发现错了之后一时也没想出来正确解法，就去做后面的题了，后来回过头来再看的时候RP爆了一下想出来了……
首先字典序的出发点是对的，这是为了最大限度地利用重复前缀。
所以换个角度来考虑：假设每个字串都从头开始打，也就是说每个串输完之后都删干净，那么总的代价就是Sum(Len[i]*2 + 1)。在此基础之上，把所有字串按字典序排序，那么对于相邻的两个串，前面重复的部[......]
| 一 | 二 | 三 | 四 | 五 | 六 | 日 |
|---|---|---|---|---|---|---|
| « 十二 | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 | |||