总结
一眨眼，一天又过去了嘿嘿。今天鸽子回归，热烈祝贺！鼓掌！今天是做的练习赛，早上三道题，一道矩阵快速幂 + 拓展欧几里德，还有两道模拟。感觉都挺简单的，就是最后一道题的数据把我恶心到了。题目说链的长度是偶数，结果样例有奇数就算了，还有个点只有一个点的链，把我的判断端点给卡了，生气。
哦对了，今天早上教室里面还飞进了一只小鸟。很漂亮。可爱。(●'◡'●)。
题解
就简单说一下吧，模拟题，也没有什么好讲的。
T1
容易发现是 fib 数列的第 n 项的 k 倍。矩阵快速幂求一下再求一下逆元就可以。[[数论]] [[矩阵快速幂]] [[拓展欧几里得]]
T2
要求判断 ipv6 地址是否合法并且将其展开成完整形式。也不难，照着题意写一些就行。 [[模拟]]
T3
记录一个点从这里起始过没有。如果后来回到起点那肯定不行。否则每次枚举走路，走一走就行，也不是很难的样子。最短就用 bfs 就可以。bfs 的部分都是复制的，其实写不了多少。为了好看，这里贴上代码。
#include <bits/stdc++.h>
using namespace std;
#define N 55
using ll = long long;
int n;
ll t;
char s[N][N];
#define p(x, y) (x * n + y)
bool vis[N][N];
int f[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};//N, E, S, W
#define hf(x, y) (x >= 0 && x < n && y >= 0 && y < n)
bool vi[N][N];
struct lc {
int x, y, dis;
};
ll walk(int& x, int& y) {
ll tot = 0;
switch(s[x][y]) {
case '*': {
int bc = 1, dir = 0;
while (1) {
for (int i = 0; i < bc; ++i) {
++tot;
x += f[dir][0], y += f[dir][1];
if (!hf(x, y) || s[x][y] != '*') {
return tot;
}
}
dir = (dir + 1) % 4;
if (!(dir & 1)) ++bc;
}
break;
}
case 'I': {
int tx = x, ty = y, mad = 0;
memset(vi, 0, sizeof(vi));
queue<lc> q;
q.push({tx, ty, 0});
vi[tx][ty] = 1;
while (!q.empty()) {
auto [nx, ny, dis] = q.front();
q.pop();
if (dis > mad) tx = nx, ty = ny, mad = dis;
else if (dis == mad) {
if (nx < tx) tx = nx, ty = ny;
else if (nx == tx && ty < ny) ty = ny;
}
for (int i = 0; i < 4; ++i) {
int tox = nx + f[i][0], toy = ny + f[i][1];
if (!hf(tox, toy) || vi[tox][toy] || s[tox][toy] != 'I') continue;
vi[tox][toy] = 1;
q.push({tox, toy, dis + 1});
}
}
x = tx, y = ty;
tot = mad;
for (int i = 0; i < 2; ++i) {
x += f[0][0], y += f[0][1];
++tot;
if (!hf(x, y)) return tot;
}
return tot;
break;
}
case 'B': {
memset(vi, 0, sizeof(vi));
int tx = x, ty = y, mid = 1e9;
queue<lc> q;
q.push({tx, ty, 0});
vi[tx][ty] = 1;
while (!q.empty()) {
auto [nx, ny, dis] = q.front();
q.pop();
int flg = 0;
for (int i = 0; i < 4; ++i) {
int tox = nx + f[i][0], toy = ny + f[i][1];
if (hf(tox, toy)) flg += s[tox][toy] == 'B';
if (!hf(tox, toy) || vi[tox][toy] || s[tox][toy] != 'B') continue;
vi[tox][toy] = 1;
q.push({tox, toy, dis + 1});
}
// assert(flg > 0);
if (flg <= 1 && dis < mid) tx = nx, ty = ny, mid = dis;
}
x = tx, y = ty, tot = mid;
for (int i = 0; i < 2; ++i) {
x += f[1][0], y += f[1][1];
++tot;
if (!hf(x, y)) return tot;
}
return tot;
break;
}
case 'W': {
memset(vi, 0, sizeof(vi));
int tx = x, ty = y, mad = 0;
queue<lc> q;
q.push({tx, ty, 0});
vi[tx][ty] = 1;
while (!q.empty()) {
auto [nx, ny, dis] = q.front();
q.pop();
int flg = 0;
for (int i = 0; i < 4; ++i) {
int tox = nx + f[i][0], toy = ny + f[i][1];
if (hf(tox, toy)) flg += s[tox][toy] == 'W';
if (!hf(tox, toy) || vi[tox][toy] || s[tox][toy] != 'W') continue;
vi[tox][toy] = 1;
q.push({tox, toy, dis + 1});
}
// assert(flg > 0);
if (flg <= 1 && dis > mad) tx = nx, ty = ny, mad = dis;
}
x = tx, y = ty, tot = mad;
for (int i = 0; i < 2; ++i) {
x += f[3][0], y += f[3][1];
++tot;
if (!hf(x, y)) return tot;
}
return tot;
break;
}
}
return 0;
}
int main() {
freopen("adventure.in", "r", stdin);
freopen("adventure.out", "w", stdout);
while (~scanf("%d%lld", &n, &t) && (n != 0 || t != 0)) {
for (int i = 0; i < n; ++i) {
scanf("%s", s[i]);
}
int w, h;
ll tim = 0;
scanf("%d%d", &w, &h);
memset(vis, 0, sizeof(vis));
while (tim <= t) {
if (vis[w][h]) {
tim = 1e18;
break;
}
vis[w][h] = 1;
ll ys = walk(w, h);
tim += ys;
if (!hf(w, h)) break;
}
tim <= t ? printf("%lld\n", tim) : puts("Die hard");
}
return 0;
}
其它
把昨天 T3 调了。后来发现是一个弱智错误。这里要打上重点。以后默认初始化 stuct 的时候千万不要用全局变量或者非常量进行初始化！太恶心拉！要记住！不然初始化时的值是0阿！分数也会变成0阿！
下午写了去年 noip T4。那个线段树。感觉还是很神奇的。晚上要做一个可持久化线段树的专题。在这里。还是很好玩的。这周又要结束了阿。看起来。只有一周了。有一些不安和期待。希望明天会更好！
标签：11,总结,tox,toy,tx,ty,int,vi,2023 From： https://www.cnblogs.com/huasushis/p/17823126.html