Znzryb's Blog

201.数字范围内按位与

Posted on 2025-07-02 Edited on 2026-02-17

思路讲解

直接计算有值最长前缀。

AC代码

源代码

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        bitset<40> bil(left),bir(right);
        using ll=long long;
        if(right==0) return 0;
        ll MAX=floor(log2l(right));
        ll ans=0;
        for(int i=MAX;i>=0;--i){
            if(bil[i]!=bir[i]){
                break;
            }else if(bil[i]){
                ans+=(1ll<<i);
            }
        }
        return (int)ans;
    }
};

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

第五届上海理工大学程序设计全国挑战赛D/N/A

Posted on 2025-07-02 Edited on 2026-03-12

思路讲解

AC代码

源代码

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

第五届上海理工大学程序设计全国挑战赛A. Another Walk Alone Problem

Posted on 2025-07-02 Edited on 2026-02-17

思路讲解

看了题解以后，我们发现有些时候我们不一定要全部依赖树状dp得出答案。

auto dfs=[&](auto &&self,ll u,ll cur,ll gain,ll de)->void{    // 在外面调用的时候dfs(dfs,u)
	vis[u]=true;dp[u]=cur;
	for(int i=0;i<g[u].size();++i){
		ll v=g[u][i][0],w=g[u][i][1];
		if(vis[v]) continue;
		if(cur+gain+A[u]-de>=w){
			self(self,v,cur,gain+A[u],de+w);
		}else{
			self(self,v,w-gain-A[u]+de,gain+A[u],de+w);
		}
	}
	for(int i=0;i<g[u].size();++i){
		ll w=g[u][i][1],v=g[u][i][0];
		if(w*2<A[u]+A[v] && A[u]>=w){
			inf.push_back(dp[u]);  // 无限循环所需要的值
			break;
		}
	}
};

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78031630

源代码

// Problem: Another Walk Alone Problem
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/111679/A
// Memory Limit: 2048 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using namespace std;

using  ll = long long;
constexpr ll MAXN=(ll)1e6+10;constexpr ll INF=(ll)1e17+9;
constexpr ll mod=(ll)1e9+7;constexpr double eps=1e-8;const double pi=acos(-1.0);
/*

*/
ll A[MAXN];
inline void solve(){
	ll N;cin>>N;
	vector<vector<array<ll,2> > > g(N+5);
	for(int i=2;i<=N;++i){
		cin>>A[i];
	}
	for(int i=1;i<=N-1;++i){
		ll u,v,w;cin>>u>>v>>w;
		g[u].push_back({v,w});g[v].push_back({u,w});
	}
	vector<ll> inf,dp(N+5,0);
	vector<bool> vis(N+5,0),isinf(N+5,0);
	// map<array<ll,2>,2> mp;
	auto dfs=[&](auto &&self,ll u,ll cur,ll gain,ll de)->void{    // 在外面调用的时候dfs(dfs,u)
		vis[u]=true;dp[u]=cur;
		for(int i=0;i<g[u].size();++i){
			ll v=g[u][i][0],w=g[u][i][1];
			if(vis[v]) continue;
			if(cur+gain+A[u]-de>=w){
				self(self,v,cur,gain+A[u],de+w);
			}else{
				self(self,v,w-gain-A[u]+de,gain+A[u],de+w);
			}
		}
		for(int i=0;i<g[u].size();++i){
			ll w=g[u][i][1],v=g[u][i][0];
			if(w*2<A[u]+A[v] && A[u]>=w){
				inf.push_back(dp[u]);
#ifdef LOCAL
    debug(w);debug(A[u]);debug(u);
#endif
				break;
			}
		}
	};
	dfs(dfs,1,0,0,0);
#ifdef LOCAL
    for(int i=2;i<=N;++i){
    	cerr<<dp[i]<<" ";
    }
    cerr<<"\n";
    for(int i=0;i<inf.size();++i){
    	cerr<<inf[i]<<" ";
    }
    cerr<<"\n";
#endif
	ll mn=inf.empty()?INF:*min_element(inf.begin(),inf.end());
	for(int i=2;i<=N;++i){
		cout<<min(dp[i],mn)<<" ";
	}
	cout<<"\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……）

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

Posted on 2025-07-02 Edited on 2026-02-17

思路讲解

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

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-02-17

思路讲解

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

那么拼起来我们用的是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
*/