2025牛客多校训练4（死胡同，交换变选数贪心）

Problem F. For the treasury!

把这个问题看成选K个数字，然后把这K个数字全部移到第一个位置，然后把多减的代价加回来。

源代码

// Problem: For the Treasury!
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/108301/F
// Memory Limit: 2048 MB
// Time Limit: 4000 ms
// by Gospel_rock
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)

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 vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN],C;
ll Sum[MAXN];

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

*/
inline void __(){
	cin>>N>>K>>C;
	FOR(i,1,N){
		cin>>A[i];
	}
	// FOR(i,1,N){
		// Sum[i]=Sum[i-1]+A[i];
	// }
	priority_queue<ll,vector<ll>,less<ll> > pq;
	FOR(i,1,N){
		pq.push(A[i]-C*(i-1));
	}
	ll ans=0;
	FOR(i,1,K){
		ans+=pq.top();
		pq.pop();
	}
	ans+=(0+K-1)*K/2*C;
	cout<<ans<<"\n";
}
/*

*/

Problem B. Blind Alley（看到这种砍掉一个方向，要想到dp）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78442849&returnHomeType=1&uid=817445536

赛时提交有问题是因为并没有考虑这个动态的过程，或许这种题目还是要首先搞清楚这个模拟，把这个模拟的本质，模拟的策略给搞清楚。模拟的策略就是说，至少目前为止，我走到这个点，一定是可以到达

直接模拟这个玩家，其实通过题意理解，只要这个玩家所走到的点最终能够走到视野的尽头，那么这个玩家就认为他能够走到走到终点。

那么前面有一个反向bfs，得到所有我们能到达终点的点。（赛时解法中已经想到了）。

那么这个far数组，或者说dp数组，可以通过比较朴素的前缀dp得到。

vector<vector<ll> > dp(N+5,vll(M+5));
ROF(j,M,1){
	if(j==M){
		FOR(i,1,N){
			if(S[i][j]=='0'){
				dp[i][j]=j;
			}
		}
		continue;
	}
	FOR(i,1,N){
		if(S[i][j]=='1') continue;
		dp[i][j]=j;
		dp[i][j]=max(dp[i][j+1],dp[i][j]);
	}
	FOR(i,2,N){
		if(S[i][j]=='1') continue;
		dp[i][j]=max(dp[i][j],dp[i-1][j]);
	}
	ROF(i,N-1,1){
		if(S[i][j]=='1') continue;
		dp[i][j]=max(dp[i][j],dp[i+1][j]);
	}
}

然后模拟这个玩家。

	while(!q.empty()){
		auto [x,y]=q.front();q.pop();
		FOR(i,0,2){
			ll u=x+dxx[i],v=y+dyy[i];
			if(u<1 || u>N) continue;
			if(v<1 || v>M) continue;
			if(vis2[u][v]) continue;
			if(S[u][v]=='1') continue;
// 只要这个玩家所走到的点最终能够走到视野的尽头，那么这个玩家就认为他能够走到走到终点
			if(dp[u][v]<y+K){ // 该玩家可以看到该点已经被堵死了。
				continue;
			}
			if(!vis[u][v]){  // 如果按照前面的逻辑筛选过了，还是踏入了陷阱，输出yes
				cout<<"Yes\n";
				return;
			}
			vis2[u][v]=true;
			q.EM(u,v);
		}
	}

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

源代码

// Problem: Blind Alley
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/108301/B
// Memory Limit: 2048 MB
// Time Limit: 2000 ms
// by Gospel_rock
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()

#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)

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 vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e3+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7; // 998244353
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
/* ->
  |  |
   <-
*/
ll dx[]={1,0,-1};
ll dy[]={0,-1,0};
inline void __();
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*

*/
inline void __(){
	cin>>N>>M>>K;
	vector<vector<char> > S(N+5,vector<char>(M+5));
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>S[i][j];
		}
	}
	// 反向bfs能够走到的点
	vector<vector<bool> > vis(N+5,vector<bool>(M+5,0));
	queue<pll> q;q.EM(1,M);
	vis[1][M]=true;
	while(!q.empty()){
		auto [x,y]=q.front();q.pop();
		FOR(i,0,2){
			ll u=x+dx[i],v=y+dy[i];
			if(u<1 || u>N) continue;
			if(v<1 || v>M) continue;
			if(vis[u][v]) continue;
			if(S[u][v]=='1') continue;
			vis[u][v]=true;
			q.EM(u,v);
		}
	}
	vector<vector<ll> > dp(N+5,vll(M+5));
	ROF(j,M,1){
		if(j==M){
			FOR(i,1,N){
				if(S[i][j]=='0'){
					dp[i][j]=j;
				}
			}
			continue;
		}
		FOR(i,1,N){
			if(S[i][j]=='1') continue;
			dp[i][j]=j;
			dp[i][j]=max(dp[i][j+1],dp[i][j]);
		}
		FOR(i,2,N){
			if(S[i][j]=='1') continue;
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
		ROF(i,N-1,1){
			if(S[i][j]=='1') continue;
			dp[i][j]=max(dp[i][j],dp[i+1][j]);
		}
	}
#ifdef LOCAL
   	FOR(i,1,N){
   		FOR(j,1,M){
   			cerr<<dp[i][j]<<" ";
   		}
   		cerr<<"\n";
   	}
   	FOR(i,1,N){
   		FOR(j,1,M){
   			cerr<<vis[i][j];
   		}
   		cerr<<"\n";
   	}
   	cend;
#endif
	q.EM(1,1);
	vll dxx={0,1,-1};
	vll dyy={1,0,0};
	vector<vector<bool> > vis2(N+5,vector<bool>(M+5,0));
	vis2[1][1]=true;
	while(!q.empty()){
		auto [x,y]=q.front();q.pop();
#ifdef LOCAL
    cerr<<x<<" "<<y<<"\n";
#endif
		FOR(i,0,2){
			ll u=x+dxx[i],v=y+dyy[i];
			if(u<1 || u>N) continue;
			if(v<1 || v>M) continue;
			if(vis2[u][v]) continue;
			if(S[u][v]=='1') continue;
			if(dp[u][v]<y+K){
				continue;
			}
			if(!vis[u][v]){
				cout<<"Yes\n";
				return;
			}
			vis2[u][v]=true;
			q.EM(u,v);
		}
	}
	cout<<"No\n";

}
/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78459227
*/

Problem I. I, Box

那么我个人认为难点在于这个题目需要输出推动序列，其实还是有点难的，难度在于这个模拟，以及代码实现上。

源代码

Problem G. Ghost in the Parentheses

首先，将（ 转为1，）转为-1，始终有合法匹配（序列是合法的）就是前缀和始终为正。

通过该条件，我们能找出所有的不可交换位置（指的是你不能拿 $）$和这个$（ $ 换 ）。

通过如下程序，可以计算出来这个 ）所能选的右括号有$rem=N/2-fix$ 个，但是这样之间计算概率只能通过第一个样例，那怎么办那？遇事不决，就上dp（当然我也不会，和grok学的，这个dp）

	ll fix=0;
	ll inv2=binpow(2,mod-2);
	ll ans=0;
	FOR(i,1,N){
		if(A[i]==1 && Sum[i]<=1){
			fix++;
		}
		if(A[i]==-1 && i!=N){
			ll rem=N/2-fix;
#ifdef LOCAL
    debug(rem);
#endif
			ans+=1*inv2*(1-binpow(inv2,rem));
			ans%=mod;
		}
	}
	ans=1-ans;
	ans%=mod;if(ans<0) ans+=mod;
	cout<<ans<<"\n";

源代码