Znzryb's Blog

ABC-411-E - E [max]

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

思路讲解

在竞技编程中，对于求解概率或期望值的问题，通常可以运用以下技巧：与其求某个最大值与某个特定值重合的概率，不如求该最大值小于或等于该特定值的概率。这个技巧也适用于这个问题：

说实话，这个我确实想到了，但是这个想法被我pass了。其实不应该忽视求什么比较容易的想法的，或者说想到了一些可以求的量，应该去想怎么样。

那么注意到那，我们可以先求概率，接着再求期望，那么P(K)表示≤k最大值小于等于K的概率

这个就是Pk-1和Pk的关系，那么我们现在的重点就是说我们如何快速计算这个，快速完成递推那？

那么这个办法就有很多，我选择是使用优先队列。

AC代码

https://atcoder.jp/contests/abc411/submissions/66998392

源代码

// Problem: E - E [max]
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Summer (AtCoder Beginner Contest 411)
// URL: https://atcoder.jp/contests/abc411/tasks/abc411_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=998244353;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN][10];
/*

*/
inline void init(){
	
}
ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
inline void solve(){
	cin>>N;
	init();
	vector<ll> li;
	li.pb(-INF);
	priority_queue<arr2> pq;
	FOR(i,1,N){
		FOR(j,1,6){
			cin>>A[i][j];
			li.pb(A[i][j]);
			pq.push({A[i][j],i});
		}
	}
	sort(all(li));
	li.resize(unique(all(li))-li.begin());
	ll lsz=SZ(li)-1;
	vector<arr2> dp(lsz+5,{0,0});		// dp[i]指的是max值大于i的概率（i是经过离散化的）
	dp[lsz][0]=1,dp[lsz][1]=1;
	vector<ll> cnt(N+5,6);
	vector<ll> org(N+5,0);
	ROF(_,lsz-1,1){
		ll val=li[_+1];ll fac1=1,fac2=1;
		vector<ll> wp;
		while(pq.empty()==false && pq.top()[0]==val){
			ll id=pq.top()[1];
			pq.pop();
			org[id]=max(cnt[id],org[id]);
			cnt[id]--;
			wp.pb(id);
		}
		sort(all(wp));wp.resize(unique(all(wp))-wp.begin());
		FOR(i,0,SZ(wp)-1){
			ll id=wp[i];	// 含有k的面<=k-1的面数
			fac1*=cnt[id];fac1%=mod;
			fac2*=org[id];fac2%=mod;
			org[id]=0;
		}
		// 分子
		dp[_][0]=dp[_+1][0]*fac1%mod;
		dp[_][1]=dp[_+1][1]*fac2%mod;	// 分母
#ifdef LOCAL
    debug(_);
    debug(dp[_][0]);
    debug(dp[_][1]);
    debug(fac1);debug(fac2);debug(val);
#endif
	}
	ll ans=0;
	dp[0][1]=1;	// 避免分母为0导致问题
	ROF(i,lsz,1){
		ll lans=0;
		ll fac1=dp[i][0]*dp[i-1][1]-dp[i-1][0]*dp[i][1];fac1%=mod;
		ll fac2=dp[i][1]*dp[i-1][1];fac2%=mod;
#ifdef LOCAL
	cerr<<"---------\n";
    debug(fac1);debug(fac2);
#endif
		fac2=binpow(fac2,mod-2,mod);
		lans=fac1*fac2%mod*li[i]%mod;	// 变为期望值
		ans+=lans;ans%=mod;
	}
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
	// cout<<10*binpow(3,mod-2,mod)%mod<<"\n";
}

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

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

没有提交之前WA了几次，其实是因为溢出了，那么我们的binpow模版需要在进入前就对a进行取模。

ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	a%=mod;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

Starters 189-Number Walks

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

思路讲解

题面总结

给定一个长度为 N 的数组 A，其中 A[i] ∈ [1, K]。需要构造一个排列 B（1 到 N 的排列），使得对于所有 i ∈ [1, K]，满足 A[B[i]] = i。

对于每个起始位置 i（1 ≤ i ≤ N），求出从位置 i 开始构造满足条件的排列 B 时，相邻元素差值绝对值之和的最小值。

换句话说，要最小化 ∑|B[j] - B[j-1]|，其中 B[1] = i，且 A[B[j]] = j。

输入格式：

第一行：测试用例数 T
每个测试用例：
- 第一行：N 和 K
- 第二行：N 个整数表示数组 A

输出格式：

对于每个测试用例，输出 N 个整数，第 i 个整数表示从位置 i 开始的最小代价。

约束条件：

1 ≤ T ≤ 10³
1 ≤ K ≤ N ≤ 10⁶
1 ≤ A[i] ≤ K
保证至少存在一个满足条件的排列 B

虽然不一定选择最靠近的，但是一定是选择右端最靠近或者左端最靠近点的一侧。

这个如何证明那？

那么我们感性的理解，如果在最优序列中，再次移动需要到 j 的各种情况。

那么我们发现，这个 j 落在外面，l，r 中还是必有一个最优，落在里面那更不必多说了。

okay，那我们也算是成功减小了范围，但是还是不知道怎么做呀？~~继续读题解~~

啊哈，那么我们发现那，这其实是一个前缀dp，即状态转移只和前面一个状态相关，那么前面一个状态里只有 l 和 r，那么答案就呼之欲出了，从前面这个来转移。

那么我们用记忆化搜索，可能这个让人更好理解一点。

那么这个正难则反思想是应用于dp的，但是这个dp也有点难写，过了就行，开摆。

AC代码

https://www.codechef.com/viewsolution/1167791134

源代码

// Problem: Number Walks
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/NUMBERWALK
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N>>K;
	init();
	vector<vector<int>> g(K+5);
	FOR(i,1,N){
		cin>>A[i];
		g[A[i]].pb(i);
	}
	// 要求A[B[i]]==i ，并且使B[i]数组中的数的差值绝对值最小
	vector<ll> memo(N+5,INF);
	auto dfs=[&](auto &&dfs,ll node,ll val)->ll{
		if(memo[node]!=INF) return memo[node];
		if(val==K){
			memo[node]=0;
			return 0;
		}
		ll v=node;
// #ifdef LOCAL
   	// debug(node);debug(val);
// #endif
		auto it=lower_bound(all(g[val+1]),v);
		if(it!=g[val+1].begin()){
			auto it_=prev(it);
			ll diff=abs(*it_-v);
			ll res=dfs(dfs,*it_,val+1);
			memo[node]=min(memo[node],diff+res);
		}
		if(it!=g[val+1].end()){
			ll diff=abs(*it-v);
			ll res=dfs(dfs,*it,val+1);
			memo[node]=min(memo[node],diff+res);
		}
		return memo[node];
	};
	FOR(i,1,N){
		auto it=lower_bound(all(g[1]),i);
		ll ans=INF;
		if(it!=g[1].begin()){
			auto it_=prev(it);
			ll diff=abs(*it_-i);
			ll res=dfs(dfs,*it_,1);
			ans=min(diff+res,ans);
		}
		if(it!=g[1].end()){
			ll diff=abs(*it-i);
			ll res=dfs(dfs,*it,1);
			ans=min(diff+res,ans);
		}
		cout<<ans<<" ";
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<memo[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

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

调试的时候发现这里写错了，应该写1，我写成2了。

FOR(i,1,N){
	auto it=lower_bound(all(g[1]),i);
	ll ans=INF;
	if(it!=g[1].begin()){
		auto it_=prev(it);
		ll diff=abs(*it_-i);
		ll res=dfs(dfs,*it_,1);
		ans=min(diff+res,ans);
	}
	if(it!=g[1].end()){
		ll diff=abs(*it-i);
		ll res=dfs(dfs,*it,1);
		ans=min(diff+res,ans);
	}
	cout<<ans<<" ";
}

SP18185 GIVEAWAY - Give Away（单点修改）（纯纯的分块，享受纯粹的暴力快乐）（三倍经验）

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

思路讲解

思路就是根号分治

FOR(_,1,Q){
	ll op,a,b,c;
	cin>>op;
	if(op==0){
		cin>>a>>b>>c;
		ll ida=upper_bound(L+1,L+1+idx,a)-L;
		ida-=1;
		ll idb=upper_bound(L+1,L+1+idx,b)-L;
		idb-=1;
		ll ans=0;
		FOR(i,0,SZ(g[ida])-1){
			if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]>=c){
				++ans;
			}
		}
		if(ida!=idb){    // 注意这个地方，小心相同重复统计导致WA
			FOR(i,0,SZ(g[idb])-1){
				if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]>=c){
					++ans;
				}
			}
		}
		FOR(i,ida+1,idb-1){
			ll id=lower_bound(all(g[i]),(arr2){c,0})-g[i].begin();
			ans+=SZ(g[i])-id;
		}
		cout<<ans<<"\n";
	}else{
		cin>>a>>b;
		ll id=upper_bound(L+1,L+1+idx,a)-L;
		id-=1;
		FOR(i,0,SZ(g[id])-1){
			if(g[id][i][1]==a){
				g[id][i][0]=b;
				break;
			}
		}
		sort(all(g[id]));
	}
}

如果问小于等于c的可以这么写。

FOR(i,ida+1,idb-1){
	ll id=upper_bound(all(g[i]),(arr2){c,INF})-g[i].begin();
	ans+=id;
}

AC代码

https://www.luogu.com.cn/record/220963190

源代码

// Problem: SP18185 GIVEAWAY - Give Away
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP18185
// Memory Limit: 1495 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	cin>>N;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
	cin>>Q;
	FOR(_,1,Q){
		ll op,a,b,c;
		cin>>op;
		if(op==0){
			cin>>a>>b>>c;
			ll ida=upper_bound(L+1,L+1+idx,a)-L;
			ida-=1;
			ll idb=upper_bound(L+1,L+1+idx,b)-L;
			idb-=1;
			ll ans=0;
			FOR(i,0,SZ(g[ida])-1){
				if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]>=c){
					++ans;
				}
			}
			if(ida!=idb){
				FOR(i,0,SZ(g[idb])-1){
					if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]>=c){
						++ans;
					}
				}
			}
			FOR(i,ida+1,idb-1){
				ll id=lower_bound(all(g[i]),(arr2){c,0})-g[i].begin();
				ans+=SZ(g[i])-id;
			}
			cout<<ans<<"\n";
		}else{
			cin>>a>>b;
			ll id=upper_bound(L+1,L+1+idx,a)-L;
			id-=1;
			FOR(i,0,SZ(g[id])-1){
				if(g[id][i][1]==a){
					g[id][i][0]=b;
					break;
				}
			}
			sort(all(g[id]));
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220963190
*/

https://www.luogu.com.cn/record/220973015 双倍经验，SP3261 RACETIME - Race Against Time

源代码

// Problem: SP3261 RACETIME - Race Against Time
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP3261
// Memory Limit: 1495 MB
// Time Limit: 1240 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	cin>>N>>Q;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
	FOR(_,1,Q){
		char op;ll a,b,c;
		cin>>op;
		if(op=='C'){
			cin>>a>>b>>c;
			ll ida=upper_bound(L+1,L+1+idx,a)-L;
			ida-=1;
			ll idb=upper_bound(L+1,L+1+idx,b)-L;
			idb-=1;
			ll ans=0;
			FOR(i,0,SZ(g[ida])-1){
				if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]<=c){
					++ans;
				}
			}
			if(ida!=idb){
				FOR(i,0,SZ(g[idb])-1){
					if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]<=c){
						++ans;
					}
				}
			}
			FOR(i,ida+1,idb-1){
				ll id=upper_bound(all(g[i]),(arr2){c,INF})-g[i].begin();
				ans+=id;
			}
			cout<<ans<<"\n";
		}else{
			cin>>a>>b;
			ll id=upper_bound(L+1,L+1+idx,a)-L;
			id-=1;
			FOR(i,0,SZ(g[id])-1){
				if(g[id][i][1]==a){
					g[id][i][0]=b;
					break;
				}
			}
			sort(all(g[id]));
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220973015
*/

https://www.luogu.com.cn/record/220977711 三倍经验，UVA12003 Array Transformer

源代码

// Problem: UVA12003 Array Transformer
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA12003
// Memory Limit:  MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	ll u;
	cin>>N>>Q>>u;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
// #ifdef LOCAL
    // debug(Q);
// #endif
	FOR(_,1,Q){
		ll p,a,b,c;
		cin>>a>>b>>c>>p;
		ll ida=upper_bound(L+1,L+1+idx,a)-L;
		ida-=1;
		ll idb=upper_bound(L+1,L+1+idx,b)-L;
		idb-=1;
		ll ans=0;
		FOR(i,0,SZ(g[ida])-1){
			if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]<c){
				++ans;
			}
		}
		if(ida!=idb){
			FOR(i,0,SZ(g[idb])-1){
				if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]<c){
					++ans;
				}
			}
		}
		FOR(i,ida+1,idb-1){
			// 严格小于c
			ll id=lower_bound(all(g[i]),(arr2){c-1,INF})-g[i].begin();
			ans+=id;
		}
		// 修改部分
		ll id=upper_bound(L+1,L+1+idx,p)-L;
		id-=1;
		FOR(i,0,SZ(g[id])-1){
			if(g[id][i][1]==p){
				g[id][i][0]=u*ans/(b-a+1);
				break;
			}
		}
		sort(all(g[id]));
	}
	FOR(i,1,idx){
		sort(all(g[i]),[](const arr2 &a,const arr2 &b){return a[1]<b[1];});
		// FOR(j,0,SZ(g[i])-1){
			// if(j==SZ(g[i])-1 && i==idx) {cout<<g[i][j][0];}
			// else {cout<<g[i][j][0]<<"\n";}
		// }
		FOR(j,0,SZ(g[i])-1){
			cout<<g[i][j][0]<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220977711
*/

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

Starters 191-Coloured Array（无向图边的定方向问题）

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

思路讲解

一般来说，这种绿题图论建模都是有套路的，一般来说就是在一个联通图内匹配符合一些性质（可能匹配数量直接和V和E相关，也有可能跑一个dfs就出来了）。

我仔细看了一下，感觉可以转化为无向图边的重定向问题 CF-1021-D. Baggage Claim 。

这些是整段代码最重要的部分。其实这部分成立的原因是该子图是联通的（虽然是废话）。

那么我们可以想到一种构造方式，就是从*点（完美匹配点，若没有就从双边点向外延伸，若还没有就无所谓了）出发，然后定向，形成像树一样的形状。

ll size=fa.size(i);
ll edge=fa.edge[fa.find(i)];
ll mcc=fa.mcc[fa.find(i)];
// 现在这里的ans意思是我可以白嫖多少元素
ans+=2*mcc+min(edge,size-mcc);

AC代码

https://www.codechef.com/viewsolution/1167249816

源代码

// Problem: Coloured Array
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/COLARR7
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORS(i, a, b, step) for (int i=(a);i<=(b);i+=(step))
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
bool mc2[MAXN],exis[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N*2+5){
		A[i]=0;
	}
	FOR(i,1,N*2+5){
		mc2[i]=0;
		exis[i]=0;
	}
}
struct DSU { // 并查集
    vector < int > fa, siz, mcc, edge;
    int ln;
    DSU(int n) {
        ln = n;
        fa.resize(ln + 5, 0), siz.resize(ln + 5, 0), mcc.resize(ln+5, 0);
        edge.resize(ln+5,0);
        FOR(i, 1, n) {
            fa[i] = i;
            if(exis[i]) siz[i] = 1;
            if(mc2[i]) mcc[i]=1;
        }
    }
    int find(int x) {
        while (fa[x] != x) {
            x = fa[x];
            fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
        	edge[x]+=1;
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        mcc[x]+=mcc[y];
        edge[x]+=edge[y]+1;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
    int countFa() {
        int res = 0;
        FOR(i, 1, ln) {
            if (fa[i] == i) ++res;
        }
        return res;
    }
};
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,2*N){
		cin>>A[i];
	}
	N=2*N;
	for(int i=1;i<=N;i+=2){
		if(A[i]==A[i+1]){
			mc2[A[i]]=true;
		}
		exis[A[i]]=true,exis[A[i+1]]=true;
	}
	DSU fa(N);
	for(int i=1;i<=N;i+=2){
		fa.merge(A[i],A[i+1]);
	}
	vector<bool> vis(N+5,0);
	ll ans=0,al=0;
	FOR(i,1,N){
		if(vis[fa.find(i)]){
			continue;
		}
		vis[fa.find(i)]=true;
		ll size=fa.size(i);
		ll edge=fa.edge[fa.find(i)];
		ll mcc=fa.mcc[fa.find(i)];
		// 现在这里的ans意思是我可以白嫖多少元素
		ans+=2*mcc+min(edge,size-mcc);
#ifdef LOCAL
	debug(ans);
    debug(size);
    debug(edge);
    debug(mcc);
    debug(al);
    debug(max(0ll,min(edge,size-mcc)));
#endif
	}
	ans=N-ans;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
1
3
1 1 1 3 1 3

3
*/

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

WA https://www.codechef.com/viewsolution/1167153030

就是贪心做法，优先处理比较独特的。

显然会被相等的一些hack数据hack

1
3
1 3 2 3 1 2

3

源代码

// Problem: Coloured Array
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/COLARR7
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N*2+5){
		A[i]=0;
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,2*N){
		cin>>A[i];
	}
	N=2*N;
	vector<set<ll> > g(N);
	vector<ll> valid(N,0);
	ll ans=0;ll al=0;
	for(int i=1;i<=N;i+=2){
		if(A[i]==A[i+1]){
			if(valid[A[i]]==0){
				valid[A[i]]=1;
			}else{
				ans+=2;
			}
			al+=2;
		}else{
			g[A[i]].insert(i);g[A[i+1]].insert(i+1);
		}
	}
// #ifdef LOCAL
    // cerr <<"OK1";
// #endif
	sort(all(g),[](const set<ll> &a,const set<ll> &b){return SZ(a)<SZ(b);} );
	vector<ll> ma(N+5,0);
	FOR(i,1,N-1){	// A[]->idx
		if(g[i].empty()) continue;
		ma[A[*g[i].begin()]]=i;
	}
	FOR(i,1,N-1){
		if(g[i].empty()) continue;
		if(valid[A[*g[i].begin()]]==1) continue;
		ll bg=*g[i].begin();
		ll ne=0;
		if(bg%2==0) ne=bg-1;
		else ne=bg+1;
		g[i].erase(bg);
		g[ma[A[ne]]].erase(ne);
		ans+=1;
		al+=2;
	}
	ans+=N-al;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
1
3
1 1 1 3 1 3

3
*/

Starters 191-Grid Path (Easy/HARD)

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

思路讲解

hard版，这个题解中的每句话都值得细细品味。至少每个段落都得看，都得学。

https://www.codechef.com/problems/GRIDPATHHD?tab=solution

AC代码

https://www.codechef.com/viewsolution/1167145951

源代码

// Problem: Grid Path (Easy)
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/GRIDPATHEZ
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char A[3][MAXN];
ll dp[3][MAXN];
/*

*/
inline void init(){
	FOR(i,1,N){
		dp[1][i]=INF;
		dp[2][i]=INF;
	}
	dp[2][N+1]=0;
}
inline void solve(){
	cin>>N>>Q;
	init();
	FOR(i,1,N){
		cin>>A[1][i];
	}
	FOR(i,1,N){
		cin>>A[2][i];
	}
	ll idx=1;
	FOR(i,1,N){
		if(A[1][i]=='1'){
			dp[1][idx]=dp[1][idx-1]+i-idx;
			++idx;
		}
	}
	idx=N;
	ROF(i,N,1){
		if(A[2][i]=='1'){
			dp[2][idx]=dp[2][idx+1]+idx-i;
			--idx;
		}
	}
#ifdef LOCAL
    FOR(i,1,N){
    	cerr<<dp[1][i]<<" ";
    }
    cerr<<"\n";
    FOR(i,1,N){
    	cerr<<dp[2][i]<<" ";
    }
    cerr<<"\n";
#endif
	ll ans=INF;
	FOR(i,1,N){
		ans=min(ans,dp[1][i]+dp[2][i]);
	}
	if(ans>=INF) cout<<-1<<"\n";
	else cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

https://www.codechef.com/viewsolution/1167615239

源代码

// Problem: Grid Path (Hard)
// Contest: CodeChef - START191
// URL: https://www.codechef.com/problems/GRIDPATHHD
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char A[3][MAXN];
/*

*/
class SEG{		// 最简单的区间加减，区间和查询，单点修改线段树  
// AC https://www.luogu.com.cn/record/221021710 线段树模版
private:
	vector<ll> L,R,Add,Sum;
	void build(ll node,ll l,ll r){
		L[node]=l;R[node]=r;Add[node]=0;Sum[node]=0;
		if(l==r){
			return;
		}
		ll mid=l+r>>1;
		build(lson(node),l,mid);
		build(rson(node),mid+1,r);
	}
	void pushup(ll node){
		while(node){
			node>>=1;
			Sum[node]=Sum[lson(node)]+Sum[rson(node)];
		}
	}
	void pushdown(ll node){
		if(L[node]==R[node]) return;
		if(Add[node]==0) return;	// 非必须
		Add[lson(node)]+=Add[node];
		Sum[lson(node)]+=(R[lson(node)]-L[lson(node)]+1)*Add[node];
		Add[rson(node)]+=Add[node];
		Sum[rson(node)]+=(R[rson(node)]-L[rson(node)]+1)*Add[node];
		Add[node]=0;
	}
	bool isin(ll a,ll b,ll c,ll d){
		if(b<c || a>d) return false;
		return true;
	}
	void add(ll node,ll l,ll r,ll x){
		if(R[node]<l || L[node]>r) return;
		pushdown(node);
		if(L[node]>=l && R[node]<=r){
			Sum[node]+=(R[node]-L[node]+1)*x;
			Add[node]+=x;
			pushup(node);
			return;			// 这里一定要return，否则就重复加了
		}
		if(isin(L[lson(node)],R[lson(node)],l,r)) add(lson(node),l,r,x);
		if(isin(L[rson(node)],R[rson(node)],l,r)) add(rson(node),l,r,x);
	}
	ll query(ll node,ll l,ll r){
		// if(R[node]<l || L[node]>r) return 0;		// 这个无所谓
		pushdown(node);
		if(L[node]>=l && R[node]<=r){
			return Sum[node];
		}
		ll ret=0;
		if(isin(L[lson(node)],R[lson(node)],l,r)) ret+=query(lson(node),l,r);
		if(isin(L[rson(node)],R[rson(node)],l,r)) ret+=query(rson(node),l,r);
		return ret;		// 不要忘记return
	}
	void modify(ll node,ll p,ll x){
		pushdown(node);
		if(L[node]==p && R[node]==p){
			Sum[node]=x;
			pushup(node);
			return;
		}
		if(isin(L[lson(node)],R[lson(node)],p,p)) modify(lson(node),p,x);
		if(isin(L[rson(node)],R[rson(node)],p,p)) modify(rson(node),p,x);
	}
	ll findk(ll node,ll k){  // 返回第k个有值的下标，当然，要求线段树叶节点值是0或1
		pushdown(node);
        if(L[node]==R[node]) return L[node];
		if(Sum[lson(node)]>=k){
			return findk(lson(node),k);
		}else{
			return findk(rson(node),k-Sum[lson(node)]);
		}
	}
public:
	SEG(int n){
		if(n<=0) n=1; //  防止传入0作为大小导致RE
		L.resize(4*n);R.resize(4*n);Add.resize(4*n);Sum.resize(4*n);
		build(1,1,n);
	}
	// c++函数重载，只要参数数量不同不用担心重名
	void add(ll l,ll r,ll x){add(1,l,r,x);}	// 这样调用的时候就不需要填node了
	ll query(ll l,ll r){return query(1,l,r);}
	ll findk(ll k){return findk(1,k);}
	void modify(ll p,ll x){modify(1,p,x);}
#ifdef LOCAL		// 用来帮助debug的
    void segDe(ll node){
    	pushdown(node);
    	cerr<<L[node]<<" "<<R[node]<<" "<<Sum[node]<<"\n";
    	if(L[node]==R[node]) return;
    	segDe(lson(node));
    	segDe(rson(node));
    }
#endif
};
inline void init(){
	
}
inline void solve(){
	cin>>N>>Q;
	init();
	vector<SEG> tr;
	tr.pb(SEG(1));
	tr.pb(SEG(N));	// 维护所有
	tr.pb(SEG(N));
	tr.pb(SEG(N));	// 维护所有下标及其和
	tr.pb(SEG(N));
	vector<ll> cnt(4,0);
	FOR(i,1,N){
		cin>>A[1][i];
		tr[1].add(i,i,A[1][i]-'0');
		if(A[1][i]=='1') cnt[1]++,tr[3].modify(i,i);
	}
	FOR(i,1,N){
		cin>>A[2][i];
	}
	reverse(A[2]+1,A[2]+1+N);
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<A[2][i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	FOR(i,1,N){
		tr[2].add(i,i,A[2][i]-'0');
		if(A[2][i]=='1') cnt[2]++,tr[4].modify(i,i);
	}
// #ifdef LOCAL
	// cerr<<"C3:\n";
    // tr[3].segDe(1);
    // cerr<<"D4\n";
    // tr[4].segDe(1);
// #endif
	auto bs=[&]()->void{
		if(cnt[1]+cnt[2]<N+1){
			cout<<-1<<"\n";
			return;
		}
		ll l=N+1-cnt[2],r=cnt[1];
// #ifdef LOCAL
    // cerr << "originlr:"<<l<<" "<<r << "-------------\n";
// #endif
		while(l<r){
			ll mid=l+r+1>>1;
			//      下标 - 第mid个
			ll res=0;
// #ifdef LOCAL
    // debug(tr[1].findk(mid)-mid);
// #endif
			if(mid!=N+1-cnt[2])res=tr[1].findk(mid)-mid-tr[2].findk(N+2-mid)+(N+2-mid);
			if(res<=0){
				l=mid;
			}else{
				r=mid-1;
			}
// #ifdef LOCAL
	// debug(mid);
    // debug(res);
// #endif
		}
// #ifdef LOCAL
    // debug(l);debug(r);
// #endif
		if(l>r) l=r;
		//                        因为下面一行是被反转过的，所以说是
		// C[1]+C[2]+D[1]+D[2]+...+D[N-1]   D[N] 不需要是因为D[N]是反转之前最靠前的
		ll sumc=tr[3].query(1,tr[1].findk(l));
		ll sumd=tr[4].query(1,tr[2].findk(N+1-l));
		// (1+l)*l/2 是从1加到l的
		ll sum=sumc-(1+l)*l/2+sumd-(N+1-l+1)*(N+1-l)/2;		// sumc和sumd是下标之和
// #ifdef LOCAL
    // debug(sumc-(1+l)*l/2);
    // debug(sumd-(N+1-l+1)*(N+1-l)/2);
    // debug(l);
    // debug(cnt[1]);
    // debug(sum);
    // debug(tr[2].findk(N+1-l));
// #endif
		cout<<sum<<"\n";
	};
	bs();
	FOR(_,1,Q){
		ll x,y;
		cin>>x>>y;
		if(x==2) y=N-y+1;	// A[2] 已经被反转了
		if(A[x][y]=='1'){
			tr[x].modify(y,0);
			tr[x+2].modify(y,0);
			cnt[x]--;
			bs();
			A[x][y]='0';
		}else{
			tr[x].modify(y,1);
			tr[x+2].modify(y,y);
// #ifdef LOCAL
    // debug(y);
// #endif
			cnt[x]++;
			bs();
			A[x][y]='1';
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1167615239
*/

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

EZ不小心错了一次，实际上是INF开小了。

第186行这里容易符号写反。

https://www.codechef.com/viewsolution/1167612305

1	if(mid!=N+1-cnt[2])res=tr[1].findk(mid)-mid-tr[2].findk(N+2-mid)+(N+2-mid);