Znzryb's Blog

The 2024 Shanghai Collegiate Programming Contest G. 象棋大师（计数状元dp）

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

思路讲解

因为方向是确定的，可以从前往后推导。

for(int s=cnts-1;s>=0;--s){
	for(int i=0;i<=N;++i){
		for(int j=0;j<=N;++j){
			if(danger[s][i][j]) continue;	// danger,continue
			bitset<15> bi(s);
			// set<array<ll,2> > mas;
			// for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
			for(int k=0;k<2;++k){
				ll u=i+di[k],v=j+dj[k];
				if(u<0 || u>N) continue;
				if(v<0 || v>N) continue;
				if(danger[s][u][v]) continue;
				ll idx=-1;
				for(int l=0;l<M;++l){
					if(ma[l][0]==u && ma[l][1]==v && bi[l]){idx=l;break;}
				}
				if(idx!=-1){
					if(danger[s-(1<<idx)][u][v]) continue;
					dp[s-(1<<idx)][u][v]+=dp[s][i][j];
					dp[s-(1<<idx)][u][v]%=mod;
				}else{
					dp[s][u][v]+=dp[s][i][j];
					dp[s][u][v]%=mod;
				}
				
			}
			
		}
	}
}

AC代码

327ms

https://codeforces.com/gym/105229/my

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";

using namespace std;

using  ll = long long;
constexpr ll mod=998244353;
/*

*/
ll dp[1100][105][105];
bool danger[1100][105][105];	// 0=safe 1=danger 2=horse
ll dx[]={1,2,2,-1,-2,1,-1,-2};
ll dy[]={2,1,-1,2,1,-2,-2,-1};
ll bx[]={0,1,1, 0,-1,0,0,-1};
ll by[]={1,0,0, 1,0,-1,-1,0};
ll di[]={0,1};
ll dj[]={1,0};
inline void solve(){
	ll N,M;
	cin>>N>>M;
	
	vector<array<ll,2> > ma;
	for(int i=0;i<M;++i){
		ll x,y;
		cin>>x>>y;
		ma.push_back({x,y});
		// mas.insert({x,y});
	}
	// dpi j s
	ll cnts=(1<<M);	// 状态数量
	for(int s=0;s<=cnts;++s){
		bitset<15> bi(s);
		vector<array<ll,2> > wp;
		set<array<ll,2> > st;
		for(int i=0;i<M;++i){
			if(bi[i]){
				wp.push_back(ma[i]);
				st.insert(ma[i]);
				// ll x=ma[i][0],y=ma[i][1];
				// danger[s][x][y]=2;
			}
		}
		for(int i=0;i<wp.size();++i){
			ll x=wp[i][0],y=wp[i][1];
			for(int j=0;j<8;++j){
				ll u=x+dx[j],v=y+dy[j];
				if(u<0 || u>N) continue;
				if(v<0 || v>N) continue;
				ll bbx=x+bx[j],bby=y+by[j];
				// 别马脚了
				if(st.find({bbx,bby})!=st.end()) continue;
				danger[s][u][v]=true;
			}
		}
	}
	if(!danger[cnts-1][0][0]) dp[cnts-1][0][0]=1;
	for(int s=cnts-1;s>=0;--s){
		for(int i=0;i<=N;++i){
			for(int j=0;j<=N;++j){
				if(danger[s][i][j]) continue;	// danger,continue
				bitset<15> bi(s);
				// set<array<ll,2> > mas;
				// for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
				for(int k=0;k<2;++k){
					ll u=i+di[k],v=j+dj[k];
					if(u<0 || u>N) continue;
					if(v<0 || v>N) continue;
					if(danger[s][u][v]) continue;
					ll idx=-1;
					for(int l=0;l<M;++l){
						if(ma[l][0]==u && ma[l][1]==v && bi[l]){idx=l;break;}
					}
					if(idx!=-1){
						if(danger[s-(1<<idx)][u][v]) continue;
						dp[s-(1<<idx)][u][v]+=dp[s][i][j];
						dp[s-(1<<idx)][u][v]%=mod;
					}else{
						dp[s][u][v]+=dp[s][i][j];
						dp[s][u][v]%=mod;
					}
					
				}
				
			}
		}
	}
	ll ans=0;
	for(int s=cnts-1;s>=0;--s){
		ans+=dp[s][N][N];
		ans%=mod;
	}
	ans%=mod;
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
}

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

*/

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

TLE，set常数太大。

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";

using namespace std;

using  ll = long long;
constexpr ll mod=998244353;
/*

*/
ll dp[1100][105][105];
bool danger[1100][105][105];	// 0=safe 1=danger 2=horse
ll dx[]={1,2,2,-1,-2,1,-1,-2};
ll dy[]={2,1,-1,2,1,-2,-2,-1};
ll bx[]={0,1,1, 0,-1,0,0,-1};
ll by[]={1,0,0, 1,0,-1,-1,0};
ll di[]={0,1};
ll dj[]={1,0};
inline void solve(){
	ll N,M;
	cin>>N>>M;
	
	vector<array<ll,2> > ma;
	for(int i=0;i<M;++i){
		ll x,y;
		cin>>x>>y;
		ma.push_back({x,y});
		// mas.insert({x,y});
	}
	// dpi j s
	ll cnts=(1<<M);	// 状态数量
	for(int s=0;s<=cnts;++s){
		bitset<15> bi(s);
		vector<array<ll,2> > wp;
		set<array<ll,2> > st;
		for(int i=0;i<M;++i){
			if(bi[i]){
				wp.push_back(ma[i]);
				st.insert(ma[i]);
				// ll x=ma[i][0],y=ma[i][1];
				// danger[s][x][y]=2;
			}
		}
		for(int i=0;i<wp.size();++i){
			ll x=wp[i][0],y=wp[i][1];
			for(int j=0;j<8;++j){
				ll u=x+dx[j],v=y+dy[j];
				if(u<0 || u>N) continue;
				if(v<0 || v>N) continue;
				ll bbx=x+bx[j],bby=y+by[j];
				// 别马脚了
				if(st.find({bbx,bby})!=st.end()) continue;
				danger[s][u][v]=true;
			}
		}
	}
	if(!danger[cnts-1][0][0]) dp[cnts-1][0][0]=1;
	for(int s=cnts-1;s>=0;--s){
		for(int i=0;i<=N;++i){
			for(int j=0;j<=N;++j){
				if(danger[s][i][j]) continue;	// danger,continue
				bitset<15> bi(s);
				set<array<ll,2> > mas;
				for(int k=0;k<M;++k){if(bi[k]) mas.insert(ma[k]);}
				for(int k=0;k<2;++k){
					ll u=i+di[k],v=j+dj[k];
					if(u<0 || u>N) continue;
					if(v<0 || v>N) continue;
					if(danger[s][u][v]) continue;
					if(mas.find({u,v})!=mas.end()){
						ll idx=0;
						for(int l=0;l<M;++l){
							if(ma[l][0]==u && ma[l][1]==v){idx=l;break;}
						}
						if(danger[s-(1<<idx)][u][v]) continue;
						dp[s-(1<<idx)][u][v]+=dp[s][i][j];
						dp[s-(1<<idx)][u][v]%=mod;
					}else{
						dp[s][u][v]+=dp[s][i][j];
						dp[s][u][v]%=mod;
					}
					
				}
				
			}
		}
	}
	ll ans=0;
	for(int s=cnts-1;s>=0;--s){
		ans+=dp[s][N][N];
		ans%=mod;
	}
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
}

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

*/

The 2024 Shanghai Collegiate Programming Contest K. 时光

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

思路讲解

就是注意到那，这个如果确定了要面对什么经历，那么肯定是选择从大到小经历最好，现在的问题就在于怎么样求这个东西，以及怎么拼起来？

那么拼起来我们用的是cal函数，其会调用mp解决拼起来的问题。

// 其实逻辑是先搞后一半，因为公式是sumB1*k2+val2+val1，那么我们要最大化sumB1*k2+val2
// 直接搞最大化比较难，但是k比较小，可以记录不同k下的val，最大化这个val。

// 输入剩余值 和 总经历数 返回最大的sumB1*k2+val2
auto cal=[&](ll rem,ll sumB1)->ll{
	ll res=0;
	for(int i=1;i<=N;++i){
		auto it=lower_bound(mp[i].begin(),mp[i].end(),(array<ll,2>){rem,INF});
		if(it==mp[i].begin()){
			continue;
		}
		it=prev(it);
		ll val2=(*it)[1];
		res=max(sumB1*i+val2,res);
	}
	return res;
};

AC代码

https://codeforces.com/gym/105229/my#

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";

using namespace std;

using  ll = long long;
const ll INF=(ll)1e17+3;
/*

*/
inline void solve(){
	ll N,M;
	cin>>N>>M;
	vector<array<ll,2> > ab(N+5,{0,0});
	for(int i=1;i<=N;++i){
		cin>>ab[i][0];
	}
	for(int i=1;i<=N;++i){
		cin>>ab[i][1];
	}
	sort(ab.begin()+1,ab.begin()+N+1,[](array<ll,2> a,array<ll,2> b){return a[1]>b[1];});
	
	ll half=N/2;ll halfs=N-half;
	vector<vector<array<ll,2> > > mp(N+5);
	ll Ans=0;
	// 先处理后半部分
	for(int i=0;i<=(1<<halfs);++i){
		bitset<30> bi(i);
		ll lans=0,sum=0,cnt=0,cost=0;
		for(int j=0;j<=halfs-1;++j){
			ll idx=j+half+1,b=ab[idx][1],a=ab[idx][0];
			if(bi[j]){
				cost+=a;
				lans+=sum;
				sum+=b;
				++cnt;
			}
		}
		if(cost>M) continue;
		Ans=max(Ans,lans);
		mp[cnt].push_back({cost,lans});
	}
	for(int i=1;i<=N;++i){
		sort(mp[i].begin(),mp[i].end());
	}
	for(int i=1;i<=N;++i){
		if(mp[i].empty()) continue;
		ll mx=0;
		for(int j=0;j<(int)mp[i].size();++j){
			mx=max(mx,mp[i][j][1]);
			mp[i][j][1]=mx;
		}
	}
	// 输入剩余值 和 总经历数 返回最大的sumB1*k2+val2
	auto cal=[&](ll rem,ll sumB1)->ll{
		ll res=0;
		for(int i=1;i<=N;++i){
			auto it=upper_bound(mp[i].begin(),mp[i].end(),(array<ll,2>){rem,INF});
			if(it==mp[i].begin()){
				continue;
			}
			it=prev(it);
			ll val2=(*it)[1];
			res=max(sumB1*i+val2,res);
		}
		return res;
	};
	// 处理前半部分
	for(int i=0;i<=(1<<half);++i){
		bitset<30> bi(i);
		ll lans=0,sum=0,cnt=0,cost=0;
		for(int j=0;j<=half-1;++j){
			ll idx=j+1,b=ab[idx][1],a=ab[idx][0];
			if(bi[j]){
				cost+=a;
				lans+=sum;
				sum+=b;
				++cnt;
			}
		}
		if(cost>M) continue;
		Ans=max(Ans,lans+cal(M-cost,sum));
	}
	cout<<Ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// ll lT;
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/gym/105229/my#
326774018
*/

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

Edu-180-E. Tree Colorings

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

思路讲解

AC代码

源代码

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

P3812 【模板】线性基

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

思路讲解

AC代码

源代码

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

BD202429 毕业照(binary lift facilitate the calculation)

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

思路讲解

前两问用二分，贪心解决。

最后一问需要使用双指针+倍增法。

AC代码

https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD

源代码

// https://www.matiji.net/exam/brushquestion/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
#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;const double pi=acos(-1.0);

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

*/
inline void init(){
	
}
struct cmpda{
	bool operator()(ll a,ll b){
		return H[a]<H[b];
	}
};
struct cmpxiao{
	bool operator()(ll a,ll b){
		return H[a]>H[b];
	}
};
inline void solve(){
	cin>>N>>K>>D;
	init();
	FOR(i,1,N){
		cin>>H[i];
	}
	ll lans2=0;
	auto check1=[&](ll mid)->bool{
		ll bp=1,res=0;
		while(bp<=N){
			ll i=bp;
			ll mn=H[i],mx=H[i];
			bool isB=false;
			FOR(j,i,N){
// #ifdef LOCAL
    // debug(H[j]-mn);
    // debug(H[j]-mx);
// #endif
				if(abs(H[j]-mn)<=mid && abs(H[j]-mx)<=mid){
// #ifdef LOCAL
    // cerr<<"OKAY\n";
// #endif
					mn=min(H[j],mn);
					mx=max(H[j],mx);
				}else{
					bp=j;
					++res;
					isB=true;
					break;
				}
				
			}
			if(!isB){
				++res;
				break;
			}
		}
// #ifdef LOCAL
	// debug(mid);
    // debug(res);
// #endif
		lans2=res;
		if(res>K){
			return false;
		}
		return true;
	};
	ll l=0,r=mod;
	while(l<r){
		ll mid=l+r>>1;
		if(check1(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
	check1(D);
	cout<<lans2<<"\n";
	vector<ll> nextPos(N+5,0);
	auto cal=[&]()->void{
		ll bp=1,res=0;
		priority_queue<ll,vector<ll>,cmpda> da;
		priority_queue<ll,vector<ll>,cmpxiao> xiao;
		FOR(i,1,N){
			bool isB=false;
			FOR(j,bp,N){
				while(da.empty()==false && (da.top()<i || da.top()>j) ){
					da.pop();
				}
				while(xiao.empty()==false && (xiao.top()<i || xiao.top()>j)){
					xiao.pop();
				}
				ll mx=da.empty()?H[j]:H[da.top()],mn=xiao.empty()?H[j]:H[xiao.top()];
				if(abs(H[j]-mx)<=D && abs(H[j]-mn)<=D){
					xiao.push(j);
					da.push(j);
				}else{
					bp=j;
					nextPos[i]=j-1;
// #ifdef LOCAL
    // debug(i);
// #endif
					isB=true;
					break;
				}
			}
			if(!isB){
				nextPos[i]=N;
				bp=N+1;
			}
		}
	};
	cal();
	ll mx_k=ceil(log2(K+1))+1;
	bitset<32> bik(K);
	vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
	ROF(i,N+1,1){
		jump[i][0]=i<=N?nextPos[i]+1:N+1;
		// if(i==N){
			// FOR(j,0,mx_k) jump[i][j]=N+1;
			// continue;
		// }
		FOR(j,1,mx_k){
			jump[i][j]=jump[jump[i][j-1]][j-1];
			// if(jump[i][j]==0) jump[i][j]=N+1;
		}
	}
	// FOR(t,0,mx_k){
		// FOR(i,1,N){
			// if(t==0) {jump[i][t]=nextPos[i]+1;continue;}
			// jump[i][t]=jump[jump[i][t-1]][t-1];
		// }
	// }
	ll ans=0;
// #ifdef LOCAL
    // FOR(i,1,N+1){
    	// FOR(j,0,mx_k){
    		// cerr<<jump[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // FOR(i,1,N){
    	// cerr<<nextPos[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	FOR(i,1,N){
		ll lans=0,idx=i;
		FOR(j,0,mx_k){
			if(bik[j]){
				idx=jump[idx][j];
			}
// #ifdef LOCAL
   	// debug(i);debug(idx);
// #endif
		}
		lans=idx-i;
		ans=max(ans,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://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
*/

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

调了比较久，最后终于是调出来了。最重要的就是这个倍增的板子，需要从N+1开始遍历。

vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
	ROF(i,N+1,1){
		jump[i][0]=i<=N?nextPos[i]+1:N+1;
		FOR(j,1,mx_k){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}