B

BFS 思维

网格图上从起点到终点，只能往上下右走，人有一个视野，超出范围的看不到。问是否存在一个死胡同，会误导人走进来

等价于是否存在一个路径，人没走进来时无法确定是不是死路，只有等走进来了才能发现是死路（由于不能往左走，此时已经晚了，游戏失败）

首先需要找到所有死路的点，这可以通过找到所有能到终点的路径，剩下的就是所有死路包含的点。从起点出发，到终点，经过的所有可能点，可以分别从起点和终点出发BFS，所有同时被两次访问到的就是。剩下那些能从起点出发到达的，但不能从终点出发到达的，就是死路的点。

接下来就是找是否存在一个死路，他在左右方向上足够深，超出角色的视野，用一个dp维护所有死路点所在连通块的最大列号即可。最后检查所有死路点的深度，看是否存在一个深度大于视野即可

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

void solve() {
    int n,m,k;
    cin>>n>>m>>k;

//     array<array<int,m+1>,n+1>a,v1,v2,dep;
    vector<vector<int>>a(n+1,vector<int>(m+1));
    vector<vector<bool>>v1(n+1,vector<bool>(m+1));
    vector<vector<bool>>v2(n+1,vector<bool>(m+1));
    vector<vector<int>>dep(n+1,vector<int>(m+1));

    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1]-'0';
        }
    }
    queue<pair<int,int>>q;
    v1[1][1]=1;
    q.push({1,1});

    int dx[4]={1,0,-1,0};
    int dy[4]={0,-1,0,1};

    while(q.size()){
        auto p=q.front();
        q.pop();
        int x=p.first,y=p.second;
        for(int i=0;i<4;i++){
            if(i==1)continue;
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==1||v1[xx][yy])continue;
            v1[xx][yy]=1;
            q.push({xx,yy});
        }
    }
    v2[1][m]=1;
    q.push({1,m});
    while(q.size()){
        auto p=q.front();
        q.pop();
        int x=p.first,y=p.second;
        for(int i=0;i<4;i++){
            if(i==3)continue;
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==1||v2[xx][yy])continue;
            v2[xx][yy]=1;
            q.push({xx,yy});
        }
    }

    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         if(v1[i][j]&&v2[i][j]){
    //             cout<<2;
    //         }
    //         else if(v1[i][j]){
    //             cout<<1;
    //         }
    //         else{
    //             cout<<0;
    //         }
    //     }
    //     cout<<'\n';
    // }
    for(int i=m;i>=1;i--){
        for(int j=1;j<=n;j++){
            if(v1[j][i]&&!v2[j][i]){
                dep[j][i]=i;
            }
            else continue;
            if((i+1)<=m&&(v1[j][i+1]&&!v2[j][i+1])){
                dep[j][i]=max(dep[j][i],dep[j][i+1]);
            }
            if((j-1)>=1&&(v1[j-1][i]&&!v2[j-1][i])){
                dep[j][i]=max(dep[j][i],dep[j-1][i]);
            }
        }
        for(int j=n;j>=1;j--){
            if(v1[j][i]&&!v2[j][i]){
                if((j+1)<=n&&(v1[j+1][i]&&!v2[j+1][i])){
                    dep[j][i]=max(dep[j][i],dep[j+1][i]);
                }

                    if(dep[j][i]-i>=k-1){
                        cout<<"Yes\n";
                        return;
                    }
            }
            
        }
    }
    cout<<"No\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

F

排序 贪心 思维

一个序列每次交换相邻元素，代价固定c。最后得分是前k个元素和-交换产生的总代价。问最大得分？

第一思路就是根据元素值，位置，代价排序，大概就是，然后取前k大之类的。但是排序根据什么标准？这里主要是前k个不好想，如果能统一交换到一个位置，此时交换次数就是，排序指标也就是，就很好做了。但这里我们要求移动到前k个位置。

实际上这个死路是有道理的，沿着这个思路想，如果我们把所有前k大元素移动到开头，接下里其实把他们分散到前k个的代价和，是确定的。所以可以先假设都移动到开头，贪心算代价，然后加上把开头的k个元素移动到前k个位置的代价即可

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;


void solve() {
    int n, k, c;
    cin >> n >> k >> c;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        a[i] -= i * c;
    }
    sort(1 + a.begin(), a.end(), [&](int x, int y) {
        return x > y;
    });
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        ans += a[i] + i*c;
    }
    cout << ans << "\n";
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; 
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}