Apr 17

发个可以O(n)时间求逆的代码

Code and Develop 2 Comments
?
1
2
3
4
int[] inv = new int[MAXN];
inv[1] = 1;
for (int i = 2; i<MAXN; i++)
    inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;

注意这里的MOD必须是素数。

摘自TopCoder上某人的代码。

Nov 30

一些看似无用的数学函数

Code and Develop 1 Comments
  • log1p(x)=log(1+x)：看似是一个丝毫没有用的函数，但是如果x非常之小，问题就会出现。计算机会把1+x的结果计算为1，然后返回了0，这和实际结果的相对误差实在太大。
  • expm1(x)=exp(x)-1：存在的理由和上面一样。
  • erfc(x)=1-erf(x)：erf()是一个计算误差的函数，当x很大的时候，erf(x)约为1，此时1-erf(x)就会被计算为0，但它的值应该是一个正数。

转自：HACKER MONTHLY Issue 3 August by John D. Cook

Apr 20

加快输入数据读入速度的函数

Code and Develop 1 Comments

最近做SPOJ，发现很多题目的读入都是有大幅度优化余地的。事实上，在C++中，使用scanf()读入整数或者实数的速度都非常慢。我们可以通过一次读入一整行的来加快速度，方法是使用gets()。

对于gets()这个函数，GCC的文档建议不要使用。我个人的感觉是只要使用得当，这个函数还是大有用处的。比如下面的代码：

?
1
2
3
4
5
6
7
char buf[10000],*o;
inline int getint() {
  while (!isdigit(*o) && *o!='-') ++o;
  int r = 0,f = *o=='-'?++o,1:0;
  while (isdigit(*o)) r = r*10+*o++-'0';
  return (f?-r:r);
}

这个代码提供了一个getint()的函数来加快读入整数的速度。我们使用o = gets(buf)，时候就可以进行相关的操作了。在这个函数的基础上稍作改进还可以读入实数等等。

Apr 2

scanf()函数的一些小问题

Code and Develop 0 Comments

对于scanf()函数来说，" ","\t","\n"并没有什么本质的区别，scanf()函数遇到这三种字符的时候会停止，但是这些字符会变成当前缓冲区中的字符。也就是说，scanf("%d",&n);语句作用完之后，如果还有回车，那么scanf("%c",&ch);读入的就是一个回车。

但是scanf("\n")所读取的并不是一个回车，而是之后所有的" ","\t","\n"字符！其实这就是把缓冲区中所有的" ","\t","\n"字符都清空了。scanf(" ");和scanf("\t");在这方面的功能与scanf("\n");并没有什么区别。

相比之下，gets()要稍微规范一点，可惜的是gets()容易出现溢出错误，所以不建议使用。gets()仅仅是读入到"\n"字符为止，但是与scanf()不同的是，gets()不会把这个遇到的"\n"字符放入缓冲区，而且gets()所跳过的仅仅是这一个"\n"字符！也就是说，gets()函数永远是读入到当前行为止，并且自动转到下一行的开头。

Mar 27

STL笔记

Code and Develop 0 Comments
  1. sort()：在使用sort(first, last, greater<T>())的时候，不要使用greater_eq。也就是对于任意的比较函数f，f(x, x)的结果都应该是false。
  2. empty()：这个函数之所以被设计出来不是没有原因的。部分的类的size()函数并不是一个常数时间的函数，比如list。所以使用empty()是一个很好的习惯，而不是写成XXX.size()==0。
  3. pop()：很多人觉得pop()应该返回顶部元素，而不是void。事实上，如果要返回顶部元素，我们只能返回值的复制，因为顶部的元素被弹出了。这样一来，效率就降低了。
  4. vector的增长量：这个增长量是2，也就是说每次容量不够的时候都是扩大2倍的容量。当然，不同的STL实现增长量也是不同的。但是2无疑是一个比较好的数值。至于为什么是2，是因为要照顾每个元素重新复制的代价。如果增长指数是r，那么最坏情况每个元素都要复制r/(r-1)次。其实也有编译器使用1.5作为增量的。