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

思路讲解

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

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;
}
/*

*/