Znzryb's Blog

Edu-180-D. Reachability and Tree

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

思路讲解

那么注意到入度为2才是这个修改的充要条件，因为这样子修改边的朝向保证了只会增加一个好对数量。

auto dfs=[&](auto &&dfs,ll u,ll alte)->void{
	vis[u]=true;
	FOR(i,0,SZ(g[u])-1){
		ll v=g[u][i];
		if(vis[v]) continue;
		bool isop=false;
		// 那么注意到入度为2才是这个修改的充要条件
		if(SZ(g[u])==2 && isM==false){	
			alte=1-alte;
			if(alte){
				ans.pb({v,u});
			}else{
				ans.pb({u,v});
			}
			isM=true;
			isop=true;
		}else{
			if(alte){
				ans.pb({v,u});
			}else{
				ans.pb({u,v});
			}
		}
		dfs(dfs,v,1-alte);
		if(isop) alte=1-alte;
	}
};

AC代码

https://codeforces.com/contest/2112/submission/325852721

源代码

// Problem: D. Reachability and Tree  D.可达性和树
// Contest: Codeforces - Educational Codeforces Round 180 (Rated for Div. 2)教育 Codeforces 第 180 轮（评级为 Div. 2）
// URL: https://codeforces.com/contest/2112/problem/D
// Memory Limit: 256 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;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
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;
	init();
	vector<vector<ll> > g(N+5);
	FOR(i,1,N-1){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	// if(N<=2){
		// cout<<"NO\n";
		// return;
	// }
	vector<arr2> ans;
	vector<bool> vis(N+5,false);
	bool isM=false;
	vector<bool> isye(N+5,0);
	
	// ll ye=0;
	// auto yezi=[&](auto &&yezi,ll u)->void{
		// if(ye!=0) return;
		// vis[u]=true;
		// bool isye=true;
		// FOR(i,0,SZ(g[u])-1){
			// ll v=g[u][i];
			// if(vis[v]) continue;
			// yezi(yezi,v);
			// isye=false;
		// }
		// if(isye) ye=u;
	// };
	auto dfs=[&](auto &&dfs,ll u,ll alte)->void{
		vis[u]=true;
		FOR(i,0,SZ(g[u])-1){
			ll v=g[u][i];
			if(vis[v]) continue;
			bool isop=false;
			// 那么注意到入度为2才是这个修改的充要条件
			if(SZ(g[u])==2 && isM==false){	
				alte=1-alte;
				if(alte){
					ans.pb({v,u});
				}else{
					ans.pb({u,v});
				}
				isM=true;
				isop=true;
			}else{
				if(alte){
					ans.pb({v,u});
				}else{
					ans.pb({u,v});
				}
			}
			dfs(dfs,v,1-alte);
			if(isop) alte=1-alte;	// 再改回来
		}
	};
	// yezi(yezi,1);
	// vis.assign(N+5,0);
	// FOR(i,0,SZ(g[ye])-1){
		// isye[g[ye][i]]=true;
	// }
	dfs(dfs,1,1);
	
	// FOR(i,0,SZ(ans)-1){
		// ll u=ans[i][0],v=ans[i][1];
		// if(is1[u] && v!=1){
			// swap(ans[i][0],ans[i][1]);
// #ifdef LOCAL
    // debug(u);debug(v);
// #endif
			// isM=true;
			// break;
		// }
	// }
	if(!isM){
		cout<<"NO\n";
		return;
	}
	cout<<"YES\n";
	FOR(i,0,SZ(ans)-1){
		ll u=ans[i][0],v=ans[i][1];
		cout<<u<<" "<<v<<"\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……）

CF-1030-D1. Red Light, Green Light (Easy version)

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

思路讲解

用稍微聪明一点的方法去模拟。

AC代码

源代码

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

CF-1031-C. Smilo and Minecraft（二维前缀和）

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

思路讲解

简单来说，就是第一次炸了以后还能存活下来的金块，一定能活下来。

那么形式化的理解就是说第一次炸完以后，剩下的空间就足够其他炸弹进行一些精细操作了。

然后枚举+二维前缀和，就可以用二维前缀和来求。

FOR(i,1,N){
	FOR(j,1,M){
		Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]+(G[i][j]=='g')-Sum[i-1][j-1];
	}
}
ll ans=0;
FOR(i,1,N){
	FOR(j,1,M){
		if(G[i][j]=='.'){
			ll xl=max(i-K+1,1ll),xr=min(i+K-1,N),yl=max(1ll,j-K+1),yr=min(M,j+K-1);
			ll lans=Sum[xr][yr]+Sum[xl-1][yl-1]-Sum[xl-1][yr]-Sum[xr][yl-1];
			ans=max(ans,Sum[N][M]-lans);
		}
	}
}

AC代码

https://codeforces.com/contest/2113/submission/325681423

源代码

// Problem: C. Smilo and Minecraft  C. Smilo 和 Minecraft
// Contest: Codeforces - Codeforces Round 1031 (Div. 2)Codeforces 第 1031 轮（第 2 组）
// URL: https://codeforces.com/contest/2113/problem/C
// Memory Limit: 256 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;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(5e2)+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;
char G[MAXN][MAXN];
ll Sum[MAXN][MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N>>M>>K;
	init();
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>G[i][j];
		}
	}
	FOR(i,1,N){
		FOR(j,1,M){
			Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]+(G[i][j]=='g')-Sum[i-1][j-1];
		}
	}
#ifdef LOCAL
    FOR(i,0,N){
		FOR(j,0,M){
			cerr<<Sum[i][j]<<" ";
		}
		cerr<<"\n";
	}
#endif
	ll ans=0;
	FOR(i,1,N){
		FOR(j,1,M){
			if(G[i][j]=='.'){
				ll xl=max(i-K+1,1ll),xr=min(i+K-1,N),yl=max(1ll,j-K+1),yr=min(M,j+K-1);
				ll lans=Sum[xr][yr]+Sum[xl-1][yl-1]-Sum[xl-1][yr]-Sum[xr][yl-1];
#ifdef LOCAL
	debug(Sum[xl-1][yr]);debug(Sum[xl][yr-1]);
    debug(i);debug(j);debug(xl);debug(yl);debug(yr);debug(xr);debug(lans);
#endif
				ans=max(ans,Sum[N][M]-lans);
			}
		}
	}
	cout<<ans<<"\n";
}

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

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

Starters 188-Swaps in a String

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

思路讲解

我感觉可以搞dp（结果看了第二个样例觉得不太行）。

那么其实就是局部最优可以推得全局最优，非常经典的贪心。

那么为什么说这个B朝右朝左选一个最大的就最优了？不会相互影响吗？

那我们来看一个你认为会相互影响的，可以看到，这个是矛盾的。所以不会相互影响

FOR(i,1,N){
	++cnt[S[i]-'A'];
	if(S[i]=='B'){
		L[i]=cnt[0];
	}else if(S[i]=='C'){
		cnt[0]=0;
	}else{
		
	}
}
cnt.assign(10,0);
ROF(i,N,1){
	++cnt[S[i]-'A'];
	if(S[i]=='B'){
		R[i]=cnt[2];
	}else if(S[i]=='A'){
		cnt[2]=0;
	}else{
		
	}
}
FOR(i,1,N){
	if(S[i]=='B'){
		ans+=max(L[i],R[i]);
	}
}

AC代码

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

源代码

// Problem: Swaps in a String
// Contest: CodeChef - START188
// URL: https://www.codechef.com/problems/SWAPSTR?tab=statement
// 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;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
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;
char S[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>S[i];
	}
	vector<ll> L(N+5,0),R(N+5,0),cnt(10,0);
	ll ans=0;
	FOR(i,1,N){
		++cnt[S[i]-'A'];
		if(S[i]=='B'){
			L[i]=cnt[0];
		}else if(S[i]=='C'){
			cnt[0]=0;
		}else{
			
		}
	}
	cnt.assign(10,0);
	ROF(i,N,1){
		++cnt[S[i]-'A'];
		if(S[i]=='B'){
			R[i]=cnt[2];
		}else if(S[i]=='A'){
			cnt[2]=0;
		}else{
			
		}
	}
	FOR(i,1,N){
		if(S[i]=='B'){
			ans+=max(L[i],R[i]);
		}
	}
	cout<<ans<<"\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.codechef.com/viewsolution/1167971455

*/

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

写了一个下午，一直WA，思路错了。

源代码

// Problem: Swaps in a String
// Contest: CodeChef - START188
// URL: https://www.codechef.com/problems/SWAPSTR?tab=statement
// 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;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
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;
char S[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>S[i];
	}
	vector<ll> cnt(10,0);
	ll ans=0;
	vector<bool> vis(N+5,false);
	set<ll> s;vector<ll> wp;
	// just process the part of string like "AABBCC" "ABC" "AABC"
	// make these parts vis[i]=true;
	FOR(i,1,N){		
		if(s.empty() && S[i]!='A'){
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(SZ(s)==1 && S[i]=='C'){
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(SZ(s)==2 && S[i]=='A') {
			s.clear();wp.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			s.insert('A'),++cnt[S[i]-'A'];
			continue;
		}
		if(SZ(s)==3 && S[i]!='C'){
			s.clear();
			ans+=max(cnt[0]*cnt[1],cnt[1]*cnt[2]);
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			if(S[i]=='A') s.insert('A'),++cnt[S[i]-'A'];
			FOR(i,0,SZ(wp)-1){
				vis[wp[i]]=true;
			}
			wp.clear();
			continue;
		}
		s.insert(S[i]);
		wp.pb(i);
		++cnt[S[i]-'A'];
	}
	if(SZ(s)==3){
		FOR(i,0,SZ(wp)-1){
			vis[wp[i]]=true;
		}
		ans+=max(cnt[0]*cnt[1],cnt[1]*cnt[2]);
	}
	
#ifdef LOCAL
    FOR(i,1,N){cerr<<vis[i];}
    cerr<<"\n";
    debug(cnt[0]);debug(cnt[1]);debug(cnt[2]);
    debug(ans);
#endif
	cnt.assign(10,0);
	s.clear();
	// process part of string like "ABAB" "AB" "AABB"
	ROF(i,N,1){
		if(vis[i]){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='C'){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='A'){
			ans+=cnt['B'-'A'];
		}
		++cnt[S[i]-'A'];
	}
	cnt.assign(10,0);
	ROF(i,N,1){
		if(vis[i]){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		if(S[i]=='A'){
			s.clear();
			cnt[0]=0;cnt[1]=0;cnt[2]=0;
			continue;
		}
		vis[i]=true;
		if(S[i]=='B'){
			ans+=cnt['C'-'A'];
		}
		++cnt[S[i]-'A'];
	}
#ifdef LOCAL
    debug(ans);
    FOR(i,0,3){
    	cerr<<cnt[i]<<" ";
    }
    cerr<<"\n";
#endif
	cout<<ans<<"\n";
}

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

1
4
AABC

*/

Starter 189-Avoid Primes

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

思路讲解

~~主要的收获就是打表~~

ll Ans[MAXN]={0,2,1,3,5,4};

最重要的就是想出来这个，让3，5靠在一起，这样就直接搞定了，后面的构造是很容易的。

AC代码

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

源代码

// Problem: Avoid Primes
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/AVOIDPRIME
// 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];
/*

*/
struct PRIME{		// 1299709 结构体可以命名为pr 一般在全局定义
// AC https://www.luogu.com.cn/record/221212624  (uva 上面的一道题目)
	int n;
	vector<ll> primes;
	vector<bool> isprime;
	PRIME(int n_){
		n=n_;
		isprime.resize(n+5,true);
		isprime[1]=false;isprime[0]=false;
		for(int i=2;i*i<=n;++i){
			if(isprime[i]){
				for(int j=2;j*i<=n;++j){
					isprime[i*j]=false;
				}
			}
		}
		for(int i=2;i<=n;++i){
			if(isprime[i]) primes.pb(i);
		}
	}
};
PRIME pr(MAXN);
ll Ans[MAXN]={0,2,1,3,5,4};
bool isUse[MAXN]={1,1,1,1,1,1};
inline void init(){
	FOR(i,6,N) Ans[i]=0;//isUse[i]=false;
}
// vector<vector<ll> > g={{0},{1,2},{2,1,3},{2,1,3,4},{2,1,3,4,5},{2,1,3,6,4,5},{2,1,3,4,6,4,7}};
inline void solve(){
	cin>>N;
	init();
	// f(p) 就是指的是可以让min(Pi,Pi+1)=素数的i的数量
	
	// if(N>=5) Ans[N]=5,isUse[5]=true,Ans[N-1]=4,isUse[4]=true;
	if(N==2){
		cout<<"2 1\n";return;
	}else if(N==3){
		cout<<"2 1 3\n";return;
	}else if(N==4){
		cout<<"2 1 3 4\n";
		return;
	}
	deque<ll> q;
	FOR(i,3,N){
		ll p=pr.primes[i];
		if(p>N) break;
		q.pb(p);
	}
	ll idx=6;
	FOR(i,6,N){
		if(i%2==0 && q.empty()==false)Ans[i]=q.front(),q.pop_front();
		else{
			while(pr.isprime[idx]){
				++idx;
			}
			Ans[i]=idx;
			++idx;
		}
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

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

*/