算法竞赛错误集锦

一. 常规错误

1. 搞混YesNo等的大小写。

for (int j = x; j <= y; j++)
    if (p[a[i]] == a[j])
    {
        puts("YES");
//      puts("Yes");
    }
    puts("NO");
//  puts("No");

2. 滥用static

void swap(int &x, int &y) {
    int t = x, x = y, y = t;
//  static int t = x, x = y, y = t;
}

static的作用范围在括号内,但是在其他方面是相当于全局变量的。初始化语句static int t = x只会被执行一次而导致错误,如果确实需要应该改成static int t = 0; t = x, x = y, y = t;

3. 使用异或swap不当

void swap(int &x, int &y) {
    int t = x, x = y, y = t;
//  x ^= y ^= x ^= y;
}

这种异或看似高端,却并不比交换型swap快,并且在两个数相等时出错,应避免使用

4. fread, fwrite写错

虽然很少写错,但是可以记一下。这里把括号写开一点。

namespace fastIO
{
    #define Getchar() ((p1==p2&&(p2=(p1=in)+fread(in,1,1<<23,stdin))), p1==p2) ? EOF : *p1++
    char in[1<<23], *p1 = in, *p2 = in;
    char out[1<<23]; int q1 = -1; const int q2 = (1<<23)-1;
    inline void flush()
    {
        fwrite(out, 1, q1 + 1, stdout);//注意:下标从0开始,应该是q1 + 1
        q1 = -1;
    } 
    inline void Putchar(const char x)
    {
        if (q1 == q2) flush();
        out[++q1] = x;
    }
        ...
        //程序结尾还需调用一次flush

5. inf大小不当

long longdouble等类型,如果使用就应该把inf的值设得更大,以避免不必要的错误。

int N, K, a[MAX], b[MAX];
double M, f[MAX];

signed main()
{
    cin >> K >> M >> N;
    for (int i = 1; i <= N; i++)
        cin >> a[i] >> b[i], f[i] = 1e18;//f[i] = 1e9
        ...

6. 取模问题

计数问题总会取模, 一般(a%p+p)%p是最稳的,但是一般不会直接这么写,写一个(a+p)%p往往比较合适。

但是更重要的是哪些地方需要取模,如果是计算的中间值,你不能确定肯定不用取模的话就应该取模,不能总想着会变的很慢。

还有最重要的就是并不是所有情况都可以取模的,比如取最大值这种,就一定要在最大值算完在取模。

7. 0做初值使用不当

一些问题(比如数颜色种类)中,如果下标从0开始,又将标记,中间值等默认赋值为0,就会导致问题。

这个时候可以将下标整体移动,或者特判一下0,或者将初值赋为-1.

int &x = a[i].fa;
if (x) {
//
    a[i0].lc = a[i0].rc = a[i0].fa = x, a[i0].c = 1;
    a[i1].lc = a[i1].rc = a[i1].fa = x, a[i1].c = 1;
    x = 0;
}

8. 浮点数输入不当

当使用scanf输入double类型数时,只能使用%lf,如果使用了%Lf或者%f都会出现问题,但是输出就没有这么多限制。

for (int i = 1; i <= N; i++)
    scanf("%lf%lf", &x[i], &y[i]);
//  scanf("%Lf%Lf", &x[i], &y[i]);

二. 数据结构

1. 线段树做修改和下推标记时没有乘以区间长度。

void add(int i, int l, int r, int c)
{
    if (r < L[i] || R[i] < l) return;
    if (l <= L[i] && R[i] <= r)
    {
        mx[i] += c * len(i);
//      mx[i] += c;
        return;
    }
    ...

需要注意的是,有些属性(最大值,最小值)是本就与区间长度无关的

2. 线段树下标从0开始

一般的线段树是无法处理下标从0开始的情况的,在与坐标有关的题目中,最好将坐标读入时全部+1以避免问题。

add(1, a[i].y1+1, a[i].y2, a[i].d);
//add(1, a[i].y1, a[i].y2-1, a[i].d)

三. 图论算法

1. Floyd自环处理不当。

Floyd矩阵在处理自环时常常出现问题,在不同题目中要求不同,可能会将f[i][i]设为0inf,若没有注意到则会导致错误。

```cpp
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
{
cin >> f[i][j];
// if (i == j) f[i][j] = 1e9;
}

上一篇:Java数组补充


下一篇:java基础