2025寒假专场4

· · 题解

401向前冲

模拟过程即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, h, k;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
typedef pair<int, int> PII;
map<PII, bool>v;
int main(){
    cin >> n >> m >> h >> k;
    string steps;
    cin >> steps;
    for(int i = 1; i <= m; i ++ ){
        int x, y;
        cin >> x >> y;
        v[{x, y}] = 1;
    }
    int sx = 0, sy = 0, dir = 0;
    for(auto c : steps){
        if(c == 'U') dir = 0;
        if(c == 'R') dir = 1;
        if(c == 'D') dir = 2;
        if(c == 'L') dir = 3;

        sx += dx[dir];
        sy += dy[dir];
        h --;
        if(h < 0){
            puts("No");
            return 0;
        }
        if(v[{sx, sy}] && h < k) h = k, v[{sx, sy}] = 0;

    }
    puts("Yes");
    return 0;
}

402shift对战capslock

DP

设前i个字符，第i个字符对应的Caps的状态为闭或者开的最少时间为f[i][j], 从第i-1个字符状态推导而来。

两种字母，分别讨论一下。

最后答案为min(f[n][0],f[n][1]);

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;

long long x, y, z;
char s[N];
int n;
long long f[N][2];
//当前需要选择第 i 个位置，Capslock 为大写 /小写所花的最小时间 

int main(){
    scanf("%lld%lld%lld", &x, &y, &z);
    scanf("%s", s + 1);
    n = strlen(s + 1);      // 获取长度 

    memset(f, 0x3f, sizeof f);
    f[0][1] = 1ll * 0;

    for (int i = 1; i <= n; i ++ )
        if (s[i] == 'A'){
            f[i][0] = min(f[i - 1][0] + min(x, z + y + z), f[i - 1][1] + min(z + x, y + z));
            f[i][1] = min(f[i - 1][0] + min(x + z, z + y), f[i - 1][1] + min(y, z + x + z));
        }
        else{
            f[i][0] = min(f[i - 1][0] + min(y, z + x + z), f[i - 1][1] + min(x + z, z + y));
            f[i][1] = min(f[i - 1][1] + min(x, z + y + z), f[i - 1][0] + min(z + x, y + z));
        }

    printf("%lld\n", min(f[n][0], f[n][1]));        // 答案为打完前 n 个字符后状态为大写或小写所需要花的最少时间 

    return 0;
}

403k等级

新链接的点的度不超过2；

所以度数\ge 3的点一定是原来的中心点。去掉与这个中心点相关的点（这个点的度数 + 这个点）

处理完上步后，再处理当前剩余度数\le 2的中心点，这种中心点相连的点有3个。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int d[N];
int n;
int main(){
    cin >> n;
    for(int i = 1; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        d[a] ++, d[b] ++;
    }
    vector<int> res;
    int cnt = n;
    for(int i = 1; i <= n; i ++ ){
        if(d[i] >= 3) res.push_back(d[i]), cnt -= d[i] + 1;
    }
    while(cnt){
        cnt -= 3;
        res.push_back(2);
    }
    sort(res.begin(), res.end());
    for(auto x : res)
        cout << x << " ";
    cout << endl;
    return 0;
}

堵塞点

#include<bits/stdc++.h>
using namespace std;
const int N = 330;
int dis[N][N], f[N][N];
const int inf = 0x3f3f3f3f;
int n, m;
int main(){

    scanf("%d%d", &n, &m);
    memset(dis, 0x3f, sizeof dis);

    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        dis[x][y] = 1;
        f[x][y] = 1;
    }

    for(int i = 1; i <= n; i++)
        dis[i][i] = 0;

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                if(dis[i][k] + dis[k][j] < dis[i][j]){
                    dis[i][j] = dis[i][k] + dis[k][j] ;
                    f[i][j] = f[i][k] * f[k][j];;
                }
                else if(dis[i][k] + dis[k][j] == dis[i][j])
                    f[i][j] += f[i][k] * f[k][j]; 
            }

    for(int i = 1; i <= n; i++) f[i][i] = 1;

    long long ans = 0;
    for(int k = 1; k <= n; k++){
        for(int u = 1; u <= n; u++){
            for(int v = 1; v <= n; v++){
                if(dis[u][v] < inf && dis[u][k] + dis[k][v] == dis[u][v] && f[u][k] * f[k][v] == f[u][v])
                    ans ++;
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

404游戏

区间DP的经典题

- 选左侧： $f[i][j] = x_i - f[i + 1][j]

则留下的区间的范围：[k, min(j, k + L - 1)]

设sum[i] = x_1 + x _2 ... + x_i

f[i][j] = sum[j] - sum[i - 1] - (sum[min(k + L - 1,j)] - sum[k - 1]) - f[k][min(k + L - 1, j)] - A 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int f[N][N],sum[N];
int n,a,b,c,d,x[N];
signed main() {

    cin >> n >> a >> b >> c >> d;

    for(int i = 1; i <= n; i++){
        cin >> x[i];
        sum[i] = sum[i - 1] + x[i];
    }
    for(int len = 1; len <= n; len++) { //  枚举区间长度 
        for(int i = 1; i + len - 1 <= n; i++) { // 枚举左端点 
            int j = i + len - 1; // 右端点 
            f[i][j] = max(x[j] - f[i][j - 1], x[i] - f[i+1][j]);

            int lenn = max(0ll, (j - i + 1) - b); // 剩余的长度 
            if(lenn == 0) f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - a);
            else for(int k = i; k + lenn - 1 <= j; k++)
                    f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - (sum[k + lenn - 1] - sum[k - 1]) - f[k][k + lenn - 1] - a);

            lenn = max(0ll,(j - i + 1) - d);
            if(lenn == 0) f[i][j] = max(f[i][j], sum[j] - sum[i-1] - c);
            else for(int k = i; k + lenn - 1 <= j; k++)
                    f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - (sum[k + lenn - 1] - sum[k - 1]) - f[k][k + lenn - 1] - c);
        }
    }
    cout << f[1][n] << "\n";
    return 0;
}