Archive for the “summary” Category
首先贴两则旧闻：一个是上个月底，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 Range-based for-loop
9 Comments »
被问到上次ZOJ Monthly中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做，然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为
而对应的Hyperplane为
那么我们实际要求的就是Convex
的体积。
不妨先考虑两个二维平面上的例子：
9 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++版本如下
15 Comments »
Posted by watashi in summary , tags: bash , bc , BigInteger , haskell , java , perl , php , python , ruby , summary
计算机内的整数往往是固定长度的，比如32位整数，如果整数超出表示范围则会发生溢出。大数(BigInteger)则是具有任意精度的数(arbitrary precision number)，是一个实际运用中常见，尤其在程序设计竞赛里频繁出现的数据结构。java因为带有BigInteger类，而成为竞赛中解决大数问题的首选，而C/C++则需要第三方库提供大数支持。至于其他很多语言，都有语言或标准库级别上的高精度运算支持，只不过其中很多除了在SPOJ和GCJ外恐怕都不怎么能用于水题。Small factorials 里有在SPOJ中使用高精度的例子。
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(白痴 )是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
bc是Binary Calculator的
7 Comments »
想当年学C#的时候.Net还是2.0，学了就直接丢掉了，要不是到MS来实习，估计也未必会再捡起来了，结果.Net都4.0了。最近coding才发现C# 3.0多了好多新特性，而自己还把一些C# 2.0的特性彻底忘了，真不敢说自己会C#了。于是总结一下最近遇到并且常用到的特性吧。
1. ? – Nullable<T>
[SerializableAttribute]
public struct Nullable<T> where T : struct, new()
C#里像int, bool, double这样的struct和enum类型都不能为null。如果确实想在值域上加上null的话，Nullable就派上用场了。T?是Nullable&ly;T>的语法糖。要将T?转为T可以通过类型转换，或者通过T?的Value属性，当然后者要高雅些。
// Nullable<int> arg = -1;
int? arg = -1;
if (arg.HasValue) {
// int value = (int)arg;
int value = arg.Value;
}
2. ?? – operator ??
o ?? v可以看作是o == null ? v : o的语法糖。??运算符在左操作数非null时返回左操作数，否则返回右操作数。
string result = gao();
Console.WriteLine(result ?? "<NULL>");
3. => – lambda expression
看别人代码的过程中才发现原来C#也有lambda了，也才发现自己真的out了。当然，感觉C#里的lambda并没有带来什么革命性的变化，更像是一个语法糖。毕竟这不是Scale，MS也有F#了。
Func<double, double, double> hypot = (x, y) => Math.Sqrt(x * x + y * y);
Func<double, double, string> gao = (x, y) =>
{
double z = hypot(x, y);
return String.Format("{0} ^ 2 + {1} ^ 2 = {2} ^ 2", x, y, z);
};
Console.WriteLine(gao(3, 4));
4. {} – initializer
collection initializer使得初始化一个List, Dictionary变得简单。
List<string> list = new List<string>{"watashi", "rejudge"};
Dictionary<string, string> dic = new Dictionary<string, string>
{
{"watashi", "watashi wa watashi"},
{"rejudge", "-rejudge -pia2dea4"}
};
而object initializer其实就是调用完成构造后执行属性操作的语法糖，它使得代码更加简洁，段落有致。试比较：
10 Comments »
Entries (RSS)