ACM技巧记录

1 常量值记得加const，有助于优化器优化

2 linux的strstr是优化过的，比KMP快

3 for循环判断不要使用计算值

如

for(int i=0;i<strlen(a), i++)

4 FFT中的模

a += M & (a>>31);

其目的是将[-M,M)中的整数模M，即变成[0,M)中的数。

其正确性依赖于GCC规定负数右移的规则按算数右移的规则，即负数右移最高位补1。

5 读入挂的使用

参考链接：https://blog.csdn.net/xs18952904/article/details/76768791

c++中：

在ACM里，经常出现数据集超大造成 cin TLE的情况。这时候大部分人（包括原来我也是）认为这是cin的效率不及scanf的错。其实像这只是C++为了兼容而采取的保守措施。我们可以在IO之前将stdio解除绑定，这样做了之后要注意不要同时混用cout和printf之类。

在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

#include <iostream>
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}

错误方式：

#define read read()

struct P{
int x, y;
P(int xx, int yy):x(xx), y(yy{});
};

int main()
{
 P p(read, read);
}

由于这样的read写在构造函数中，读入的顺序不确定，容易产生bug

但是可以这样写

P p{read, read}

因为语言标准要求初始化列表中的元素必须做左到右求值

6 加入INF,NAN异常，来帮助找到错误

#include<iostream>
#include<cfenv>
#include<cmath>

using namespace std;
int main(){
    feenableexcept(FE_INVALID|FE_DIVBYZERO|FE_OVERFOLW);
    double a=-1, b=0;
    cout<<sqrt(a/b)<<"\n;
    return0;
}

7 对拍

generator.py

from random import randint ,seed
seed(int(input()))
n = randint(1, 10)
print(n)
print(" ".join([str(randint(1,100)) for i in range(n)]))

#!/bin/sh

for ((i=0;;i++)) do
    echo $i | python3 generator.py > dara-$i.in
    ./brute < data-$i.in > data-$i.ans
    if | ./solution < data-$i.in > data-$i.out; then
        echo "runtime error on test $i"
        break
    fi
    if diff data-$i.ans data-$i.out; then
        rm data-$i.{in,out,ans}
    else
        echo "wrong answer on test $i"
        break
    fi
    echo "test $i ok"
done

8 调试使用GDB

打比赛主流工具是codeblocks和文本编辑器vi等。

相对来说GDB是较好的调试器