Znzryb's Blog

ABC-400-D - Takahashi the Wall Breaker（BFS双段队列优化or堆优化）

Posted on 2025-04-06 Edited on 2026-04-06

思路讲解

双段队列优化，让cnt比较低的先走，这样子保证可以被比较好的剪枝

也可以使用堆优化，比双段队列deque稍慢，但也还行。

AC代码

https://atcoder.jp/contests/abc400/submissions/64555057

双段队列优化源代码

// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h> // Includes <deque>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128; // Consider if __int128 is really needed, ll might suffice.
typedef pair<ll,ll> pll;
typedef array<ll,3> arr; // {cost, row, col}
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10;
// Using long long INF is good practice for large grids or costs
constexpr ll INF=static_cast<ll>(4e18); // Adjusted INF to avoid overflow if summing costs many times, though 5e18 is likely fine too.

ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN]; // Stores minimum cost (spells) to reach cell (i, j)

// Directions for normal moves (cost 0)
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

// Relative coordinates for magic moves (cost 1)
// This covers adjacent cells (dist 1) and jumps (dist 2) in the 5x5 area
// A more explicit approach with separate loops for adjacent and jumps is also fine.
// Let's stick to the explicit approach for clarity, matching the original intent better.
ll magic_dx[] = {1, 0, -1, 0,  2, 0, -2, 0}; // Adjacent + Jumps X
ll magic_dy[] = {0, -1, 0, 1,  0, 2, 0, -2}; // Adjacent + Jumps Y


inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>maze[i][j];
			vis[i][j]=INF; // Initialize costs to infinity
		}
	}
	cin>>A>>B>>C>>D;

	deque<arr> q; // Use deque for 0-1 BFS

	vis[A][B]=0;
	q.push_front({0,A,B}); // Start with 0 cost, push to front

	while(!q.empty()){
		arr current = q.front();
		q.pop_front();

		ll cnt=current[0];
        ll x=current[1];
        ll y=current[2];

        // Optimization: If we found a shorter path to (x, y) already, skip processing this one.
        if (cnt > vis[x][y]) {
            continue;
        }

		// --- Explore Cost 0 Moves (Normal adjacent moves to '.') ---
		FOR(i,0,3){
			ll fx=x+dx[i];
            ll fy=y+dy[i];

			// Check boundaries
			if(fx<1 || fx>N || fy<1 || fy>M) continue;
            // Can only move normally into empty cells
			if(maze[fx][fy]=='#') continue;

            // If we found a path with the same or lower cost (cnt)
			if(vis[fx][fy] > cnt) { // Use '>' because cost is the same (cnt)
				vis[fx][fy]=cnt;
				q.push_front({cnt, fx, fy}); // Push to FRONT for cost 0
			}
		}

		// --- Explore Cost 1 Moves (Magic: Adjacent or Jump) ---
        ll next_cost = cnt + 1;
        // Iterate through all 8 possible magic moves (4 adjacent, 4 jumps)
		FOR(i,0,7){ // Use the combined magic_dx/dy arrays
			ll fx=x+magic_dx[i];
            ll fy=y+magic_dy[i];

			// Check boundaries
			if(fx<1 || fx>N || fy<1 || fy>M) continue;
            // Can use magic on '#' or '.'

            // If we found a path with lower cost (next_cost)
			if(vis[fx][fy] > next_cost){
				vis[fx][fy]=next_cost;
				q.push_back({next_cost, fx, fy}); // Push to BACK for cost 1
			}
		}
	}

    // Output result
    if (vis[C][D] == INF) {
        // Depending on problem statement, output -1 or the INF value if unreachable
        // Sticking to original behavior: print the value in vis[C][D]
        cout << -1 << "\n"; // Common practice if unreachable needs specific output
    } else {
	    cout<<vis[C][D]<<"\n";
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T; // Uncomment if there are multiple test cases
	// while(T--){
		// solve();
	// }
	solve(); // Call solve once if only one test case
	return 0;
}

https://atcoder.jp/contests/abc400/submissions/64575744

堆优化源代码

// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
ll kx[4]={2,0,-2,0};
ll ky[4]={0,-2,0,2};

struct cmp{
	bool operator()(arr a,arr b){
		return a[0]>b[0];
	}
};

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>maze[i][j];
			vis[i][j]=INF;
		}
	}
	cin>>A>>B>>C>>D;
	priority_queue<arr,vector<arr>,cmp> q;
	q.push({0,A,B});
	vis[A][B]=0;
	while(!q.empty()){
		ll cnt=q.top()[0],x=q.top()[1],y=q.top()[2];
		q.pop();
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt) continue;
			if(maze[fx][fy]=='#') continue;
			vis[fx][fy]=cnt;
			q.push({cnt,fx,fy});
		}
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt+1) continue;
			vis[fx][fy]=cnt+1;
			q.push({cnt+1,fx,fy});
		}
		FOR(i,0,3){
			ll fx=x+kx[i],fy=y+ky[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<=cnt+1) continue;
			vis[fx][fy]=cnt+1;
			q.push({cnt+1,fx,fy});
		}
	}
	cout<<vis[C][D]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc400/submissions/64575744
*/

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

zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值）

Posted on 2025-04-04 Edited on 2026-04-06

思路讲解

原来是想用zkw线段树写P1253，但是zkw写懒标记顺序不可调换的题目还是比较难的，我们要顺势而为，这个写zkw就是为了简单，写着反而复杂就干脆不写了。

参考讲解

https://www.cnblogs.com/Judge/p/9514862.html

https://www.cnblogs.com/zsc985246/p/16112689.html

参考这段建树程序

inline void build(){
	for(M=1;M<=N;M<<=1);
	for(int i=M+1;i<=M+1+N;++i){
		cin>>tr[i];
	}
	for(int i=M-1;i;--i){
		tr[i]=max(tr[i<<1],tr[i<<1|1]);
		// 相当于子节点里装的值需要不断+母节点的值+母母节点的值+...+根节点的值
		// 才是真实的值，这样子可以比较好的实现bottom-up修改
		tr[i<<1]-=tr[i],tr[i<<1|1]-=tr[i];
	}
}

这个线段树（求最大值的话）子节点里装的值需要不断+母节点的值+母母节点的值+…+根节点的值才是真实的值，这样子可以比较好的实现bottom-up修改。

加法用这套东西是没有问题的，但容易发现，覆盖用这套操作会稍微有点问题。

https://blog.csdn.net/weixin_43960287/article/details/108246164

看过了，这个问题基本上可以说无解了。

AC代码

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

307. 区域和检索 - 数组可修改（zkw线段树单点修改区间查询）

Posted on 2025-04-04 Edited on 2026-04-06

思路讲解

参考题解以及视频讲解

【数据结构扩展(二) --线段树 (普通+zkw)】【精准空降到 18:48】 https://www.bilibili.com/video/BV1gy4y1D7dx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1128

https://www.cnblogs.com/Judge/p/9514862.html

AC代码

https://leetcode.cn/problems/range-sum-query-mutable/submissions/618952189

class NumArray {
public:
    typedef long long ll;
    vector<ll> tree;
    ll N;
    void update(int index, int val) {
        ll diff=val-tree[index+N];
        for(int i=index+N;i>0;i>>=1){
            tree[i]+=diff;
        }
    }
    int sumRange(int left, int right) {
        ll res=0;
        for(int i=left+N,j=right+N;i<=j;i>>=1,j>>=1){
            if(i%2==1) res+=tree[i++];
            if(j%2==0) res+=tree[j--];
        }
        return res;
    }
    NumArray(vector<int>& nums) {
        // for(int i=0;i<nums.size();++i){
        //     lnum.push_back(nums[i]);
        // }
        N=nums.size();
        tree.resize(2*N+5,0);
        for(int i=0;i<nums.size();++i){
            update(i,nums[i]);
        }
        // for(int i=0;i<tree.size();++i){
        //     cout<<i<<": "<<tree[i]<<"\n";
        // }
    }
    
};

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

ABC-397-F - Variety Split Hard

Posted on 2025-04-03 Edited on 2026-04-06

思路讲解

题意就是把一个序列三分，然后求最大种类数之和

参考题解

【AtCoder 初学者竞赛 397比赛讲解（ABC397）】【精准空降到 30:17】 https://www.bilibili.com/video/BV1eMQaYEEXa/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1817

说实话，在看题解之前，我是不会想到这种方法的，毕竟就算枚举 $i，j$ 也需要 $O（n^2）$ ，加快验证过程也没有什么意义。

首先，我们有C题的经验，prei和sufj+1我们都知道

然后不能同时枚举i，j，我们不妨只枚举j（无所谓i，j）

这个怎么寻找突破口那？

容易发现，这个#[i+1,j]是否需要+1的起始位置就是aj+1上一次出现的位置，即 $las_{a_{j+1}}$ 。

zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值）

想着用zkw线段树解决，但还是算了，就普通线段树吧。

然后一定要想清楚，按照我的编码方式j不需要现在加，因为包括在了las[j]。需要加的其实是A[j-1]，las[j-1]。

	FOR(j,3,N){
		// 由于j是确定的，利用离线思想
		// 线段树里存的相当于pre[i]+#[i+1,j-1]（j为目前的j）
		if(las[A[j-1]]==0){
			add(1,1,j-2,1);
		}else{
			add(1,las[A[j-1]],j-2,1);	// 加到j-2就够了，j-1的时候该点以囊入pre
		}
		ans=max(ans,cntr[j]+query(1,1,j-2));
		las[A[j-1]]=j-1;
// #ifdef LOCAL
	// cerr<<j<<"\n";
    // FOR(i,1,4*N){
    	// cerr<<i<<"--l:"<<tr[i].l<<" r:"<<tr[i].r<<" val:"<<tr[i].val<<"\n";
    // }
    // cerr<<"\n";
// #endif
	}
	cout<<ans<<"\n";
}

AC代码

https://atcoder.jp/contests/abc397/submissions/64623246

// Problem: F - Variety Split Hard
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
bool vis[MAXN];
bool visr[MAXN];
ll cnt[MAXN],cntr[MAXN];

struct TREE{
	ll l=0,r=0,val=-INF;
}tr[MAXN*4];

ll lazy[MAXN*4];

inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}

inline void pushdown(ll node){
	// 这句话还是重要的，防止RE
	if(tr[node].l==tr[node].r) return;
	if(lazy[node]!=0){
		tr[ls(node)].val+=lazy[node];
		tr[rs(node)].val+=lazy[node];
		lazy[ls(node)]+=lazy[node];
		lazy[rs(node)]+=lazy[node];
		lazy[node]=0;
	}
}
inline void pushup(ll node){
	node/=2;
	while(node){
		tr[node].val=max(tr[ls(node)].val,tr[rs(node)].val);
		node/=2;
	}
}

void add(ll node,ll l,ll r,ll val){ 
	if(r<l) return;
	if(r<tr[node].l || l>tr[node].r){
		return;
	}
	pushdown(node);
	if(l<=tr[node].l && tr[node].r<=r){
		lazy[node]+=val;
		tr[node].val+=val;
		pushup(node);
		return;
	}
	ll mid=(tr[node].l+tr[node].r)/2;
	// 只要不是和左节点一点关系都没有，我们都要进左节点
	if((r<tr[node].l || l>mid)==false) add(ls(node),l,r,val);
	if((r<mid+1 || l>tr[node].r)==false) add(rs(node),l,r,val);
}


void build(ll node,ll l,ll r){
	if(l>r){
		return;
	}
	if(l==r){
		tr[node].l=l;
		tr[node].r=r;
		tr[node].val=0;	// 用来使用
		return;
	}
	tr[node].l=l;
	tr[node].r=r;
	ll mid=l+r>>1;
	build(ls(node),l,mid);
	build(rs(node),mid+1,r);
}


ll query(ll node,ll l,ll r){
	if(r<tr[node].l || l>tr[node].r){
		return -INF;
	}
	pushdown(node);
	if(l<=tr[node].l && tr[node].r<=r){
		return tr[node].val;
	}
	ll mid=(tr[node].l+tr[node].r)/2;
	ll res=-INF;
	// 只要不是和左节点一点关系都没有，我们都要进左节点
	if((r<tr[node].l || l>mid)==false) res=max(res,query(ls(node),l,r));
	if((r<mid+1 || l>tr[node].r)==false) res=max(res,query(rs(node),l,r));
	return res;
}

ll las[MAXN];
inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>A[i];
	}
	FOR(i,1,N){
		if(!vis[A[i]]) cnt[i]=cnt[i-1]+1;
		else cnt[i]=cnt[i-1];
		vis[A[i]]=true;
	}
	ROF(i,N,1){
		if(!visr[A[i]]) cntr[i]=cntr[i+1]+1;
		else cntr[i]=cntr[i+1];
		visr[A[i]]=true;		
	}
	build(1,1,N);
	FOR(i,1,N){
		// 初始化线段树
		add(1,i,i,cnt[i]);
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<cnt[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	ll ans=0;
	// 在该j下的最好情况是suf[j]+max(pre[i]+#[i+1,j-1]) 
	// #[i+1,j-1]是指该闭区间内的数字种数
	las[A[1]]=1;	// 该值最后一次出现的位置
	// las[A[2]]=2;
	FOR(j,3,N){
		// 由于j是确定的，利用离线思想
		// 线段树里存的相当于pre[i]+#[i+1,j-1]（j为目前的j）
		if(las[A[j-1]]==0){
			add(1,1,j-2,1);
		}else{
			add(1,las[A[j-1]],j-2,1);	// 加到j-2就够了，j-1的时候该点以囊入pre
		}
		ans=max(ans,cntr[j]+query(1,1,j-2));
		las[A[j-1]]=j-1;
// #ifdef LOCAL
	// cerr<<j<<"\n";
    // FOR(i,1,4*N){
    	// cerr<<i<<"--l:"<<tr[i].l<<" r:"<<tr[i].r<<" val:"<<tr[i].val<<"\n";
    // }
    // cerr<<"\n";
// #endif
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc397/submissions/64623246
10
1 2 3 3 4 5 6 6 7 8

10

*/

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

RE是因为没加这句话

inline void pushdown(ll node){
	// 这句话还是重要的，防止RE
	if(tr[node].l==tr[node].r) return;
	if(lazy[node]!=0){
		tr[ls(node)].val+=lazy[node];
		tr[rs(node)].val+=lazy[node];
		lazy[ls(node)]+=lazy[node];
		lazy[rs(node)]+=lazy[node];
		lazy[node]=0;
	}
}

ABC-397-E - Path Decomposition of a Tree

Posted on 2025-04-02 Edited on 2026-04-06

思路讲解

总的来说就是问你这颗树能不能分解成由K个点组成的路径

哈哈，我的理解有问题，其实这个所谓的“路径”是“链”（根据形式化题意）

AC代码

https://atcoder.jp/contests/abc397/submissions/64463352

// Problem: E - Path Decomposition of a Tree
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T;
vector<ll> g[MAXN];
bool vis[MAXN];
bool Ans=true;
// bool needed[MAXN];

ll dfs(ll x){	// 如果return 0，就说明子树已经自行满足了，其他数就说明还需要K-x个点
	if(!Ans) return 0;
	vis[x]=true;
	// vector<ll> rec;
	ll sum=0;
	ll cnt=0;
	for(int i=0;i<g[x].size();++i){
		ll node=g[x][i];
		if(vis[node]) continue;
		ll lrec=dfs(node);
		if(lrec!=0) ++cnt;
		// rec.pb(lrec);
		sum+=lrec;
	}
	if(sum+1==K && cnt<=2){
		return 0;
	}
	if(sum+1<K && cnt<=1){
		return sum+1;
	}
	Ans=false;
	return 0;
}

inline void solve(){
	cin>>N>>K;
	if(K==1){
		cout<<"Yes\n";
		return;
	}
	FOR(i,1,N*K-1){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	Ans=true;
	dfs(1);
	if(Ans) cout<<"Yes\n";
	else cout<<"No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc397/submissions/64463352
*/

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

一个是没有注意到链

还有这个条件是cnt≤1

1
2
3

if(sum+1<K && cnt<=1){
	return sum+1;
}