526互联

AtCoder Beginner Contest 295

发布时间 2023-12-31 14:15:01作者: mostimali



B - Bombsd

难度: ⭐

题目大意

给定一个n*m的网格, 其中' . '表示空白, ' # '表示障碍物, 数字x表示此处有一个炸弹, 会将附近曼哈顿距离小于等于x的格子都变成空白; 问所有炸弹爆炸后的网格;

解题思路

数据范围很小, 暴力即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e2 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
bool st[N][N], st2[N][N][10];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void modify(int x, int y, int u){
    if(u < 0) return;
    if(st2[x][y][u]) return;
    st[x][y] = true;
    st2[x][y][u] = true;
    for(int i = 0; i < 4; i++){
        if(x + dx[i] >= 1 && x + dx[i] <= n) modify(x + dx[i], y, u - 1);
    }
    for(int i = 0; i < 4; i++){
        if(y + dy[i] >= 1 && y + dy[i] <= m)modify(x, y + dy[i], u - 1);
    }
}

signed main() {
    IOS;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
            if(isdigit(g[i][j])){
                modify(i, j, g[i][j] - '0');
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(st[i][j]) cout << '.';
            else cout << g[i][j];
        }   
        cout << endl;
    }
    return 0;
}



C - Socks

难度: ⭐⭐

题目大意

小莫有n只袜子, 给出这n只袜子各自的颜色, 小莫需要把两个颜色相同的袜子两两配对, 请问最多可以配成多少双;

解题思路

也是比较直接的一道题, 没有什么贪心策略, 能配就配; 对于颜色x的袜子, 如果之前有一只颜色x的袜子, 那么就答案+1, 然后把这两个袜子去掉; 这个过程可以用map实现;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
map<int, int> mp;

signed main() {
    IOS;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> m;
        if(mp[m]){
            mp[m] = 0;
            res++;
        }
        else mp[m]++;
    }
    cout << res;
    return 0;
}



D - Three Days Ago

难度: ⭐⭐⭐

题目大意

给定一个由n个数字组成的字符串s, 字符串s可以随意排序; 问有多少个区间(l, r), 可以用区间内的数字组合成两个一模一样的子串; eg: "56846485"可以变成"4568 4568";

解题思路

由题意得, 无非就是让区间内的每个数字的个数都是偶数个; 数据范围较大, 所以需要线性的解决; 因此我们可以线性的扫描字符串, 当前是第i个数字, 我们可以知道前i个数字有几个是落单的, 然后我们把落单的情况存下来, 如果在之后第j个数字, 我们又遇到了相同的落单情况, 那么(i, j)就是一个满足要求的情况; 而落单的情况我们可以用一个长度为10的字符串来表示; 用哈希来表示数量即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int p[N];
map<string, int> mp;

signed main() {
    string s;
    cin >> s;
    int len = s.size();
    string str = "aaaaaaaaaaa";
    mp[str]++;
    for(int i = 0; i < len; i++){
        int x = s[i] - '0';
        if(str[x] == 'a') str[x] = s[i];
        else str[x] = 'a';
        res += mp[str];
        mp[str]++;
    }
    cout << res;
    return 0;
}



E - Kth Number

难度: ⭐⭐⭐⭐



F - substr = S

难度: ⭐⭐⭐⭐⭐