最近做SPOJ，发现很多题目的读入都是有大幅度优化余地的。事实上，在C++中，使用scanf()读入整数或者实数的速度都非常慢。我们可以通过一次读入一整行的来加快速度，方法是使用gets()。
对于gets()这个函数，GCC的文档建议不要使用。我个人的感觉是只要使用得当，这个函数还是大有用处的。比如下面的代码：
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)，时候就可以进行相关的操作了。在这个函数的基础上稍作改进还可以读入实数等等。
这道题看上去有点欧几里得算法的意思在里面，实际上不是。我仅仅是在判断有没有解的时候用了一次求最大公约数的算法，接下来就是模拟，分别模拟从a往b倒和从b往a倒得两种情况，很容易就Accepted了。
#include <cstdio>
#include <climits>
using namespace std;
int ntest,a,b,c,d;
int min(int a,int b) {
return a<b?a:b;
}
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int check(int a,int b) {
int ret = 0,ca = 0,cb = 0;
for (;;) {
if (ca==c || cb==c) return ret;
if (cb==b) cb = 0;
else if (ca==0) ca = a;
else {
int dt = min(b-cb,ca);
ca -= dt; cb += dt;
}
ret++;
}
}
int main() {
scanf("%d",&ntest);
while (ntest--) {
scanf("%d%d%d",&a,&b,&c);
d = gcd(a,b);
if (c%d!=0 || c>a && c>b) printf("-1\n");
else {
int ans = check(a,b);
ans = min(ans,check(b,a));
printf("%d\n",ans);
}
}
return 0;
}
Your program in C++ from 2010-04-09 07:16:22 ran for 0.01 seconds and used 2536 KB of memory.
打开一个页面元素比较简单的网页，然后再地址栏里面输入：
javascript:(function(){var s=document.createElement("script");s.charset="UTF-8";var da=new Date();s.src="http://www.rr.iij4u.or.jp/~kazumix/d/javascript/meltdown/meltdown.js?"+da.getTime(); document.body.appendChild(s)})();
就可以看到很神奇的东西。
虽然是js的外挂代码，但是还是挺有意思的。
这个题目相当经典了，是一个树结构的询问题。一般而言，这种题目都是先给出一个树，然后进行更改边权值、对边的修改（节点也可以），然后对某段路径进行询问。从根本上来讲，这类题目的本质都是在维护树的路径。
QTREE算是这类题目中的一道入门题。给出一棵树，然后更改边的权值或者询问一条路径上边权最大的边。由于不涉及树的形态，我们直接用树链剖分先构造固定的线段树来维护路径。对于相应的更改和询问，只要先预处理好LCA就可以轻松维护了。
在树中不同路径中遍历的复杂度是O(log n)，查询一次边的复杂度是O(log n)，每次查询LCA的复杂度是O(log n)。我在预处理LCA的时候采用的是O(n log n)-O(log n)的算法，所以总的复杂度就是O(n log n+q log2 n)。事实上，如果我们用RMQ的O(n)-O(1)算法来处理这个LCA，复杂度就应该是O(n+qlog2 n)。
值得注意的是，使用gets()优化一下输入，程序会快很多，我的程序就快了1.37s。至于为什么我的程序这么慢，只能说明我的代码写得太烂了。
Your program in C++ from 2010-04-07 07:19:34 ran for 4.09 seconds and used 4424 KB of memory.
Your program in C++ from 2010-04-07 11:05:42 ran for 2.72 seconds and used 4348 KB of memory.
对于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()函数永远是读入到当前行为止，并且自动转到下一行的开头。