抽象错误集锦

本文收录自己犯过的一些离谱错误，用来引以为戒。

  1. (Acwing 121)离散化之后混用下标和离散化的数值 
    1
    2
    3
    4
    5
    6
    7
    8
    ll tx=lower_bound(x,x+rx,i+mid-1)-x,ty=lower_bound(y,y+ry,j+mid-1)-y;
    if(x[tx]>i+mid||tx>=rx)tx--;
    if(y[ty]>j+mid||ty>=ry)ty--;
    ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
    if(ans>=c){
    	res=true;
    	goto out_of_loop;
    }
    正确写法： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    ll tx=lower_bound(x,x+rx,x[i]+mid-1)-x,ty=lower_bound(y,y+ry,y[j]+mid-1)-y;
    if(x[tx]>x[i]+mid-1||tx>=rx)tx--;
    if(y[ty]>y[j]+mid-1||ty>=ry)ty--;
    ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
    if(ans>=c){
        res=true;
        goto out_of_loop;
    }

    其中 i,j 是下标， x[i],y[j] 是离散化之后的数。
  2. (AT_abc356_d)组合数求法。 错误示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    ll c(ll p,ll n){
    	if(n==0)return 0;
        ll res=1;
        for(ll i=1;i<=p;i++){
            res=(res*i)%Mod;
        }
        for(ll i=n;i>=n-p;i--){
            res=(res*i)%Mod;
        }
        return res;
    }
    槽点有点多。
    首先，，因此即便 ， 也非零。其次，下半部分的阶乘应当时乘上乘法逆元，而不是乘上 。第三， 有 个数。正确示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ll c(ll p,ll n){
        ll res=1;
        for(ll i=1;i<=p;i++){
            res=(res*niyuan[i])%Mod;
        }
        for(ll i=n;i>n-p;i--){
            res=(res*i)%Mod;
        }
        return res;
    }
  3. (Acwing220)线性筛等需要多个循环变量时分清每个变量是做什么的。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void prime_prework(){
        memset(min_prime_factor,0,sizeof min_prime_factor);
        for(ll i=2;i<=inp;i++){
            if(min_prime_factor[i]==0){
                phi[i]=i-1;
                min_prime_factor[i]=i;
                primes[n]=i;
                n++;
            }
            sum_prefix[i]=sum_prefix[i-1]+phi[i];
            for(ll j=0;j<n&&primes[i]<=min_prime_factor[j]/*此处下标i,j反了*/&&i*primes[j]<=inp;j++){
                phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
                min_prime_factor[i*primes[j]]=primes[j];
            }
        }
    }
    正确示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void prime_prework(){
    	memset(min_prime_factor,0,sizeof min_prime_factor);
    	for(ll i=2;i<=inp;i++){
    		if(min_prime_factor[i]==0){
    			phi[i]=i-1;
    			min_prime_factor[i]=i;
    			primes[n]=i;
    			n++;
    		}
    		sum_prefix[i]=sum_prefix[i-1]+phi[i];
    		for(ll j=0;j<n&&primes[j]<=min_prime_factor[i]&&i*primes[j]<=inp;j++){
    			phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
    			min_prime_factor[i*primes[j]]=primes[j];
    		}
    	}
    }
  4. (AcWing258)想得太复杂了。看完题目以为要用一大堆推理分析，调了好久都没想出来。后来发现暴力就能过。（实际上不是没注意到数据范围，而是以为这道题目时限比较松）结论就是：当一个思路不太好实现时，建议换一个思路。
  5. (Luogu P4198)开 long double 要开全！！ 
    1
    ll cal(ll p,ll h){/**/} // <-- ll h 应为 long double h
    正确示范： 
    1
    ll cal(ll p,long double h){/**/}
  6. (Luogu P4556)检查特殊下标（比如 ）有没有特判。（可以用 fsanitize 查查ub）
  7. (Luogu P4556)还是那题，倍增法LCA记得特判第一步就移动到相同的点上的可能。
  8. (Luogu P4556)又是那题，还是倍增法LCA,检查开的数组的大小，记住 。
  9. (Luogu P6225)写树状数组时记得不要把 和 搞混了。虽然很离谱但是我已经连续两次把 中的 写成 了。
  10. (Luogu P6619)还是树状数组，写 pos-=lowbit(pos) 的时候不要把 lowbit 漏掉。
  11. (Luogu P6619)倍增的时候不要直接把算出来的 当作 。听起来很离谱，但是我确实这么干了。还有记得更新各个变量。
  12. (Luogu P3834)可持久化权值线段树到叶子节点的时候记得把旧的数值复制进来。
  13. (Luogu P7453)记得取模！！！
  14. (Luogu P7453)区间操作记得更新路径上的节点的值！！
  15. (Luogu P4170)递归dp如果不确定调用次数记得写记忆化！！！
  16. (Luogu网校 T483205)一边 range-for 一边插入节点会出问题。
  17. (Luogu网校 T483205) std::unordered_map<__int128,__int128> 会出问题，因为 __int128 没有默认的 hash 函数。（改为 long long 即可）
  18. (Luogu网校 T483205)手写邻接表+hash 忘记更新下标。 错误示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    i128 query(ll i){
        i128 h=((i%M)*P)%M;
        ll ind=head[h];
        while (ind!=-1){
            if(ht[ind].num==i){
                return ht[ind].val; 
            }
        }
        return 0;
    }

    正确示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    i128 query(ll i){
        i128 h=((i%M)*P)%M;
        ll ind=head[h];
        while (ind!=-1){
            if(ht[ind].num==i){
                return ht[ind].val; 
            }
            ind=ht[ind].nxt; //<-- 这行少了
        }
        return 0;
    }
  19. (Luogu网校 T486366)多测慎用 memset()，以及不需要频繁取模。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    while(t--){
        memset(s,0,sizeof s); //<-- 这一行
        memset(order,0,sizeof order); //<-- 和这一行
        /*
        由于这两个数组是 1e7 级别的
        数据保证所有测试点 n 的总和为 1e7
        所以当 n 的规模远小于 1e7是
        总共的测试点组数可能会来到
        1e3 甚至 1e4。
        而这两个语句在每个测试点都会重复memset一边 1e7 的数组
        因此导致 TLE。
        */
        //sth else
        for(ll i=0;i<n-k+1;i++){
            ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); //<-- 这里的取模是多余的，因为下一行已经取过一次摸了，而且并不会爆精度。多出来的一次取模导致常数变大 TLE
            ans%=(ll)1e9+7;
        }
    }
    正确示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    while(t--){
    	//sth else
    	s[n+1]=s[n]=0;// 最终程序最大只会访问到 n，因此只把这两个赋值就可以了。（前面的有输入）
    	//sth else
        for(ll i=0;i<n-k+1;i++){
            ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); // <-- 去掉多余的取模操作
            ans%=(ll)1e9+7;
        }
    	//output...
    }
  20. (Luogu P6033)这道题时间复杂度卡的很紧。有的时候构造函数可以省略。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct node{
    	ull val;
        ull times;
    	node(){
            val=times=0; //<-- 此处构造函数会在声明时调用。由于数组过大(1.5e7)导致调用是会有约 50ms 的常数增加（此题时限 500ms，卡的很紧）
    	}
    };
    struct Queue{
    	node data[(int)1.5e7+100];
        //sth
    	//在队列的push函数中已经有了对于node相关成员的修改。因此无需初始化。
    }
    正确示范： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct node{
    	ull val;
        ull times;
    	// <-- 删去了构造函数
    };
    struct Queue{
    	node data[(int)1.5e7+100];
        //sth
    }
  21. (Luogu P4513)线段树的 x<=mid 不要写成 mid<=x。 
    1
    2
    3
    4
    5
    6
    7
    void modify(ll p,ll x,ll v){
    	//sth
    	if(mid<=x){ //<-- 应为 x<=mid
    		modify(lc(p),x,v);
    	}
    	//sth
    }
  22. (Luogu网校 T489100)写线性筛的时候需要注意各种边界问题。（以及复制代码的时候把变量名盖全）
  23. (Luogu网校 T491913)Floyd 算法。需要注意不能枚举通过一条边到达 的点和从 开始通过一条边可以到达的点。具体看代码。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for(ll i=0;i<m;i++){
    	ll s,t,v;
    	cin>>s>>t>>v;
    	G1[s].push_back({v,t});
    	G2[t].push_back({v,s});
    }
    //do sth
    for(ll i=1;i<=n;i++){
        for(auto s:G2[arr[i].ind]){ //<-- 这两处有误
            for(auto t:G1[arr[i].ind]){ //<--
    			//do sth
            }
        }
    }
    正确写法： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for(ll i=0;i<m;i++){
    	ll s,t,v;
    	cin>>s>>t>>v;
    	G1[s].push_back({v,t});
    	G2[t].push_back({v,s});
    }
    //do sth
    for(ll i=1;i<=n;i++){
    	for(ll s=1;s<=n;s++){
    		for(ll t=1;t<=n;t++){
    			//do sth
    		}
    	}
    }
  24. (校内模拟)复制粘贴：其一 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    template<ll T>
    struct modint{
        ll val;
        modint(){
            val=0;
        }
        modint(ll x){
            val=x%T;
        }
        bool operator==(const modint<T>& b)const{
            return val==b.val;
        }
        modint<T> operator+(const modint<T> &b)const{
            return modint<T>(val+b.val);
        }
        modint<T> operator+=(const modint<T> &b){
            val=(val+b.val)%T;
            return *this;
        }
        modint<T> operator*(const modint<T> &b)const{
            return modint<T>(val+b.val); //<-- 注意这里
        }
        modint<T> operator*=(const modint<T> &b){
            val=(val*b.val)%T;
            return *this;
        }
        modint<T> operator-(const modint<T> &b)const{
            return modint<T>(val-b.val+((val-b.val<0)?T:0));
        }
        modint<T> operator-=(const modint<T> &b){
            val=(val-b.val)%T;
            if(val<0)val+=T;
            return *this;
        }
    };
  25. (同上)复制粘贴：其二 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ll l=1,r=sz;
    while (l<r) {
        ll mid=(l+r)>>1;
        if(rotate(m, mid)==rotate(m, mid)){ // <-- 恒等
            l=mid+1;
        }
        else {
            r=mid;
        }
    }
  26. (没想到吧，还是一道题)字符串hash没有预处理 pow 数组（甚至已经声明过了
  27. (一样)二维 hash 写错数组 
    1
    2
    3
    4
    5
    6
    7

    for(ll i=1;i<=n*2;i++){
        for (ll j=1; j<=m*2; j++) {
            G[i][j].a=(H[i-1][j].a*P1)+H[i][j].a;
            G[i][j].b=(H[i-1][j].b*P2)+H[i][j].b; //<-- 右侧 H[i-1][j] 应为 G[i-1][j]
        }
    }
  28. (P9149) 死循环：其一 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while (h < v.size() && i == v[h].r) {
    	ll t = bi.query(v[h].r) - bi.query(v[h].l - 1);
    	if (t > d) {
    		continue; //<-- 注意 h 并不会更新，导致死循环
    	}
    	ll rest_w = w - nums - t, rest_d = d - t;
    	ans += C(rest_d, rest_w);
    	h++;
    }
  29. (P3527)无限递归：其一 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void add(ull l, ull r, ull val) {
        if (r < l) {
            add(1, m, val);
            add(r + 1, l - 1, -val);
        } else {
            add(l, val);
            add(r + 1, -val);
        }
        return;
    }
    考虑 l==3&&r==2 的情况，add(r + 1, l - 1, -val); 递归后仍然 r<l。
  30. (P3810)使用之前记录下来的下标访问元素的时候要原数组是否更改。 
    1
    2
    3
    4
    solve(0, total - 1); // 这个函数是cdq分治，里边要重新排序，之前记录的下标会失效
    for (ll i = 0; i < n; i++) {
        cnt[ans[i]] += arr[i].times;
    }
    解决： 
    1
    2
    3
    4
    5
    solve(0, total - 1);
    sort(arr, arr + total, [](const e &a, const e &b) {return a.i<b.i;});// <-- 重新排个序就好了
    for (ll i = 0; i < n; i++) {
        cnt[ans[i]] += arr[i].times;
    }
    补上提交记录或许更容易理解：不排序，排序
OI
#OI
抽象错误集锦
https://blogs.sving1024.top/chou-xiang-cuo-wu-ji-jin/
发布于
2024年6月14日
许可协议