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;
}