Znzryb's Blog

CF-1022-C. Neo's Escape

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

思路讲解

就是要注意到，如果一段连续的相同的数字是不会影响结果的，因此需要把他们缩减。

AC代码

源代码

// Problem: C. Neo's Escape
// Contest: Codeforces - Codeforces Round 1022 (Div. 2)
// URL: https://codeforces.com/contest/2108/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

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

ll N,M,K,T,A[MAXN],uA[MAXN];
// unordered_map<ll,ll> Pos;

inline void solve(){
	cin>>N;
	set<ll> reaches;
	// Pos.clear();
	A[0]=0,A[N+1]=0;
	priority_queue<arr> pq;
	FOR(i,1,N){
		cin>>A[i];
		// pq.push({A[i],i});
	}
	
	ll idx=0,up=0;
	FOR(i,1,N){
		if(up!=A[i]){
			up=A[i];
			uA[++idx]=A[i];
			pq.push({A[i],idx});
		}
	}
	ll ans=0;
	while(!pq.empty()){
		ll pos=pq.top()[1];
		pq.pop();
		if(reaches.find(pos)==reaches.end()){
			++ans;
			reaches.insert(pos+1);
			reaches.insert(pos-1);
		}else{
			reaches.insert(pos+1);
			reaches.insert(pos-1);
		}
	}
	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://codeforces.com/contest/2108/submission/318060392
*/

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

https://codeforces.com/contest/2108/submission/317973413

1
3
11 10 10

Edu-CF-178-E. Unpleasant Strings

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

思路讲解

首先贪心的，我们在每个位置上总归想跳的最远，且在每个位置上都跳的最远，得到的一定是最少跳跃次数的。

那么这个每个位置上通过加一个字母能够一次跳到的最远位置怎么得到的那？其实就是所有合法字母中上一次出现的位置最远的字母的位置（如果有一个合法字母前面没出现过，那我们就认为他直接跳出去结束了）。

ROF(i,N-1,0){
	FOR(j,0,K-1){
		if(Pos[j].empty()){
			JumpFar[i]=N;
			JumpCh[i][j]=N;
		}else{
			JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			JumpCh[i][j]=Pos[j].back();
		}
	}
	Pos[S[i]-'a'].pb(i);
}

然后知道了在这个位置上最远能跳多远，那么我们知道最多要跳多少次那？可以通过记忆化搜索。

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

	ROF(i,N-1,0){
		dp[i]=dfs(i);
	}

最后这个串需要用多少位原串需要跳跃处理，否则会 $TLE$ ，最坏 $O(NQ)$ 时间复杂度。

AC代码

https://codeforces.com/contest/2104/submission/317799371

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

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>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
// ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll JumpCh[MAXN][35];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}


inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				JumpCh[i][j]=N;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
				JumpCh[i][j]=Pos[j].back();
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
// #ifdef LOCAL
    // cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
// #endif
	}
	
// #ifdef LOCAL
    // FOR(i,0,N-1){
    	// cerr<<dp[i]<<" ";
    // }
    // cerr<<"\n";
// #endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,idxs=0,bp=-INF;
		while(idxs<N){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[idxs]){
				bp=idxs;
				++idx;
				idxs=JumpCh[idxs][s[idx]-'a'];
			}else{
				idxs=JumpCh[idxs][s[idx]-'a'];
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
		
// #ifdef LOCAL
    // cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
// #endif

		cout<<dp[bp]<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2104/submission/317799371
*/

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

https://codeforces.com/contest/2104/submission/317796467

对比对部分没有优化。

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

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>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				break;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
#ifdef LOCAL
    cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
#endif
	}
	
#ifdef LOCAL
    FOR(i,0,N-1){
    	cerr<<dp[i]<<" ";
    }
    cerr<<"\n";
#endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,bp=-INF;
		FOR(i,0,N-1){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[i]){
				bp=i;
				++idx;
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
#ifdef LOCAL
    cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
#endif
		cout<<dp[bp]<<"\n";
	}
}

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

*/

Edu-CF-178-D. Array and GCD

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

思路讲解

其实思路还是很简单的，就是符合要求的一列数字，数字总和最小的就是 $2，3，5，7，11，…$

这样的一串素数数列。

证明？那么我们假设其中一个数字可以减去1，首先2不能-1（出现了1），那么其他的数字-1也不能（被2除）。

得证。

AC代码

https://codeforces.com/contest/2104/submission/317754416

源代码

// Problem: D. Array and GCD
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

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>(4e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr ll range=static_cast<ll>(7e6)+5;

ll N,M,T,A[MAXN];
ll isPrime[range+10];
vector<ll> primes;
ll primeSum[MAXN];

inline void genPrime(){
	FOR(i,2,range) {isPrime[i]=true;}
	// range 范围内经过估算，有4.4e5个素数
	for(int i=2;i*i<=range;++i){
		if(!isPrime[i]) continue;
		for(int j=2*i;j<=range;j+=i){
			isPrime[j]=false;
		}
	}
	for(int i=2;i<=range;++i){
		if(isPrime[i]) primes.pb(i);
	}
	// assert(SZ(primes)>MAXN);
}

inline bool check(ll x){
	if(x==N-1) return true;
	ll res=0;
	FOR(i,1+x,N){
		res+=A[i];
	}
	ll stand=0;
	ll len=N-x;
	if(len==2){
		stand=5;
	}else{
		FOR(i,0,len-1){
			stand+=primes[i];
		}
	}
	
// #ifdef LOCAL
    // cerr << "len:"<<N-x<<" stand:"<<stand << '\n';
// #endif
	if(res>=stand) return true;
	return false;
}

inline void solve(){
	cin>>N;
	FOR(i,1,N){
		cin>>A[i];
	}
	sort(A+1,A+1+N);
	ll l=0,r=N-1;
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
	while(l<r){
		ll mid=l+r>>1;
// #ifdef LOCAL
    // cerr << "OK2" << '\n';
// #endif
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	genPrime();
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2104/submission/317754416

*/

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

CF-1021-D. Baggage Claim

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

思路讲解

无向图边的重定向问题。

只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）

其实比较难的就是想样例4，多个块共用一个块，这个时候怎么办？

把他转化为图论问题，其实就是问这张图上有多少条 $1→5$ 路径？

这个有几种路径怎么算那？这其实根本用不到什么最小割，最大流什么的，割是用来解决不相交路径数量问题的。直接上dfs就行。

唉，这个直接暴力会TLE，毕竟数量太多了，一个一个统计一定会TLE的。

https://www.luogu.com.cn/problem/solution/CF2097B

其实想到见图了可以更进一步，直接将约束和点抽象为图。

主要就是把这个问题转化为了无向图方向确定问题。

AC代码

https://codeforces.com/contest/2097/submission/318339701

源代码

// Problem: B. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 1)
// URL: https://codeforces.com/contest/2097/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

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

ll N,M,K,T;
ll fa[MAXN*2];
ll Ind[1010][1010];
ll rNode[MAXN*2],rEdge[MAXN*2];
bool vis[MAXN*2];
ll selfLoop[MAXN*2];

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


ll find(ll x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(x==y) {
		// 增加了一个自环，也算是加了
		rEdge[fax]+=1;
		selfLoop[fax]=true;
#ifdef LOCAL
    cerr << "--------selfLoop-----" << '\n';
#endif
		return;
	}else if(fax==fay){
		rEdge[fay]+=1;
		return;
	}
	rNode[fay]+=rNode[fax];
	rEdge[fay]+=rEdge[fax]+1;
	selfLoop[fay]|=selfLoop[fax];
	fa[fax]=fay;
}

inline void solve(){
	cin>>N>>M>>K;
	// init
	FOR(i,0,K*4){
		fa[i]=i;
		rNode[i]=1;
		rEdge[i]=0;
		vis[i]=false;
		selfLoop[i]=false;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	vector<arr> xy;
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=0;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		vector<ll> inds;
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			inds.pb(ind);
		}
		FOR(i,0,SZ(inds)-2){
			ll ind1=inds[i],ind2=inds[i+1];
#ifdef LOCAL
    cerr << "ind1:"<<ind1<<" ind2:"<<ind2 << '\n';
#endif
			merge(ind1,ind2);
		}
		if(SZ(inds)==1){
#ifdef LOCAL
    cerr << "selfLoop:"<<inds.back() << '\n';
#endif
			merge(inds.back(),inds.back());
		}
	}
	ll ans=1;
	FOR(i,1,tot){
		ll fai=find(i);
		if(vis[fai]) continue;
		vis[fai]=true;
		ll rem=rNode[fai]-rEdge[fai];
#ifdef LOCAL
    cerr <<"fai:"<< fai<<" rem:"<<rem << '\n';
#endif
		if(rem==1){	// 树，有一个点入度为0，枚举这个点，就有N种选择
			ans*=rNode[fai];
			ans%=mod;
		}else if(rem==0){
			if(selfLoop[fai]){
				ans*=1;
			}else{
				ans*=2;
				ans%=mod;
			}
		}else{
			cout<<0<<"\n";
			return;
		}
	}
	ans%=mod;
	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://codeforces.com/contest/2097/submission/318339701
*/

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

TLE

毕竟我的算法是去试每一条路径

https://codeforces.com/contest/2098/submission/317475573

源代码

// Problem: D. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 2)
// URL: https://codeforces.com/contest/2098/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

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

ll N,M,K,T,A[MAXN];

vector<ll> g[MAXN*4];
ll Ind[1010][1010];
bool vis[MAXN*4];

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

ll ans=0;

void dfs(ll x,ll las){
	if(vis[x]) return;
	if(las+1!=x && x<=K) return;
	if(x==K){
		++ans;
		ans%=mod;
		return;
	}
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll fx=g[x][i];
		if(vis[fx]) continue;
		// if(fx<=K){
			// if(x<=K){
				// if(x+1!=fx) continue;
			// }
		// }
		// 如果说进入的点是我人为加出来的，需要延续上一个不是人为加出的点
// #ifdef LOCAL
    // cerr<<"x:"<<x<<" fx:"<<fx<<" las:"<<las<<"\n";
//     
// #endif
		if(x>K) dfs(fx,las);
		else dfs(fx,x);
		vis[fx]=false;

	}
}

inline void solve(){
	cin>>N>>M>>K;
	vector<arr> xy;
	// 只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）
	// initialize
	FOR(i,0,K*4){
		g[i].clear();
		vis[i]=false;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=K+1;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			g[i].pb(ind);
			g[ind].pb(i+1);
		}
	}
	
// #ifdef LOCAL
	// cerr<<"T:"<<T<<"\n";
    // FOR(i,0,K*4){
    	// // if(g[i].empty()) break;
    	// cerr<<i<<":";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // cerr<<"\n";
// #endif
	ans=0;
	dfs(0,-1);
	ans%=mod;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2098/submission/317475573

*/

调试中一个样例出的一些问题

样例

通过暴力程序dfs我们得知，这个点直到（2，3）点，仍然有11条路径
但到了（1，4）点，我们就只有2条路径了。
因为有一个始源路径就是（2，5）->（3，3）->（3，4）,（2，3）->（1，4）也需要
所以说问题出在passNum的统计上，（3，3）作为始祖路径之一，早已不是只有一条路径通过了

问题代码

// Problem: D. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 2)
// URL: https://codeforces.com/contest/2098/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

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

ll N,M,K,T,A[MAXN];

vector<ll> g[MAXN*4];
ll Ind[1010][1010];
// bool vis[MAXN*4];
ll passNum[MAXN*4];

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

inline void solve(){
	cin>>N>>M>>K;
	vector<arr> xy;
	// 只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）
	// initialize
	FOR(i,0,K*4){
		g[i].clear();
		// vis[i]=false;
		passNum[i]=0;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=K+1;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){	// 节点加入算法
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			g[i].pb(ind);
			g[ind].pb(i+1);
		}
	}
	
	ll ans=1;
	FOR(i,0,K-1){
		ll needLos=0;
		FOR(j,0,SZ(g[i])-1){
			ll node=g[i][j];	// 超出K的节点，通过上面的节点加入算法，可以保证该点一定有用
			// assert(node>=K);
			needLos+=passNum[node];
			passNum[node]+=(ans-passNum[node]);
		}
		ans=SZ(g[i])*ans-needLos;
#ifdef LOCAL
	
    cerr <<"i:"<<i<< " ans:"<<ans<<" SZ:"<<SZ(g[i])<<" needLos:"<<needLos << '\n';
#endif
	}
	
// #ifdef LOCAL
	// cerr<<"T:"<<T<<"\n";
    // FOR(i,0,K*4){
    	// // if(g[i].empty()) break;
    	// cerr<<i<<":";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // cerr<<"\n";
// #endif

	ans%=mod;
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2098/submission/317475573
1
5 5 11
2 5
3 4
4 5
5 4
4 3
5 2
4 1
3 2
2 1
1 2
2 3
1 4
通过暴力程序dfs我们得知，这个点直到（2，3）点，仍然有11条路径
但到了（1，4）点，我们就只有2条路径了。
因为有一个始源路径就是（2，5）->（3，3）->（3，4）,（2，3）->（1，4）也需要
所以说问题出在passNum的统计上，（3，3）作为始祖路径之一，早已不是只有一条路径通过了

*/

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(x==y) {
		// 增加了一个自环，也算是加了
		rEdge[fax]+=1;
		selfLoop[fax]=true;
#ifdef LOCAL
    cerr << "--------selfLoop-----" << '\n';
#endif
		return;
	}else if(fax==fay){  // 这段斜体加粗要加上用来特判即不是自环，但在同一联通块的情况
		rEdge[fay]+=1;
		return;
	}
	rNode[fay]+=rNode[fax];
	rEdge[fay]+=rEdge[fax]+1;
	selfLoop[fay]|=selfLoop[fax];
	fa[fax]=fay;
}

CF-1020-F. Goblin

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

思路讲解

终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。

比如这张图中是包含9个。

那么唯一的问题就是，这张生成网格太大了，最多可能有4e10个块。这就有点恐怖了。

如果说跑dfs，bfs， $O(n^2)$ 无法通过此题。

唉，其实像这种题反而难想，因为暴力太容易想到，但是暴力的优化就不是很容易了，可能要另起炉灶了。

那么就直接使用dp的类似思路，一列一列的推过去，然后就做出来了？一次AC！

推的代码

// 终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。
if(S[1]=='0') Cnt[1][0]=0,Cnt[1][1]=N-1;
else Cnt[1][0]=1;
FOR(i,2,N){
	if(S[i]=='0'){
		Cnt[i][0]=i-1;
		Cnt[i][1]=N-i;
		if(S[i-1]=='1'){ // 10情况，上半部分相连
			Cnt[i][0]+=Cnt[i-1][0];
		}else{      // 00 情况，上半部分和上半部分连，下半部分和下半部分连
			Cnt[i][0]+=Cnt[i-1][0];
			Cnt[i][1]+=Cnt[i-1][1];
		}
	}else{
		Cnt[i][0]=1;
		if(S[i-1]=='0'){ // 01情况，和下半部分连
			// 就是一列分为上下（如果是0）的话
			Cnt[i][0]+=Cnt[i-1][1];	// 和下面联通
		}
		// 如果是1直接就不联通了，开摆
	}
}

AC代码

源代码

// Problem: F. Goblin
// Contest: Codeforces - Codeforces Round 1020 (Div. 3)
// URL: https://codeforces.com/contest/2106/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#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())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

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;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T;
char S[MAXN];
ll Cnt[MAXN][3];

inline void solve(){
	cin>>N;
	FOR(i,0,N+5) Cnt[i][0]=0,Cnt[i][1]=0;
	FOR(i,1,N){
		cin>>S[i];
	}
	// 终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。
	if(S[1]=='0') Cnt[1][0]=0,Cnt[1][1]=N-1;
	else Cnt[1][0]=1;
	FOR(i,2,N){
		if(S[i]=='0'){
			Cnt[i][0]=i-1;
			Cnt[i][1]=N-i;
			if(S[i-1]=='1'){
				Cnt[i][0]+=Cnt[i-1][0];
			}else{
				Cnt[i][0]+=Cnt[i-1][0];
				Cnt[i][1]+=Cnt[i-1][1];
			}
		}else{
			Cnt[i][0]=1;
			if(S[i-1]=='0'){
				// 就是一列分为上下（如果是0）的话
				Cnt[i][0]+=Cnt[i-1][1];	// 和下面联通
			}
			// 如果是1直接就不联通了，开摆
		}
	}
	ll ans=0;
	FOR(i,1,N){
		ans=max({Cnt[i][1],ans,Cnt[i][0]});
	}
	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://codeforces.com/contest/2106/submission/317269384
*/