多校冲刺 NOIP 20211030 模拟 (19)

10-30-2021 约 2411 字预计阅读 5 分钟

今天的考试考的好难受啊

Task 1 特殊字符串

写完dp数组（写成[n][n]了）以为是 $n^2$ 的，就没打。然后我尝试进行转化，转化成了有 $n$ 个线段，每个线段都有一个权值，要求线段不重叠，求权值最大值的问题。然后又不会了……

正解其实就是一个 $n*26$ 的转移，设 $dp[i][j]$ 表示枚举到第 $i$ 位，字符为 $j$ 的最大值。转移显然（一车人都切了）。对了，还需要把这个二元组的权值放到矩阵上。初始状态就是除了 dp[位置i][位置i对应的字符] 为1外其他都为-inf

 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


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
#define int int64_t

const int maxn = 100010;

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int mat[26][26];
int n, m;
string s;
int dp[1000010][26];

int32_t main() {
  freopen("shiki.in", "r", stdin);
  freopen("shiki.out", "w", stdout);
  cin >> n;
  cin >> s;
  cin >> m;
  For(i, 1, m) {
    char ch1, ch2;
    int val;
    cin >> ch1 >> ch2 >> val;
    mat[ch1 - 'a'][ch2 - 'a'] += val;
  }
  Set(dp, -0x3f);
  For(i, 1, n) {
    dp[1][s[i - 1] - 'a'] = 0;
  }
  For(i, 1, n) {
    For(j, 0, 25) {
      if (j == s[i - 1] - 'a') continue;
      dp[i][j] = dp[i - 1][j];
    }
    int mx = 0;
    For(j, 0, 25) { mx = max(mx, dp[i - 1][j] + mat[j][s[i - 1] - 'a']); }
    dp[i][s[i - 1] - 'a'] = mx;
  }
  int ans = 0;
  For(i, 0, 25) { ans = max(ans, dp[n][i]);}
  cout << ans << endl;
  return 0;
}

Task 2 宝可梦

垃圾题调一天，懒得重构了，最后打了215行

手模一下可以发现，一定可以走一圈再绕回来。所以所有经过的点组成了一个环，答案就是环上两点的距离。然后你码完会发现一个点会不止经过1次，那就把各个方向上的都存起来。然后你又会发现当第二次经过起始点时可能没有走完全程，这时可以把当前点当前方向有值作为边界。再处理一堆细节就行了

  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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 500010;

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int n, m, q;
vector<int> mat[maxn];
struct VAL {
  int pos[4];
};
vector<VAL> val[maxn];
pair<int, int> dl[4] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

#define UP 2
#define DOWN 0
#define LEFT 1
#define RIGHT 3

#define nxtx x + dl[(dir + 1) % 4].first
#define nxty y + dl[(dir + 1) % 4].second
#define gox x + dl[dir].first
#define goy y + dl[dir].second

void go(int dir, int &x, int &y) {
  x += dl[dir].first;
  y += dl[dir].second;
}

int cnt = 1;
void getAns(int dir, int x, int y, int xx, int yy) {
  // while (mat[nxtx][nxty] != 1) {
  //   val[gox][goy].pos[dir] = cnt;
  //   go(dir, x, y);
  //   cnt++;
  // }
  bool flg = 1;
  while (1) {
    // cout << x << ' ' << y << ' ' << cnt << endl;
    flg = 0;
    if (mat[gox][goy] == 1 || mat[nxtx][nxty] != 1) {
      if (mat[nxtx][nxty] != 1) {
        dir++;
        dir = (dir + 4) % 4;
      } else {
        dir--;
        dir = (dir + 4) % 4;
      }
    }
    if (mat[gox][goy] != 1) {
      if (val[gox][goy].pos[dir]) return;
      val[gox][goy].pos[dir] = cnt;
      go(dir, x, y);
      cnt++;
    }
  }
}
int main() {
  freopen("pokemon.in", "r", stdin);
  freopen("pokemon.out", "w", stdout);
  n = read<int>();
  m = read<int>();
  For(i, 0, m + 1) {
    mat[0].push_back(1);
    mat[n + 1].push_back(1);
  }
  int pp = 0, ppp = 0;
  For(i, 1, n) {
    mat[i].push_back(1);
    val[i].resize(m + 1);
    For(j, 1, m) {
      char ch = getchar();
      while (ch != '.' && ch != 'X') {
        ch = getchar();
      }
      if (ch == '.') {
        mat[i].push_back(0);
        if (pp == 0) {
          pp = i;
          ppp = j;
        }
      } else {
        mat[i].push_back(1);
      }
    }
    mat[i].push_back(1);
  }
  q = read<int>();
  getAns(RIGHT, pp, ppp, pp, ppp);
  For(i, 1, n) {
    For(j, 1, m) { cout << setw(4) << val[i][j].pos[0]; }
    cout << endl;
  }
  cout << endl;
  For(i, 1, n) {
    For(j, 1, m) { cout << setw(4) << val[i][j].pos[1]; }
    cout << endl;
  }
  cout << endl;
  For(i, 1, n) {
    For(j, 1, m) { cout << setw(4) << val[i][j].pos[2]; }
    cout << endl;
  }
  cout << endl;
  For(i, 1, n) {
    For(j, 1, m) { cout << setw(4) << val[i][j].pos[3]; }
    cout << endl;
  }
  cout << endl;
  int ccnt = cnt - 1;
  For(i, 1, q) {
    int x, y, xx, yy;
    x = read<int>();
    y = read<int>();
    xx = read<int>();
    yy = read<int>();
    char ch = getchar();
    while (!isalpha(ch)) {
      ch = getchar();
    }
    // cout <<ccnt << endl;
    if (ch == 'U') {
      go(UP, x, y);
      int minn = 0x3f3f3f3f;
      For(i, 0, 3) {
        if (val[xx][yy].pos[i]) {
          int tmp = val[xx][yy].pos[i];
          if (tmp <
              (val[x][y].pos[UP] - 1 == 0 ? ccnt : val[x][y].pos[UP] - 1)) {
            tmp += ccnt;
          }
          minn = min(minn, tmp);
        }
      }
      // minn++;

      cout << minn - (val[x][y].pos[UP] - 1 == 0 ? ccnt : val[x][y].pos[UP] - 1)
           << endl;
    }
    if (ch == 'D') {
      go(DOWN, x, y);
      int minn = 0x3f3f3f3f;
      For(i, 0, 3) {
        if (val[xx][yy].pos[i]) {
          int tmp = val[xx][yy].pos[i];
          if (tmp <
              (val[x][y].pos[DOWN] - 1 == 0 ? ccnt : val[x][y].pos[DOWN] - 1)) {
            tmp += ccnt;
          }
          minn = min(minn, tmp);
        }
      }
      // minn++;
      cout << minn - (val[x][y].pos[DOWN] - 1 == 0 ? ccnt
                                                   : val[x][y].pos[DOWN] - 1)
           << endl;
    }
    if (ch == 'L') {
      go(LEFT, x, y);
      int minn = 0x3f3f3f3f;
      For(i, 0, 3) {
        if (val[xx][yy].pos[i]) {
          int tmp = val[xx][yy].pos[i];
          if (tmp <
              (val[x][y].pos[LEFT] - 1 == 0 ? ccnt : val[x][y].pos[LEFT] - 1)) {
            tmp += ccnt;
          }
          minn = min(minn, tmp);
        }
      }
      // minn++;
      // cout << val[x][y].pos[LEFT] << endl;
      cout << minn - (val[x][y].pos[LEFT] - 1 == 0 ? ccnt
                                                   : val[x][y].pos[LEFT] - 1)
           << endl;
    }
    if (ch == 'R') {
      go(RIGHT, x, y);
      int minn = 0x3f3f3f3f;
      For(i, 0, 3) {
        if (val[xx][yy].pos[i]) {
          int tmp = val[xx][yy].pos[i];
          if (tmp < (val[x][y].pos[RIGHT] - 1 == 0
                         ? ccnt
                         : val[x][y].pos[RIGHT] - 1)) {
            tmp += ccnt;
          }
          minn = min(minn, tmp);
        }
      }
      // minn++;
      cout << minn - (val[x][y].pos[RIGHT] - 1 == 0 ? ccnt
                                                    : val[x][y].pos[RIGHT] - 1)
           << endl;
    }
    // cout << cnt << endl;
  }
  return 0;
}

Task 3 矩阵

垃圾dfs，题连看都没看（血亏）直接枚举每个点和它周围四个方向的值爆搜就完了

  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


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 40010;

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int n, m;
int getId(int x, int y) { return y + x * m; }
int val[maxn];
bool vis[maxn];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int ans = 1;
// void dfs(int x, int y, int rat, int cnt) {
//   if (x == 0 || y == 0) return;
//   if (rat == 0) {
//     For(i, 0, 3) {
//       if (max(mat[x][y], mat[x + dx[i]][y + dy[i]]) * 1.0 /
//                   min(mat[x][y], mat[x + dx[i]][y + dy[i]]) -
//               max(mat[x][y], mat[x + dx[i]][y + dy[i]]) /
//                   min(mat[x][y], mat[x + dx[i]][y + dy[i]]) ==
//           0) {
//         dfs(x + dx[i], y + dy[i],
//             max(mat[x][y], mat[x + dx[i]][y + dy[i]]) /
//                 min(mat[x][y], mat[x + dx[i]][y + dy[i]]),
//             cnt + 1);
//       }
//     }
//   } else {
//     bool flg = 0;
//     For(i, 0, 3) {
//       if (max(mat[x][y], mat[x + dx[i]][y + dy[i]]) * 1.0 /
//               min(mat[x][y], mat[x + dx[i]][y + dy[i]]) ==
//           rat) {
//         // if (vis[x + dx[i]][y + dy[i]] == rat) {
//         //   puts("-1");
//         //   exit(0);
//         // }
//         vis[x + dx[i]][y + dy[i]] = rat;
//         dfs(x + dx[i], y + dy[i], rat, cnt + 1);
//         flg = 1;
//       }
//     }
//     if (!flg) {
//       ans = max(ans, cnt);
//     }
//   }
// }
map<pair<int, int>, int> mp;
void dfs(int x, int y) {
  vis[getId(x, y)] = true;
  For(i, 0, 3) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx <= 0 || nx > n || ny <= 0 || ny > m) {
      continue;
    }
    if (val[getId(nx, ny)] == val[getId(x, y)]) {
      puts("-1");
      exit(0);
    }
    if (val[getId(nx, ny)] > val[getId(x, y)] &&
        val[getId(nx, ny)] % val[getId(x, y)] == 0) {
      if (!vis[getId(nx, ny)]) dfs(nx, ny);
      int ratio = val[getId(nx, ny)] / val[getId(x, y)];
      int cnt = 0;
      if (mp[{getId(nx, ny), ratio}] == 0) {
        cnt = 2;
      } else {
        cnt = mp[{getId(nx, ny), ratio}] + 1;
      }
      ans = max(ans, cnt);
      mp[{getId(x, y), ratio}] = max(mp[{getId(x, y), ratio}], cnt);
    }
  }
}
int main() {
  freopen("matrix.in", "r", stdin);
  freopen("matrix.out", "w", stdout);
  n = read<int>();
  m = read<int>();
  For(i, 1, n) {
    For(j, 1, m) { val[getId(i, j)] = read<int>(); }
  }
  For(i, 1, n) {
    For(j, 1, m) {
      if (!vis[getId(i, j)]) {
        dfs(i, j);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Task 4

我太菜，不会，请移步fengwu的牛批博客

目录

多校冲刺 NOIP 20211030 模拟 (19)

Task 1 特殊字符串

Task 2 宝可梦

Task 3 矩阵

Task 4