2023年11月9日总结

2023年11月9日总结

混氏新子 蒟蒻
  2023-11-09 22:54:36 2023-11-09 22:54:36 创建   2023-11-09 23:05:30 2023-11-09 23:05:30 更新    1.2k 字  5 分钟  

总结

一眨眼，一天又过去了嘿嘿。今天鸽子回归，热烈祝贺！鼓掌！今天是做的练习赛，早上三道题，一道矩阵快速幂 + 拓展欧几里德，还有两道模拟。感觉都挺简单的，就是最后一道题的数据把我恶心到了。题目说链的长度是偶数，结果样例有奇数就算了，还有个点只有一个点的链，把我的判断端点给卡了，生气。

哦对了，今天早上教室里面还飞进了一只小鸟。很漂亮。可爱。(●’◡’●)。

题解

就简单说一下吧，模拟题，也没有什么好讲的。

T1

容易发现是 fib 数列的第 n 项的 k 倍。矩阵快速幂求一下再求一下逆元就可以。[[数论]] [[矩阵快速幂]] [[拓展欧几里得]]

T2

要求判断 ipv6 地址是否合法并且将其展开成完整形式。也不难，照着题意写一些就行。 [[模拟]]

T3

记录一个点从这里起始过没有。如果后来回到起点那肯定不行。否则每次枚举走路，走一走就行，也不是很难的样子。最短就用 bfs 就可以。bfs 的部分都是复制的，其实写不了多少。为了好看，这里贴上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#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。那个线段树。感觉还是很神奇的。晚上要做一个可持久化线段树的专题。在这里 。还是很好玩的。这周又要结束了阿。看起来。只有一周了。有一些不安和期待。希望明天会更好！

  • 标题: 2023年11月9日总结
  • 作者: 混氏新子
  • 创建于 : 2023-11-09 22:54:36
  • 更新于 : 2023-11-09 23:05:30
  • 链接: https://blog.huasushis.cn/2023/2023年11月9日总结/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 圣诞树 圣诞树 2017 山东一轮集训 Day4」棋盘 题解 2017 山东一轮集训 Day4」棋盘 题解
推荐阅读
6.29 测试 6.29 测试 圣诞树 圣诞树
评论
此页目录
2023年11月9日总结
  1. 总结
  2. 题解
    1. T1
    2. T2
    3. T3
  3. 其它