Posts Tagged ‘ ACM

STL神马的最可爱了~ o(> <)o~

因为以前是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。毕竟比赛里这东西用好了能省下很多时间的~

2010 ACM-ICPC Multi-University Training Contest (3) – Host by WHU

做了五个小时A了3题= =。又一次深刻地认识了自己有多水。

Prob.A Ancient Printer

水题,最开始想着字典序排下来就可以了,但是后来发现仅仅按照字典序是不行的,字典序靠前的串可能很长,造成出现原本不必要的删除操作。
发现错了之后一时也没想出来正确解法,就去做后面的题了,后来回过头来再看的时候RP爆了一下想出来了……
首先字典序的出发点是对的,这是为了最大限度地利用重复前缀。
所以换个角度来考虑:假设每个字串都从头开始打,也就是说每个串输完之后都删干净,那么总的代价就是Sum(Len[i]*2 + 1)。在此基础之上,把所有字串按字典序排序,那么对于相邻的两个串,前面重复的部[......]

继续阅读