Znzryb's Blog
0%

常见问题（WA）

Posted on Edited on

通用错误

前面算还是后面算？

一个东西，到底是在前面算，还是在后面算的，一定要搞清楚。如果是在后面算的，前面就不要算，否则会重复。

image

位掩码与开闭区间

这个-1非常重要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
			ll cur = sum - N + K - 1;
			FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
				debug(j);
#endif
				mask[j] = 0;
			}
			up = cur;
			// 这一大段代码
			// sum-N+K<=val<=K
			if ((mask & dp).any()) {
				ans = i;
			} else {
				break;
			}

RE 运行时错误

.back()

比较常见的运行时错误有，就是这个去取这个 vector 的最后一个数（.back()），但是 vector 为空。

1
2
3
4
5
6
7
if (it==res.end() || it==prev(res.end())) {
    if (res.empty()) {
        return {0,0};
    }else {
        return {0,res.back()};
    }
}

OJ和本地结果不一致

一定是超界访问了。

1
2
3
4
5
6
7
8
FOR(i,1,10000){
    ll lans=0;
    FOR(j,1,5000){
        if(i==i-j) lans+=2*min(cnt[i-j],cnt[j]);
        else lans+=min(cnt[i-j],cnt[j]);
    }
    ans=max(ans,lans);
}

输入

输入类型不匹配

1
2
3
4
5
6
7
struct OP{
    ll char op;ll dis;
    friend istream& operator >>(istream &is,OP &e){
        cin>>e.op>>e.dis;
        return is;
    }
};

输入的时候就输入，不要干其他事情

忘记cin了，导致了一系列问题。

1
2
3
4
FOR(i, 1, N) {
	cin >> A[i];
	res ^= A[i];
}

函数

函数返回值不能为空值

指针

默认构造函数初始化

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct MyString{
    char *p;
    int n;
    static int cnt;
    static int GetCount(){
        return cnt;
    }
    MyString(){p=nullptr;n=0;++cnt;}
    MyString(unsigned n,char c){
        p=new char[n+1];
        this->n=n;
        FOR(i,0,n-1){
            p[i]=c;
        }
        p[n]='\0';
        ++cnt;
    }
    MyString(char *s){
        n=strlen(s);
        p=new char[n+1];
        p[n]='\0';
        FOR(i,0,n-1){
            p[i]=s[i];
        }
        ++cnt;
    }
    char operator[](int i)const{
        return p[i];
    }
    MyString& operator= (const MyString &s){
        n=s.n;
        p=new char[n+1];
        FOR(i,0,n-1){
            p[i]=s[i];
        }
        p[n]='\0';
        return *this;
    }
    MyString (MyString &s){
        n=s.n;
        p=new char[n+1];
        FOR(i,0,n-1){
            p[i]=s[i];
        }
        p[n]='\0';
        ++cnt;
    }
    ~MyString(){
        --cnt;
        delete [] p;
    }
    void ShowStr(){
        FOR(i,0,n-1){
            cout<<p[i];
        }
    }
};

字符串

字符串，字符拼接

image

整行读入

getline会把换行符给读掉。

1
2
3
4
5
6
7
inline void __(){
    string s;
    getline(cin,s);
    char c;c=cin.get();
    s.resize(remove(all(s),c)-s.begin());
    cout<<s<<"\n";
}

但是普通的cin不会读掉换行符号，需要再cin.get()一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;cin.get();
    while(lT--)
        __();
    return 0;
}
/*

*/
inline void __(){
    string s;
    getline(cin,s);
    reverse(all(s));
    cout<<s<<(lT!=0?"\n":"");
}

统计连续的相同字符数量

https://ac.nowcoder.com/acm/contest/108300/D

那么WA的原因在于这个有一些小问题，就是加粗部分赛时那发WA的没有加，即初始化阶段也要加上答案判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
FOR(i,1,N){
	if(g[S[i]-'0'].empty() || i-g[S[i]-'0'].back()!=1){
		cnt=1;
		g[S[i]-'0'].pb(i);
		if(S[i]=='0' && cnt>=M+1){
			cout<<N<<"\n";
			return;
		}else if(S[i]=='1' && cnt>=M){
			cout<<N<<"\n";
			return;
		}
	}else{
		++cnt;
		g[S[i]-'0'].pb(i);
		if(S[i]=='0' && cnt>=M+1){
			cout<<N<<"\n";
			return;
		}else if(S[i]=='1' && cnt>=M){
			cout<<N<<"\n";
			return;
		}
	}
}
cout<<SZ(g[1])<<"\n";

倍增

树上倍增，只能解决最高点，不能解决最低点，或者至少需要转化。

这个倍增还是太阴间了。就是一般来说，找到的点就是答案的情况，还是要特判一下。

1
2
3
4
5
ll low=tr.findlow(u);
if(low==u){
	cout<<l<<"\n";
	return;
}

差分相关

离散化

https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=20171

注意这里不能简单+1（下方的代码是对的）（简单的+1就是查lr[i].SE的idx，然后加的地方直接就是idx+1，这个是不行的，我们不能默认这两个区间是相交的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vll diff(SZ(li)+5,0);
FOR(i,1,N){
	ll l=lower_bound(all(li),lr[i].FI)-li.begin();
	ll r=lower_bound(all(li),lr[i].SE+1)-li.begin();
	l++,r++;
	ll rnd=rng();
	diff[l]^=rnd;
	diff[r]^=rnd;
}
vll Sum(SZ(li)+5,0);
FOR(i,1,SZ(li)+2){
	Sum[i]=Sum[i-1]^diff[i];
}
set<ll> st;
FOR(i,1,SZ(li)+2){
	st.insert(Sum[i]);
}
cout<<SZ(st)<<"\n";

简单算术

向上取整除法可以这样写，没有精度问题，非常对呀。注意C特性，x/2实际上是往0取整的，所以x<0的时候就不用我们操心了，C自动向上取整。

1
2
3
4
5
inline ll chu(ll x){
	if(x<0) return x/2;
	if(x%2==0) return x/2;
	return x/2+1;
}

状态压缩

差一错误

状压要特别小心差一错误。（就是加粗，下划线的地方必须要+1）

1
2
3
4
5
6
7
8
FOR(s,0,(1<<N)){
	bitset<25> bi(s);
	ll val=0;
	FOR(i,0,N-1){
		if(bi[i]){
			val+=V[i+1];
		}
	}

std

accumulate

这边一定要写0ll，否则很有可能会爆炸

1
ll sum=accumulate(all(A),0ll);

unique

自定义结构体使用unique，需要定义==和<，两者缺一不可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Point{
    ll x,y;
    bool operator<(const Point& other){
        if(x!=other.x) return x<other.x;
        return y<other.y;
    }
    bool operator==(const Point& other){
        return x==other.x && y==other.y;
    }
};
inline void __(){
    cin>>N;
    vector<Point> stars(N);
    FOR(i,0,N-1){
        cin>>stars[i].x>>stars[i].y;
    }
    sort(all(stars));
    stars.resize(unique(all(stars))-stars.begin());
    cout<<SZ(stars)<<"\n";
}

双指针

https://leetcode.cn/problems/fruit-into-baskets/submissions/649566028/?envType=daily-question&envId=2025-08-04

内层循环因为循环完退出时，应该重新定向bp

image

否则会被形如这样的数据卡掉。

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
class Solution {
public:
    int totalFruit(vector<int>& A) {
        ll N=SZ(A);
        unordered_map<ll,ll> mp;
        mp[A[0]]++;
        ll ans=1;
        ll bp=0;
        FOR(i,0,N-1){
            if(i!=0){
                mp[A[i-1]]--;
                if(mp[A[i-1]]<=0) mp.erase(A[i-1]);
            }
            FOR(j,max(bp,i+1),N-1){
                mp[A[j]]++;
                if(SZ(mp)>2){
                    bp=j;
                    mp.erase(A[j]);
                    break;
                }
                ans=max(ans,j-i+1);
                if(j==N-1){
                    bp=j+1;
                }
            }
        }
        return ans;
    }
};

dfs（递归）

MLE，TLE，递归退出条件

遇到这两个东西，看看是不是这个递归退出条件的问题？

这个循环退出条件特别容易忘记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function<void(ll,ll,ll,ll)> dfs=[&](ll a,ll b,ll c,ll d){
    if(d>=b){  
        
    }else{
        swap(a,c);
        swap(b,d);
    }
    if(b==0 || d==0 || a==1 || c==1){
        return;
    }
    if(b<=1 && d<=1){
        if(b==0) a=1;
        if(d==0) c=1;
        ans*=__gcd(c,a);
        ans%=mod;
        return;
    }
    ll e=__gcd(a,c);
    ans*=binpow(e, b);
    ans%=mod;
    ll x=a/e;
    // dfs(e*x,b,e,b-d);
    dfs(x,b,e,d-b);
};

取余（取模）

C++是取余操作，会得到负数，进而导致错误。

1
2
3
4
FOR(i,1,N-1){
    diff[i]=abs(diff[i]);
    diff[i]%=2;
}

序列匹配问题（相同情况需要特判）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78695197

1
2
3
4
5
6
7
8
9
ll ans=2;
FOR(i,2,10000){
    ll lans=0;
    FOR(j,1,i){
        if(j==i-j) lans+=(cnt[j]/2*2);
        else lans+=min(cnt[i-j],cnt[j]);
    }
    ans=max(ans,lans);
}

日期相关问题

模拟宜采用正向逻辑。

0-based的话星期六星期日就是星期5，6。

1
2
3
4
5
if(idx==5 || idx==6){
            
        }else{
            mp[{mon,d}]++;
        }

zkw线段树/线段树

zkw线段树节点表示范围以及线段树上二分

节点表示范围是 [le,rr][le,rr]，然后根节点表示范围是[0,sz−1][0,sz-1]

1
2
3
4
int dis(int o){return dep-__lg(o);}
int len(int o){return 1<<dis(o);}
int le(int o){return (o<<dis(o))-sz;}
int rr(int o){return (o+1<<dis(o))-sz-1;}

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
36
// 找到最靠近r的符合位置
 template<class F> int findl(int r,F&&fun){
     return findl(1,r,0,sz-1,fun);
 }
 // 找到最靠近r的符合位置
 template<class F> int findl(int o,int qr,int l,int r,F&&fun){
     if(l==r){
         return l;
     }
     // pushdown(o);
     ll ls=o<<1,rs=ls|1;
     ll mid=l+r>>1;
     ll pos=-1;
     if(fun(tr[rs]) && mid+1<=qr) pos=findl(rs,qr,mid+1,r,fun);
     if(pos!=-1) return pos;
     if(fun(tr[ls])) pos=findl(ls,qr,l,mid,fun);
     return pos;
 }
 // 找最靠近l的符合位置
 template<class F> int findr(int l,F&&fun){
     return findr(1,l,0,sz-1,fun);
 }
 // 找最靠近l的符合位置
 template<class F> int findr(int o,int ql,int l,int r,F&&fun){
     if(l==r){
         return l;
     }
     // pushdown(o);
     ll ls=o<<1,rs=ls|1;
     ll mid=l+r>>1;
     ll pos=-1;
     if(fun(tr[ls]) && mid>=ql) pos=findr(ls,ql,l,mid,fun);
     if(pos!=-1) return pos;
     if(fun(tr[rs])) pos=findr(rs,ql,mid+1,r,fun);
     return pos;
 }

线段树内部之间不要相互调用

千万不要这么干，因为不仅更新的时候要调用，下传标记也要调用，你能保证两个线段树的懒标记状态一样吗？这个是不可能的，因为你也不可能同时更新，询问两个线段树，除非把他们合为一个。

image

指针与迭代器

lower_bound与++

一定要it，不能it。

image

dp 动态规划

超范围转移

不要去想超范围转移哪些是正确的，而是直接给所有超范围部分赋值-INF。

正难则反，去想哪些超范围转移是正确的。（一般是起始位置的转移位置）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vll> A(N+5,vll(M+5));
vector<vll> dp(N+5,vll(M+5,-INF));
vector<vll> dp2(N+5,vll(M+5,-INF));
FOR(i,1,N){
    FOR(j,1,M){
        cin>>A[i][j];
    }
}
dp[0][1]=0;
dp[1][0]=0;
FOR(y,1,M){
    FOR(x,1,N){
        ll val=A[x][y];
        dp[x][y]=max(max(dp2[x][y-1],dp[x][y-1])+val,dp[x-1][y]+val);
    }
    ROF(x,N,1){
        ll val=A[x][y];
        dp2[x][y]=max(max(dp2[x][y-1],dp[x][y-1])+val,dp2[x+1][y]+val);
    }
}

计算几何

检查线段交点

如果发现检查器太严格，可能是这道题目要求的不相交，是和所有和自己不相关的线不相交

检查器最好检查一下两个线段的交点是不是一个线段的端点？这种情况需不需要特殊处理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto check=[&](Line a)->bool {
    bool ok=true;
    FOR(i,0,SZ(A)-1){
        Line t=A[i];
        // if(t==a) continue;
        if(onseg(a.p, t) && onseg(a.q, t)) return false;
        if(isseginterline(t, a) && isseginterline(a, t)){
            if(onseg(a.p, t) || onseg(a.q, t)) continue;
            ok=false;
            break;
        }
    }
    return ok;
};

图论

dij

剪枝条件不要把现有的队列里的点给剪掉

一定要是>号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while (!pq.empty()) {
    auto [node,dis]=pq.front();
    pq.pop_front();
    if(dis>Dis[node]) continue;
    Dis[node]=dis;
    for(auto&v:g[node]){
        if(node<=N){
            if(dis+1>=Dis[v]) continue;
            Dis[v]=dis+1;
            pq.PB({v,dis+1});
        }else{
            if(dis>=Dis[v]) continue;
            Dis[v]=dis;
            pq.PF({v,dis});
        }
    }
}