Posts Tagged “summary”

通常在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 »

熟悉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 »

Python里有个特殊的变量__name__,如果当前模块是主模块,则为’__main__’,否则为模块名。通过判断

if __name__ == '__main__':

执行不同的代码,这样一个模块即可被重用,又可以单独执行,这种结构在Python里非常常见。也可以在if里简单的做一些模块的测试:

# gao.py
def scanl(s, f, a):
	retval = [s]
	for v in a:
		s = f(s, v)
		retval.append(s)
	return retval

if __name__ == '__main__':
	print scanl(1, int.__mul__, range(1, 10))
else:
	print __name__, 'imported'
#> [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

而当gao被import时,这些测试将不被执行:

# gaogao.py
import gao
print 'in' + __name__ + ':', sum(gao.scanl(10000000, int.__div__, range(1, 20)))
#> gao imported
#> in__main__: 27182814

在Perl中虽然有个类似的__PACKAGE__可以得到包的名字(get package name),但是却不像Python中的__name__那样可以判断是否是直接执行的。我没

Comments No Comments »

まずもって〜旧正月あけましておめでとうございます〜
来年もよろしくお願いいたします

正如标题里的[流水],这只是一篇关于自己如“流れる水”般农历牛年的流水账。

  • 首先是寒假,这似乎是大学唯一一次能待到十五的寒假,和父母一起看了彩车龙灯花火,下次在家过元宵不知是何时了
  • 2月份回到学校,终于下定决心结束了在218的土著生活。当然,每天绝大多数的时间还是呆在218的,只不过不怎么在那里睡觉了而已,时差依然混乱中
  • 2月开始的2009 TCO Algorithm,主idrejudge幸运而又不幸地直接晋级Round 1。我也因此人品耗光,Round 2的时候以0分杯具,最终没有实现获得Tshirt的目标
  • 3月底的浙江大学校赛大杯具,队伍的表现也让人失望,自己因此有点情绪低落
  • 3到4月准备World Finals过程中做了大量的大妈题,也就是Andrew Stankevich’s Contest,完成了#1-#5的解题报告,收获非常大,但现在#6-#10却没了动静
  • 4月份最难忘的就是在Stockholm ACM-ICPC World Finals中,作为Zodiac的一员,同队友hhangerFire创造了ZJU历史上的最好成绩,第六名,银牌
  • 从瑞典回来当天就奔去宁波参加全国邀请赛,两位广东队友居然用广东话讨论,让我着实郁闷,最后技不如人,仅获第二,第二次失去帮ouyang保研的机会
  • 5月17日的浙江省省赛依靠速度和一点rp获得了冠军,完成了帮ouyang的保研
  • 6月11日是每年一度的竞赛表彰会,关键在于有米领,会后编程答疑版举行了例版聚,很hi,ms是自己第二次组织版聚
  • 6月14日百度之星复赛,而我却在连续参加大学物理一/二重修的考试,结果两门70+的成绩替代了我原本物理学一/三90+的成绩= =b
  • 找了个更大的硬盘重新架设了90(zjuicpc-host),更新了软件,然后慢慢加了一些东西,问题还很多,希望有时间折腾
  • 6月20日是CET6的日子,还要感谢owen在最后一天帮我交了报名费,还有寒mm考试前给我的2B铅笔,让我最后以裸考480多的成绩低空飘过。于是刚好可以研究生英语免试了
  • 7月的主题自然是集训和校队选拔,可开始的一个星期我却还要忙于数学系的短学期课程——Photoshop!整个7月是相当忙碌,也累得够呛
  • 7月份另一件麻烦事就是搬寝室,我从蓝田4舍6046.4搬到了蓝田4舍6036.4,折腾死我了
  • 7月19-21日去北京参加了有道难题决赛,比赛时如同梦游,显然是杯具了。此行最大的收获是ym到了dmks前辈,当然最后白捡了个300G的移动硬盘也是很爽的
  • 没能力去百度决赛也不是坏事,7月22日刚回到杭州就人生唯一一次观看到了日全食
  • 7月底去深圳参加了为期一周的腾讯创新夏令营(TIC’09),有不少收获,包括来自组织方的和营友的,也接受了不少tencent价值观。最杯具的是因为自己再度比赛中梦游而以一名之差和5000米奖金失之交臂 555
  • 腾讯创新夏令营结束后直接从深圳回家,没待多久就又回学校开始漫无止境的八月
  • 8月的主题是组队集训,我和jay哥寒mm组成的浙江大学的ACM-ICPC三队yukkuri。训练中队伍的配合表现不佳和日益临近的Regional让我不免焦虑了起来,好在最后大家共同克服了问题,队伍也成长了起来
  • 8月开始租了一个海外的VPS,主要用途是用了架设VPN用于上网,后来又架了现在的blog: ゆっくりでいいさ。感谢一

Comments 18 Comments »

计算机内的整数往往是固定长度的,比如32位整数,如果整数超出表示范围则会发生溢出。大数(BigInteger)则是具有任意精度的数(arbitrary precision number),是一个实际运用中常见,尤其在程序设计竞赛里频繁出现的数据结构。java因为带有BigInteger类,而成为竞赛中解决大数问题的首选,而C/C++则需要第三方库提供大数支持。至于其他很多语言,都有语言或标准库级别上的高精度运算支持,只不过其中很多除了在SPOJ和GCJ外恐怕都不怎么能用于水题。Small factorials里有在SPOJ中使用高精度的例子。

Perl: Math::BigInt

Math::BigInt提供了非常多方法,而且很多方法也有对应的运算符重载,支持bin, oct, dec, hex格式字符串与BigInt之间的相互转化,几乎没有不支持的操作,包括三角函数,二项式系数都有。不过Math::BigInt有很多不同的实现,其中最快的是Math::BigInt::GMP,效果还是非常理想的,但是默认的Math::BigInt::Calc就慢得不能忍了,远比php, java, ruby, python的都要慢。另外Math::BigFloat是基于Math::BigInt的高精度浮点数。

use Math::BigInt lib => 'GMP';
use Math::BigFloat try => 'GMP';
print Math::BigFloat->bpi(64), "\n"; # 3.14...
my $x = new Math::BigInt('0x123456789abcdef');
my $y = Math::BigInt->new('0b101010101010101');
print $x + $y, "\n";
print join(":", $x->copy()->bdiv($y)), "\n";

Bash: bc

说bash支持高精度不是很严谨,不过bc(白痴)是Linux下一个支持任意精度数字计算的语言,也算半个标配。bc支持算术运算(+, -, *, /, %, ^等),逻辑运算(<=, ==, ||等),流程控制(if, while, for等),函数定义(define)。bc本身就可以写成脚本执行。

#!/usr/bin/bc -q

define e(n) {
	auto i, p, s;
	p = 10 ^ n;
	s = 2 * p;
	for (i = 2; p > 0; ++i) {
		p /= i;
		s += p;
	}
	return s;
}

print "input a integer: "
x = read()
e(x)
quit

# input a integer: 40
# 27182818284590452353602874713526624977552

Php: BCMath

bc是Binary Calculator的

Comments 7 Comments »