赛时FB，补GI

F

题意

有n个宝藏，每个宝藏有自己的val，你能获得前k个
同时，你还可以进行一些交换，每次交换消耗价值c
求解你可以获得的最大价值

思路

考虑将所有宝藏都换到最前面，取最高的k个，然后再加上把k个宝藏从第一个放到前k个的价值

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  priority_queue<int> pq;
  int n, k, c;
  cin >> n >> k >> c;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  for (int i = 0; i < n; i++) {
    pq.emplace(a[i] - i * c);
  }
  int answer = 0;
  for (int i = 0; i < k; i++) {
    answer += pq.top();
    pq.pop();
  }
  answer += k * (k - 1) / 2 * c;
  cout << answer << endl;
  return 0;
}

B

题意

一张n*m地图，判断有没有可能因为视野限制走入死胡同

思路

走入死胡同意味着，在k视野下看到是活路，但实际是死路，也就是思路的横向宽度大于等于k
从起点和终点分别跑一个dfs就能找到所有不可达的块，判断每一个块的宽度即可

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int N, M, K;
  cin >> N >> M >> K;
  auto mp = vector(N + 2, string(M + 2, '1'));
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      cin >> mp[i][j];
    }
  }
  auto visit1 = vector(N + 2, vector(M + 2, false));
  auto visit2 = vector(N + 2, vector(M + 2, false));
  auto dot = vector(N + 2, vector(M + 2, false));

  auto dfs1 = [&](auto &self, int x, int y) -> void {
    if (mp[x][y] == '1') return;
    if (visit1[x][y]) return;
    visit1[x][y] = true;
    self(self, x + 1, y);
    self(self, x - 1, y);
    self(self, x, y + 1);
  };
  dfs1(dfs1, 1, 1);

  auto dfs2 = [&](auto &self, int x, int y) -> void {
    if (mp[x][y] == '1') return;
    if (visit2[x][y]) return;
    visit2[x][y] = true;
    self(self, x + 1, y);
    self(self, x - 1, y);
    self(self, x, y - 1);
  };
  dfs2(dfs2, 1, M);

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      dot[i][j] = visit1[i][j] && !visit2[i][j];
    }
  }

  auto visit = vector(N + 2, vector(M + 2, false));

  auto search = [&](auto &self, int x, int y, int width) -> int {
    visit[x][y] = true;
    int a1 = 1, a2 = 1, a3 = 1;
    if (!visit[x + 1][y] && dot[x + 1][y])
      a1 = self(self, x + 1, y, width);
    if (!visit[x - 1][y] && dot[x - 1][y])
      a2 = self(self, x - 1, y, width);
    if (!visit[x][y + 1] && dot[x][y + 1])
      a3 = self(self, x, y + 1, width + 1);
    return max({a1, a2, a3, width});
  };

  int maxwidth = 0;
  for (int j = 1; j <= M; j++) {
    for (int i = 1; i <= N; i++) {
      if (dot[i][j] && !visit[i][j])
        maxwidth = max(maxwidth, search(search, i, j, 1));
    }
  }

  if (maxwidth < K)
    cout << "No\n";
  else
    cout << "Yes\n";
}
int main() {
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}

G

题意

给一个合法括号序列s，每个字符有1/2的概率变成？，请问获得的含？序列可以唯一还原成合法序列的概率

思路

对于一个子序列，可被唯一合法还原的条件是：
- 必须是若干个'('在前，然后若干个')'，因为只要存在")("，将这两个交换必然合法，存在多种方案
- 交换最后一个'('和第一个')'前缀和序列存在负值(非法情况)
枚举l表示最后一个被变成'?'的'('的位置，然后找r为第一个被变成'?'的')'的位置

代码

#include<bits/stdc++.h>
using namespace std;
using ll =long long ;
const int p=998244353;

ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

ll ans=0;
ll a[1010101],pre[1010101],suf[1010101],sum[1010101];
int main(){
    string s;
    cin >> s;
    s=' '+s;
    for(int i=1;i<s.length();i++) {
        a[i]=(s[i]=='('?1:-1);
        sum[i]=a[i]+sum[i-1];
        // cout << sum[i] << ' ' ;
    }
    // cout << endl;
    for(int i=1;i<s.length();i++) pre[i]=pre[i-1]+(a[i]==1);
    for(int i=s.length()-1;i>=1;i--) suf[i]=suf[i+1]+(a[i]==-1);

    for(int l=1,r=1;l<s.length();l++){
        while(r<s.length()&&(sum[r]>1||r<l)) r++;
        if(r==s.length())break;
        if(a[l]==1){
            // cout << l << ' ' << r << ' ' << pre[l-1] << ' ' << suf[r+1] << endl;
            ans=(ans+(qpow(2,pre[l-1])*qpow(2,suf[r+1])%p))%p;
            // cout << ans << endl;
        }
    }
    ans=(ans+qpow(2,(s.length()/2))%p);   
    // cout << ans << endl;
    ll inv=qpow(qpow(2,s.length()-1),p-2);
    cout << (ans*inv)%p << endl;
    return 0;
}

I

题意

n*m的推箱子地图，箱子自己移动，判断是否存在不超过1e5长度的解

思路

对于每个箱子跑bfs，找到最近的目标，然后恢复路径，从终点往箱子回溯，如果路上遇到箱子，就清空路径
形式化的：对于箱子A和终点C，回溯A->C的路径中遇到箱子B则存储两段路径，B->C，A->B

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
/**
 * 每个箱子广搜
 * 途中遇到未到位的箱子怎么办？
 * 途中遇到已经到位的箱子怎么办？
 * 每个箱子搜出来一条路，回溯这个路，回溯的过程中，如果遇到已经占位的别的箱子，就分成两段
 * Eg.A->C中间，B处有一个箱子，所得路径C->a
 * 从C回溯，到B遇见障碍，将C->B记为一段
 * 然后从B继续回溯，直到A
 * 这样就获得了B->C，A->B的两段路径
 */

int n,m;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
string mp[55];
vector<pair<pii,pii>> path;
int vis[55][55];
int prex[55][55];
int prey[55][55];
vector<pair<pair<int,int>,char>> ans;

char getdir(pii now,pii lst){
    if(now.f==lst.f){
        return lst.s>now.s?'L':'R';
    }else{
        return lst.f>now.f?'U':'D';
    }
}

void creat(){
    // for(auto [x,y]:path){
    //     cout << x.f+1 << ' ' << x.s+1 << "->" << y.f+1 << ' ' << y.s+1 << endl;
    // }
    int flg=-1;
    for(int i=0;i<path.size();i++){
        pii now1=path[i].f,lst1=path[i].s;
        if(mp[lst1.f][lst1.s]!='.'){
            for(int j=i;j>flg;j--){
                pii now2=path[j].f,lst2=path[j].s;
                ans.push_back({{lst2.f,lst2.s},getdir(now2,lst2)});
            }
            // cout<< "OK"<< i<<' '<< flg <<endl;
            flg=i;            
        }
    }
    mp[path.back().s.f][path.back().s.s]='.';
    mp[path[0].f.f][path[0].f.s]='!';
}

bool check(pii tp){
    if(tp.f<0||tp.f>=n||tp.s<0||tp.s>=m||mp[tp.f][tp.s]=='#'||vis[tp.f][tp.s]) return false;
    return true;
}

void bfs(int x,int y){
    queue<pii> q;
    memset(vis,0,sizeof(vis));
    memset(prex,0,sizeof(prex));
    memset(prey,0,sizeof(prey));
    path.clear();
    q.push({x,y});
    vis[x][y]=1;
    prex[x][y]=-1;
    prey[x][y]=-1;
    while(!q.empty()){
        pii now=q.front();
        q.pop();
        if(mp[now.f][now.s]=='*'){
            while(prex[now.f][now.s]!=-1||prey[now.f][now.s]!=-1){
                pii lst={prex[now.f][now.s],prey[now.f][now.s]};
                path.push_back({now,lst});
                now=lst;
            }
            return ;
        }
        for(int i=0;i<4;i++){
            pii next={now.f+dir[i][0],now.s+dir[i][1]};
            if(check(next)){
                q.push(next);
                vis[next.f][next.s]=1;
                prex[next.f][next.s]=now.f;
                prey[next.f][next.s]=now.s;
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> mp[i];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='@'){
                bfs(i,j);
                if(path.size()==0){
                    cout << -1 << endl;
                    return 0;
                }
                creat();
            }
        }
    }
    cout << ans.size() << endl;
    for(auto [x,y]:ans){
        cout << x.f+1 << ' ' << x.s+1 << ' ' << y << endl;
    }

    return 0;
}

牛客多校04

F

题意

思路

代码

B

题意

思路

代码

G

题意

思路

代码

I

题意

思路

代码