Znzryb's Blog
0%

Posted on Edited on

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

Problem F. For the treasury!

把这个问题看成选K个数字，然后把这K个数字全部移到第一个位置，然后把多减的代价加回来。

Problem B. Blind Alley（看到这种砍掉一个方向，要想到dp）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78442849&returnHomeType=1&uid=817445536

赛时提交有问题是因为并没有考虑这个动态的过程，或许这种题目还是要首先搞清楚这个模拟，把这个模拟的本质，模拟的策略给搞清楚。模拟的策略就是说，至少目前为止，我走到这个点，一定是可以到达

直接模拟这个玩家，其实通过题意理解，只要这个玩家所走到的点最终能够走到视野的尽头，那么这个玩家就认为他能够走到走到终点。

那么前面有一个反向bfs，得到所有我们能到达终点的点。（赛时解法中已经想到了）。

那么这个far数组，或者说dp数组，可以通过比较朴素的前缀dp得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<ll> > dp(N+5,vll(M+5));
ROF(j,M,1){
	if(j==M){
		FOR(i,1,N){
			if(S[i][j]=='0'){
				dp[i][j]=j;
			}
		}
		continue;
	}
	FOR(i,1,N){
		if(S[i][j]=='1') continue;
		dp[i][j]=j;
		dp[i][j]=max(dp[i][j+1],dp[i][j]);
	}
	FOR(i,2,N){
		if(S[i][j]=='1') continue;
		dp[i][j]=max(dp[i][j],dp[i-1][j]);
	}
	ROF(i,N-1,1){
		if(S[i][j]=='1') continue;
		dp[i][j]=max(dp[i][j],dp[i+1][j]);
	}
}

然后模拟这个玩家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	while(!q.empty()){
		auto [x,y]=q.front();q.pop();
		FOR(i,0,2){
			ll u=x+dxx[i],v=y+dyy[i];
			if(u<1 || u>N) continue;
			if(v<1 || v>M) continue;
			if(vis2[u][v]) continue;
			if(S[u][v]=='1') continue;
// 只要这个玩家所走到的点最终能够走到视野的尽头，那么这个玩家就认为他能够走到走到终点
			if(dp[u][v]<y+K){ // 该玩家可以看到该点已经被堵死了。
				continue;
			}
			if(!vis[u][v]){  // 如果按照前面的逻辑筛选过了，还是踏入了陷阱，输出yes
				cout<<"Yes\n";
				return;
			}
			vis2[u][v]=true;
			q.EM(u,v);
		}
	}

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

Problem I. I, Box

那么我个人认为难点在于这个题目需要输出推动序列，其实还是有点难的，难度在于这个模拟，以及代码实现上。

Problem G. Ghost in the Parentheses

首先，将（ 转为1，）转为-1，始终有合法匹配（序列是合法的）就是前缀和始终为正。

通过该条件，我们能找出所有的不可交换位置（指的是你不能拿 ））和这个$（ $ 换 ）。

通过如下程序，可以计算出来这个 ）所能选的右括号有rem=N/2−fixrem=N/2-fix 个，但是这样之间计算概率只能通过第一个样例，那怎么办那？遇事不决，就上dp（当然我也不会，和grok学的，这个dp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	ll fix=0;
	ll inv2=binpow(2,mod-2);
	ll ans=0;
	FOR(i,1,N){
		if(A[i]==1 && Sum[i]<=1){
			fix++;
		}
		if(A[i]==-1 && i!=N){
			ll rem=N/2-fix;
#ifdef LOCAL
    debug(rem);
#endif
			ans+=1*inv2*(1-binpow(inv2,rem));
			ans%=mod;
		}
	}
	ans=1-ans;
	ans%=mod;if(ans<0) ans+=mod;
	cout<<ans<<"\n";

Posted on Edited on

思路讲解

我们赛时设计了一个算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vll siz(N+5,0);
vector<pll> nodes(N+5,{0,0});
FOR(i,1,K){
	ll u,l,r;
	cin>>u>>l>>r;
	siz[u]=r-l+1;
	nodes[u]={l,r};
}
function<void(ll)> dfs=[&](ll u)->void{
	for(auto &v:g[u]){
		dfs(v);
		siz[u]+=siz[v];
	}
};

但是这个算法只能判断可达性（或者可达性都有点问题），瓶颈在于这个算法并不在乎达到该节点的时间。

那么有没有办法让这个算法在乎时间那？其实也简单，在该时间内，该树只有之前能到达的点。

1
2
3
4
5
6
7
8
9
10
11
ll mn=min(time,dis);
ll v=tr.findk(u,dis-mn);
if(v==u){   // 找到可到达点
	ll ans=dis+l-1;
	cout<<ans<<"\n";
	return;
}
while(v!=low){  // 溯源路径，给路径上面所有点打上OK标记
	tr.OK[v]=true;
	v=tr.fa[v][0];
}

AC代码

心路历程（WA，TLE，MLE……）

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});
        }
    }
}

Posted on Edited on

思路讲解

思路就是用异或操作可以对齐位数，然后使用最高位，不断左移异或。

总的来说我就是看题解的。

image

image

AC代码

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

心路历程（WA，TLE，MLE……）

这边多进行了一次操作导致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
}else{
	// 先对齐位数
	// if(__lg(A)!=__lg(B)){
		// B^=A;
		// ans.pb(4);
	// }
	ll siz=__lg(A);
	ROF(i,siz,0){	// 最多操作64次
		bitset<40> bia(A),bic(C);
		if(bia[i]==bic[i]){
			B>>=1;
			ans.pb(2);
		}else{		
			A^=B;
			ans.pb(3);
			B>>=1;
			ans.pb(2);
		}
	}
	// B>>=1;
	// ans.pb(2);
	B^=A;
	ans.pb(4);
}