Archive for the “summary” Category

前几天,秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著,我(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》,终于通过人民邮电出版社正式出版了。可喜可贺,可喜可贺。有关该书的简介,目录、试读和购买链接请通过传送门访问。这里我主要想说一下自己为什么要翻译和推荐本书,还有对程序设计竞赛学习资料的一些看法。也附带一些对译者序和第1章的补充说明。

Comments 71 Comments »

通常在Online Judge上的题目要求程序从标准输入流(standard input, stdin)读入输入数据,将答案输出到标准输出流(standard output, stdout),并通常会无视标准错误输出流(standard error, stderr)的输出。当然,过多的stderr输出必然会占用许多额外的时间,导致TLE,所以即使把debug信息输出到stderr,有时也要注意通过注释和条件编译去掉for循环中的debug语句。不过更多的时候,我们主要需要关心的还是stdin和stdout。

不过有时候,某些Online Judge的某些题目就会要求从给定文件读入测试数据,或将结果输出到给定文件中,或二者皆有。大多数编程语言在提供文件IO操作API的同时,都提供有许多直接操作标准输入输出的API。而很多初学者对这些API都要比对文件操作的API熟悉得多。所以如果在此时,能用标准输入输出的API来替代文件输入输出的API无疑是很方便的。在本地,这可以通过shell的重定向轻松办到

./p.exe < input.txt > output.txt 2> log.txt

不过在Online Judge上,这一点就行不通了。好在很多语言都提供有一些API,能实现类似的功能。

除了希望使用标准输入输出的API来实现文件输入输出外。在本地调试程序的时候,有时候通过终端(屏幕)进行交互会方便得多,即使要进行文件输入输出也可以借由shell轻松自如的选择文件。所以,程序在本地使用stdio,而在Online Judge上才使用指定的文件会方便不少。

当然,前面还漏了一点,用标准输入输出的API除了可以节省力气外,还有一个好处是:如果同样一道题,在多数OJ上要用标准输入输出,但有些OJ要求文件输入输出时,代码无需经过太多修改就能AC。嗯,其实我就是在做Codeforces上新加的Andrew Stankevich Contests想到可以做这么一个总结的。下面的代码都用Think Positive这道题测试过,可以AC的完整代码请通过github访问。

Comments 5 Comments »

首先贴两则旧闻:一个是上个月底,IS0 C++委员会正式批准了C++编程语言国际标准最终草案(FDIS)。

标准本身已经完成,接下来将是根据委员会会议修改意见更新工作草案,预计将用三周时间完成FDIS草案,然后交给日内瓦的ITTF,最新的C++标准将在夏天发布,先前被临时命名为C++0x的新标准将被称为C++ 2011。从2003年发布的C++03到2011年的C++ 2011,新标准的制定历经了8年时间。GCC和Visual C++编译器都已加入了C++2011/C++0x的支持。

另一个则是紧接着在3月25日,GCC 4.6.0发布。

GNU项目和GCC开发者正式宣布发布GNU编译器4.6.0版本。 GCC 4.6.0的新特性包括:支持Go语言,改进C++0x支持,可伸缩全程序优化器已能可靠使用,新的-Ofast选项, 无效命令行的严格检查,改进编译时间和内存占用,等等。

而这其中正包括了倍受期待的foreach了,在C++0x,它的正式名字是Range-based for-loop

Comments 9 Comments »

被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做,然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

\{(x_1,x_2,\cdots,x_n)|0\le x_1\le X_1, 0\le x_2\le X_2, \cdots, 0\le x_n\le X_n\}

而对应的Hyperplane为
a_1x_1+a_2x_2+\cdots+a_nx_n=b

那么我们实际要求的就是Convex
\{\mathbf{x}|0\le x_i\le X_i,\mathbf{a}^T\mathbf{x}\le b\}

的体积。

不妨先考虑两个二维平面上的例子:

mp-case-1

\{(x,y)|0\le x\le 4,0\le y\le 3,x+y\le 5\}

Comments 14 Comments »

熟悉STL或熟悉ACM/ICPC的话,其中的set, map, multiset, multimap一定用过无数次了,它们都是用平衡二叉树(红黑树)实现的,复杂度为O(lgn)。我们也知道set, map可以通过哈希来实现,复杂度只有O(1),可惜直到现在,unsorted_set或hash_map都没能成为C++标准的一部分(C++0x,- -b)。不过无论在GNU GCC中还是Microsoft Visual Studio中都有对hash_set, hash_map, hash_multiset, hash_multimap的支持。

GCC中的hash_map定义在<ext/hash_map>文件,namespace __gnu_cxx中。要定义一个hash_map<int, int>非常简单:

#include <ext/hash_map>
using namespace __gnu_cxx;
hash_map<int, int> hm;

在使用map时,如果我们想要改变元素顺序,或以自定义的struct/class作为key的时候,可以设定map第三个模板参数(默认是less<Key>,即operator<)。对于hash_map,我们需要设定其第三个(hash<Key>)和第四个模板参数(equal_to<Key>, operator==)。

typedef long long my_type;
typedef int any_type;
struct my_hash {
    size_t operator()(const my_type& key) const {
        return (key >> 32) ^ key;
    }
};
struct my_equal_to {
    bool operator()(const my_type& lhs, const my_type& rhs) const {
        return lhs == rhs;
    }
};
hash_map<my_type, any_type, my_hash, my_equal_to> my_hash_map;

对与int等基本类型,系统提供有hash<int>等版本的模板特化,所以只需要指定前两个模板参数就足够了。实现了模板特化的有以下类型

[const] char*, crope, wrope, [signed|unsigned] char, [unsigned] short, [unsigned] int, [unsigned] long

如果需要的话,我们也可以为其他类型实现模板特化

// hash_map<Key, Tp, HashFn=hash<Key>, EqualKey=equal_to<Key>, Alloc=allocator<Tp> >
#include <cstdio>
#include <utility>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;

namespace __gnu_cxx {
    template<>
    struct hash<pair<int, int> > {
        size_t operator()(const pair<int, int>& key) const {
            return key.first * key.second;
        }
    };
}
hash_map<pair<int, int>, int> hm;

Visual C++的hash_map定义在<hash_map>文件,namespace stdext中,早先在namespace std中。其实现与GCC的不同,模板参数也不一样,比如上面的例子在VC++版本如下

Comments 15 Comments »