个人赛链接: https://www.luogu.com.cn/contest/120853#description
A.拯救oibh总部
解题思路
这题很第十四届蓝桥杯的D题有些相似, 我们可以从图的边界外开始入手去遍历整个图来得到答案;
神秘代码1
#include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 500 + 10, mod = 1e9 + 7;
int n, m, k, sum, maxn;
char g[N][N];
bool st[N][N];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
void bfs(int x,int y) {
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a <= n+1 && b >= 0 && b <= m+1 && g[a][b] != '*'&&!st[a][b]) {
if (g[a][b] == '0') sum--;
bfs(a, b);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
if (g[i][j] == '0') sum++;
}
}
bfs(0,0);
cout << sum;
return 0;
}
C.跳跃机器人
解题思路
这个题我第一眼看起来以为是dfs, 在经历了n次爆栈后还是默默地用bfs过了...
神秘代码
#include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e7 + 10, mod = 1e9 + 7;
int n, m, k, minn = 1e9;
bool st[N];
int d[N];
int g[4];
int bfs() {
memset(d, -1, sizeof d);
queue<int> q;
q.push(1);
d[1] = 0;
while (q.size()) {
int u = q.front();
q.pop();
g[1] = u * 2, g[2] = u + 1, g[3] = u - 1;
for (int i = 1; i <= 3; i++) {
int a = g[i];
if (d[a] == -1&&a<=n) {
d[a] = d[u] + 1;
q.push(a);
}
}
}
return d[n];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
cout << bfs();
return 0;
}
D.The Loathesome Hay Baler S
解题思路
因为题目中指明一个齿轮不会由两个齿轮带动, 所以我们在bfs过程中遍历所有齿轮找到所有它能够到的齿轮, 只要这个齿轮还未被其他齿轮带动就可以入队; 本题的一个难点在于寻找传动序列, 这里其实是用了一个邻接表在储存的, 遍历的时候只需要从工作齿轮开始倒着遍历即可;
本题的bfs和常规模板不同, 可以认识认识;
神秘代码
/#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1100 + 10, mod = 1e9 + 7;
int n, ini, ed;
int xt, yt;
double v[N];
bool st[N];
int mp[N];
struct str {
int x, y, r;
}wh[N];
void bfs() {
queue<int> q;
q.push(ini);
v[ini] = 10000;
st[ini] = true;
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if ((wh[i].x - wh[t].x) * (wh[i].x - wh[t].x) + (wh[i].y - wh[t].y) * (wh[i].y - wh[t].y) == (wh[i].r + wh[t].r) * (wh[i].r + wh[t].r)&&!st[i]) {
st[i] = true;
v[i] = v[t] * 1.0 * wh[t].r / wh[i].r;
mp[i] = t;
if (i == ed) return;
q.push(i);
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout .tie(0);
cin >> n >> xt >> yt;
for (int i = 1; i <= n; i++) {
int x, y, r;
cin >> x >> y >> r;
wh[i] = { x,y,r };
if (x == 0 && y == 0) ini = i;
else if (x == xt && y == yt) ed = i;
}
bfs();
double num =0;
for (int i = ed; i; i = mp[i]) num+=v[i];
cout << (int)num;
return 0;
}
E.电话号码
解题思路
签到题, 哈希和模拟;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k, minn = 1e9;
map<char, int> mp;
map<string, int> res;
void ini() {
int b = 1;
int d = 0;
for (int i = 0; i < 26; i++) {
char c = 'A' + i;
if (c == 'Q' || c == 'Z')continue;
d++;
if (d > 3) d = 1, b++;
mp[c] = b;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
ini();
while (n--) {
string s;
cin >> s;
string s2 = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
s2 += s[i];
if (s2.size() == 3) s2 += '-';
}
else if (s[i] >= 'A' && s[i] <= 'Z') {
char a = '1' + mp[s[i]];
s2 += a;
if (s2.size() == 3) s2 += '-';
}
}
res[s2]++;
}
bool f = false;
for (auto t : res) {
if (t.second > 1) {
cout << t.first << ' ' << t.second << endl;
f = true;
}
}
if (!f) cout << "No duplicates." << endl;
return 0;
}
F.Binary Land
解题思路
本题和后面的I题是本次训练赛最折磨我的两道题, 但是这两道题题型有些相似, 在我搞懂I后, F题也很快就看明白了; 与以往的bfs类型不同, 这两道题就是用了结构体来表示更加复杂的状态, 这也提醒了我bfs的队列中存的是状态, 一直以来自己都说不明白这点...
一开始我因为固有思想也是开了两个数组来分别表示两个企鹅到每个点的步数, 开了两个队列来存位置等等, 反正是越看越迷糊; 然后在看到题解的结构体后真的是非常痛苦... 开一个结构体str表示当前状态, 因素就是当前两只企鹅各自的位置以及走了多少步; 因为bfs的特性, 当时第一次两只企鹅都到达终点时, 此时的步数即为最小步数; 接下来就是正常的bfs路子, 遍历方向, 检查边界; 然后我们需要注意到样例给我们展示的撞墙操作, 企鹅可以往墙壁方向行动, 效果是原地不动, 所以我们更新后得到最后真正的坐标, 然后我们再去判断是否遇到蜘蛛网以及检查当前状态是否已经被标记过了(这里我们开了一个四维数组来存放坐标), 检查结束后, 符合要求的步数加一, 进入队列即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 30 + 10, mod = 1e9 + 7;
int n, m, num;
int m1, m2, g1, g2, x, y;
char g[N][N];
bool st[N][N][N][N];
int minn=1e9;
int dx[4] = { 1,0,-1,0 }, dyg[4] = { 0,1,0,-1 }, dym[4] = { 0,-1,0,1 };
struct str {
int x1, y1, x2, y2;
int step;
};
int bfs() {
queue<str> q;
str ini = { m1, m2, g1, g2 ,0};
q.push(ini);
while (q.size()) {
auto t = q.front();
q.pop();
if (g[t.x1][t.y1] == 'T' && g[t.x2][t.y2] == 'T') {
return t.step;
}
for (int i = 0; i < 4; i++) {
int a = t.x1 + dx[i], b = t.y1 + dym[i], c = t.x2 + dx[i], d = t.y2 + dyg[i], s = t.step+1;
if (a >= 1 && a <= n && b >= 1 && b <= m && c >= 1 && c <= n && d >= 1 && d <= m) {
if (g[a][b] == '#') a = t.x1, b = t.y1;
if (g[c][d] == '#') c = t.x2, d = t.y2;
if (st[a][b][c][d]|| g[a][b] == 'X' || g[c][d] == 'X') continue;
else {
str cre = { a,b,c,d,s};
st[a][b][c][d] = true;
q.push(cre);
}
}
}
}
return -1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
if (g[i][j] == 'M') m1 = i, m2 = j;
else if (g[i][j] == 'G') g1 = i, g2 = j;
else if (g[i][j] == 'T') x = i, y = j;
}
}
int res = bfs();
if (res == -1) cout << "no" << endl;
else cout << res;
return 0;
}
G.The Rock Game S
解题思路
读完题后根据n的范围很容易把二进制和题目联想到一起, 二进制表示当前游戏状态, 0表示没有石头, 1表示有石头; dfs对当前的状态进行遍历, 这里要注意dfs中u和num的定义, 我在这被坑了一下, 当时没多想就写的dfs(0,0), 认为第一个0是当前的状态, 第二个0是当前第几步, 答案要求输出0~2^n步; 但是, 在dfs函数里我们发现, a才是当前的状态, u是上一步的状态, 而num也是上一步是第几步; 所以dfs的截止条件是num = (2^n)-1, 而不是2^n; 理解这一点后我再来说说dfs函数, 我们遍历上一步的状态u的每一位, 如果有石头我们就搬走, 没有就放; 因为每个状态就不能重复, 所以还需要map用来标记; 用数组d来储存所有状态即可;
神秘代码
##include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, k, idx = 1;
bool st[N];
int d[N];
map<int, int> mp;
vector<int> v;
bool f = false;
void show() {
for (int i = 0; i <= k; i++) {
int a = d[i];
for (int j = 0; j < n; j++) {
if (a >> j & 1) printf("X");
else printf("O");
}
printf("\n");
}
}
void dfs(int u, int num) {
if (f) return;
if (num == k-1) {
if (d[k] == 0) {
show();
f = true;
}
return;
}
for (int i = 0; i < n; i++) {
int a;
if (u >> i & 1) a = u - (1 << i);
else a = u + (1 << i);
if (!mp[a]) {
mp[a]=1;
d[num+1] = a;
dfs(a, num + 1);
mp[a]=0;
}
}
}
signed main() {
scanf("%d", &n);
k = 1 << n;
dfs(0, 0);
return 0;
}
H.Binary search
解题思路
这个题真的很怪, 当我打算推导一下w对各个环节的影响时, 我发现题目给的代码已经给我写好了, 于是我糊里糊涂套上之后直接过了, 只能说是...针不戳;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 3e6 + 10, mod = 1e9 + 7;
int n, m, k, minn = 1e9;
bool st[N];
int q[N];
void dfs(int l, int r, int num) {
if (l == r) {
minn = min(minn, num);
return;
}
for (int w = 0; w <= 1; w++) {
int mid = l + r + w >> 1;
if (q[mid] - w < k) {
dfs(mid + !w, r, num + 1);
}
else dfs(l, mid - w, num + 1);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> q[i];
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> k;
minn = 1e9;
dfs(1, n, 0);
cout << minn << endl;
}
return 0;
}
I.Obstacle Course S
解题思路
我又爱又恨的一道题, 真有种打魂类游戏的感觉; 在前面的F题说过了, 用结构体表示状态, 因素有坐标, 方向d(我们用方向数组的下标表示方向, 起点没有方向就设为-1), 以及起点到这个坐标并且朝d方向时所经过的最少转折点num; 这个num就是本题最大的坑点, 也是折磨了我两个小时的地方, 这个等会用到的时候再说; 数组f[i][j]表示起点到(i,j)这个点所经历的最少转折点, 因为要求最小值所以初始化为无穷大; 注意f和num的区别, f没有细分方向, 是这个点的各个方向的num中的最小值;
然后就是bfs起手三件套, 起点初始化, 遍历方向, 检查边界和题目要求; 然后就来到了本题的重点, 根据方向分情况讨论,设上个点为a, 当前点为b, 如果a是起点或者a和b的方向相同, 那么此时b点状态中的num就等于a点状态中的num; 如果方向不同, 那么b的num就是a的num+1; 那么我们该如何判断是否入队呢, 还记得f[i][j]吗, 既然f是当前这个点的最优情况, 那么我们就把b的num和f进行比较, 如果num小于等于f, 那么说明沿着当前这个方向走可能会比f当前的那个方向要好, 所以我们就可以将其入队了; 如果已经到达终点, 就不用将其入队;
这个题给我提供了bfs的一种新的思路和想法, 所以这个题一定要好好看看;
神秘代码
#include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<pair<int, int>, int> PPI;
const int N = 100 + 10, mod = 1e9 + 7;
int n, m, num;
int x, y, x2, y2;
char g[N][N];
int f[N][N];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
struct str {
int x, y, d, num;
};
int bfs() {
memset(f, 0x3f, sizeof f);
queue<str> q;
str ini = { x,y,-1,0 };
q.push(ini);
f[x][y] = 0;
while (q.size()) {
auto t = q.front();
q.pop();
int t1 = t.x, t2 = t.y, d = t.d, num = t.num;
if (t1 == x2 && t2 == y2) continue;
for (int i = 0; i < 4; i++) {
int a = t1 + dx[i], b = t2 + dy[i];
if (a >= 1 && a <= n && b >= 1 && b <= n && g[a][b] != 'x') {
str cre;
cre.x = a, cre.y = b, cre.d = i;
if (d == -1 || i == d) {
if (f[a][b] >= num) {
f[a][b] = num;
cre.num = num;
q.push(cre);
}
}
else {
if (f[a][b] >= num + 1) {
f[a][b] = num + 1;
cre.num = num +1;
q.push(cre);
}
}
}
}
}
if (f[x2][y2] == 0x3f3f3f3f) return -1;
else return f[x2][y2];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> g[i][j];
if (g[i][j] == 'A') x = i, y = j;
else if (g[i][j] == 'B') x2 = i, y2 = j;
}
}
cout << bfs();
return 0;
}