2025寒假专场2

compaq · 2025-01-07 13:49:35 · 题解

201填充数字

直接模拟

202字符串问题

统计出第一个和第二个字符串中'@'的数量。

桶排出所有小写字母在第一个字符串中的数量，然后再第二个字符串中相应减去，减去后这个个字符不为0，,且不是atcoder中的一个，则肯定不行。否则算入修改的数量。

最后判断修改的数量是否会超标。

203二进制变换

贪心：

将初始字符串中的'?'看成0， 得到一个数值tmp,

若tmp > n则结束，这是当前最小的数值了。

否则从最高位开始，若遇到'?'，则该位置改成1。

#include<bits/stdc++.h>
using namespace std;
long long n;
string t;
char s[100];

int main(){
    cin >> t >> n;

    for(int i = t.size() - 1; i >= 0; i--)
        s[t.size() - i - 1] = t[i]; // 索引为0的位置个各位 

    long long tmp = 0;
    for(int i = 0; i < t.size(); i++)
        if(s[i] == '1')
            tmp = tmp | (1ll << i);

    if(tmp > n){
        puts("-1");
        return 0;
    }

    for(int i = t.size() - 1; i >= 0; i--){
        if(s[i] == '?'){
            if( (tmp | (1ll << i)) <= n){
                tmp = (tmp | (1ll << i));
            }
        }
    }
    cout << tmp << endl;

    return 0;
}

204糖果方格

注意到糖的数量非常少，只有18颗，可以进行状压。

预处理所有的糖果点，计算出相互之间的最短距离，存在d[][]当中。

设f[i][s]表示第i个点状态为s时的最少步数，

#include<bits/stdc++.h>
#define INF 1e9
#define N 305
#define M 20
#define S 1048576
using namespace std;
int n, m, k, cnt, ans;
int sx, sy, tx, ty;
const int dx[]={1, 0, -1, 0};
const int dy[]={0, 1, 0, -1};
int dis[N][N], f[M][S], d[M][M];
bool vis[N][N];
pair<int, int>node[M];
char s[N][N];
bool check(int i,int j){
    return 1 <= i && i <= n && 1 <= j && j <= m && s[i][j] != '#' && !vis[i][j];
}

void BFS(int x,int y){
    for(int i=0;i<=n;++i) 
        for(int j=0;j<=m;++j) 
            dis[i][j] = INF,vis[i][j] = false;

    queue< pair<int, int> >q;
    q.push({x, y}), dis[x][y] = 0;
    vis[x][y] = true;

    while(!q.empty()){
        pair<int, int> now = q.front(); q.pop();
        int xx = now.first, yy = now.second;
        for(int i = 0; i < 4; ++i){
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if(check(nx, ny)){
                dis[nx][ny] = dis[xx][yy] + 1;
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> s[i][j];
            if(s[i][j] == 'S') sx = i,sy = j;
            if(s[i][j] == 'G') tx = i,ty = j;
            if(s[i][j] == 'o') node[++cnt] = {i, j};
        }
    }
    node[0] = {sx, sy}, node[++cnt] = {tx, ty};
    for(int i = 0; i <= cnt; ++i){
        int x = node[i].first, y = node[i].second;
        BFS(x, y);
        for(int j = 0; j <= cnt; ++j){
            int nx = node[j].first;
            int ny = node[j].second;
            d[i][j] = dis[nx][ny];
        }
    }

    //for(int i = 0; i <= cnt; i++) cout << node[i].first << ' ' << node[i].second << endl;

    memset(f, 0x3f, sizeof f);

    f[0][0] = f[0][1] = 0;
    for(int s = 0; s < (1 << (cnt + 1)); s++){
        for(int i = 0; i <= cnt; i++){
            for(int j = 0; j <= cnt; j++){
                if(s & (1 << j) && f[j][s & (~(1 << j))] <= k)
                    f[i][s] = min(f[i][s], f[j][s &( ~(1 << j))] + d[j][i]);
            }
        }
    }

    for(int s = 0; s < (1 << cnt + 1); s++) 
        if(f[cnt][s] <= k) 
            ans = max(ans, __builtin_popcount(s));
    printf("%d\n", ans < 2 ? - 1 : ans - 2);
    return 0;
}