2025牛客多校训练4（死胡同，交换变选数贪心） · znzryb
## Problem F. For the treasury!
把这个问题看成选K个数字，然后把这K个数字全部移到第一个位置，然后把多减的代价加回来。
::: 源代码
```cpp
// 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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78442849&returnHomeType=1&uid=817445536)
赛时提交有问题是因为并没有考虑这个动态的过程，或许这种题目还是要**首先搞清楚这个模拟**，把这个模拟的本质，**模拟的策略**给搞清楚。模拟的策略就是说，至少目前为止，我走到这个点，一定是可以到达
直接模拟这个玩家，其实通过题意理解，**只要这个玩家所走到的点最终能够走到视野的尽头，那么这个玩家就认为他能够走到走到终点。**
那么前面有一个反向bfs，得到所有我们能到达终点的点。（赛时解法中已经想到了）。
那么这个far数组，或者说dp数组，可以通过比较朴素的前缀dp得到。
```cpp
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]);
}
}
```
然后模拟这个玩家。
```cpp
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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78459227)
::: 源代码
```cpp
// 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
那么我个人认为难点在于这个题目需要输出推动序列，其实还是有点难的，难度在于这个模拟，以及代码实现上。
::: 源代码
```cpp
```
:::
## Problem G. Ghost in the Parentheses
首先，将（ 转为1，）转为-1，始终有合法匹配（序列是合法的）就是前缀和始终为正。
通过该条件，我们能找出所有的不可交换位置（指的是你不能拿 $）$和这个$（ $ 换 ）。
通过如下程序，可以计算出来这个 ）所能选的右括号有$rem=N/2-fix$ 个，但是这样之间计算概率只能通过第一个样例，那怎么办那？遇事不决，就上dp（当然我也不会，和grok学的，这个dp）
```cpp
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";
```
::: 源代码
```cpp
```
:::