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
难度: ⭐⭐⭐⭐⭐
- Beginner AtCoder Contest 295beginner atcoder contest 295 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 310 beginner atcoder contest 315