常见问题（WA） · znzryb
## 通用错误
### 前面算还是后面算？
一个东西，到底是在前面算，还是在后面算的，一定要搞清楚。如果是在后面算的，前面就不要算，否则会重复。
[](https://www.notion.so/24c4539447bd80ccaa4ad35344443ef0)
### 位掩码与开闭区间
这个-1非常重要。
[](https://www.notion.so/26a4539447bd8056a440f82962ae744e)
```cpp
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 为空。
```cpp
if (it==res.end() || it==prev(res.end())) {
if (res.empty()) {
return {0,0};
}else {
return {0,res.back()};
}
}
```
## OJ和本地结果不一致
一定是超界访问了。
```cpp
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);
}
```
## 输入
### 输入类型不匹配
```cpp
struct OP{
ll char op;ll dis;
friend istream& operator >>(istream &is,OP &e){
cin>>e.op>>e.dis;
return is;
}
};
```
### 输入的时候就输入，不要干其他事情
忘记cin了，导致了一系列问题。
```cpp
FOR(i, 1, N) {
cin >> A[i];
res ^= A[i];
}
```
## 函数
### 函数返回值不能为空值
## 指针
### 默认构造函数初始化
```cpp
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];
}
}
};
```
## 字符串
### 字符串，字符拼接
### 整行读入
getline会把换行符给读掉。
```cpp
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()一下。
```cpp
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](https://ac.nowcoder.com/acm/contest/108300/D)
那么WA的原因在于这个有一些小问题，就是加粗部分赛时那发WA的没有加，即**初始化阶段也要加上答案判断**。
```cpp
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";
```
## 倍增
树上倍增，只能解决最高点，不能解决最低点，或者至少需要转化。
[](https://www.notion.so/2394539447bd8042a52fd8e9a28fca78)
这个倍增还是太阴间了。就是一般来说，找到的点就是答案的情况，还是要特判一下。
```cpp
ll low=tr.findlow(u);
if(low==u){
cout<<l<<"\n";
return;
}
```
## 差分相关
### 离散化
[](https://www.notion.so/23b4539447bd809e88a1f501a35ed8c4)
[https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=20171](https://acm.hdu.edu.cn/contest/view-code?cid=1174&rid=20171)
注意这里不能简单+1（下方的代码是对的）（简单的+1就是查lr[i].SE的idx，然后加的地方直接就是idx+1，这个是不行的，我们不能默认这两个区间是相交的）
```cpp
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++自动向上取整。
```cpp
inline ll chu(ll x){
if(x<0) return x/2;
if(x%2==0) return x/2;
return x/2+1;
}
```
## 状态压缩
### 差一错误
状压要特别小心差一错误。（就是加粗，下划线的地方必须要+1）
```cpp
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，否则很有可能会爆炸
```cpp
ll sum=accumulate(all(A),0ll);
```
### unique
自定义结构体使用unique，**需要定义==和<**，两者缺一不可。
```cpp
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](https://leetcode.cn/problems/fruit-into-baskets/submissions/649566028/?envType=daily-question&envId=2025-08-04)
### 内层循环因为循环完退出时，应该重新定向bp
否则会被形如这样的数据卡掉。
```cpp
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，递归退出条件
遇到这两个东西，看看是不是这个递归退出条件的问题？
这个循环退出条件特别容易忘记。
```cpp
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++是取余操作，会得到负数，进而导致错误。
```cpp
FOR(i,1,N-1){
diff[i]=abs(diff[i]);
diff[i]%=2;
}
```
## 序列匹配问题（相同情况需要特判）
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78695197](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78695197)
```cpp
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。
```cpp
if(idx==5 || idx==6){
}else{
mp[{mon,d}]++;
}
```
## zkw线段树/线段树
### zkw线段树节点表示范围以及线段树上二分
节点表示范围是 $[le,rr]$，然后根节点表示范围是$[0,sz-1]$
```cpp
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;}
```
[](https://www.notion.so/25b4539447bd808cb23df5dff12ebcb5)
```cpp
// 找到最靠近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;
}
```
### 线段树内部之间不要相互调用
[](https://www.notion.so/24c4539447bd8031b625f8fd22b25826)
千万不要这么干，因为不仅更新的时候要调用，下传标记也要调用，你能保证两个线段树的懒标记状态一样吗？这个是不可能的，因为你也不可能同时更新，询问两个线段树，**除非把他们合为一个。**
## 指针与迭代器
### lower_bound与++
一定要++it，不能it++。
## dp 动态规划
### 超范围转移
[](https://www.notion.so/2524539447bd80909c26e8257c239518)
不要去想超范围转移哪些是正确的，而是直接给所有超范围部分赋值-INF。
正难则反，去想哪些超范围转移是正确的。（一般是起始位置的转移位置）
```cpp
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);
}
}
```
# 计算几何
## 检查线段交点
### 如果发现检查器太严格，可能是这道题目要求的不相交，是和所有和自己不相关的线不相交
检查器最好检查一下两个线段的**交点**是不是一个线段的**端点**？这种情况需不需要特殊处理？
[](https://www.notion.so/25d4539447bd8002b84bf88d65a5a936)
```cpp
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
### 剪枝条件不要把现有的队列里的点给剪掉
一定要是>号。
[](https://www.notion.so/2634539447bd80a3922bd202f07b2d9c)
```cpp
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});
}
}
}
```