NOIP模拟测试18

╰+哭是因爲堅強的太久メ 2021-10-23 16:44 321阅读 0赞

本博客禁止sjzyz观看

为什么会变成这样呢……第一次有了秒切的T1，又有了想出了正解的T2。两件快乐事情重合在一起。而这两份快乐，又给我带来更多的快乐。得到的，本该是像梦境一般幸福的时间……但是，为什么，会变成这样呢……

为什么T2会爆炸呢

Problem A:引子

劲爆大模拟，自从我用Python写了个2048后我最喜欢大模拟了（逃

大体思路就是每个矩形的侧边从下到上，靠下的水管导向的矩形必被先填满。

大力%你即可AC（

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cctype>
      2 #include <cmath>
      3 #include <cstdio>
      4 #include <cstdlib>
      5 #include <cstring>
      6 #include <ctime>
      7 #include <algorithm>
      8 #include <bitset>
      9 #include <complex>
     10 #include <deque>
     11 #include <iostream>
     12 #include <map>
     13 #include <queue>
     14 #include <set>
     15 #include <stack>
     16 #include <string>
     17 #include <utility>
     18 #include <vector>
     19 
     20 int n, m, lx, ly;
     21 char matrix[1005][1005];
     22 bool vis[1005][1005];
     23 const int dx[8] = {
         1, -1, 0, 0, 1, 1, -1, -1};
     24 const int dy[8] = {
         0, 0, 1, -1, 1, -1, 1, -1};
     25 struct Node {
     26     int x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4;
     27 } node[1000005];
     28 std::vector<int> ans;
     29 
     30 void find(int id, int x, int y) {
     31     memset(vis, 0, sizeof(vis));
     32     std::queue<int> qx, qy;
     33     qx.push(x), qy.push(y);
     34     vis[x][y] = 1;
     35     int sx = x, sy = y;
     36     while (!qx.empty()) {
     37         x = qx.front(), y = qy.front();
     38         qx.pop(), qy.pop();
     39         for (int i = 0; i < 8; i++) {
     40             int xx = x + dx[i], yy = y + dy[i];
     41             if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
     42             if (matrix[xx][yy] == '+') {
     43                 if (xx < sx && yy < sy)
     44                     node[id].x_1 = xx, node[id].y_1 = yy;
     45                 if (xx < sx && yy > sy)
     46                     node[id].x_2 = xx, node[id].y_2 = yy;
     47                 if (xx > sx && yy < sy)
     48                     node[id].x_3 = xx, node[id].y_3 = yy;
     49                 if (xx > sx && yy > sy)
     50                     node[id].x_4 = xx, node[id].y_4 = yy;
     51                 continue;
     52             }
     53             if (!vis[xx][yy] && matrix[xx][yy] != '|' && matrix[xx][yy] != '-')
     54                 vis[xx][yy] = 1, qx.push(xx), qy.push(yy);
     55         }
     56     }
     57 }
     58 
     59 int calc(int x, int y) {
     60     int tmp = 0;
     61     while (isdigit(matrix[x][y])) y--;
     62     y++;
     63     for (y; isdigit(matrix[x][y]); y++)
     64         tmp = tmp * 10 + matrix[x][y] - '0';
     65     return tmp;
     66 }
     67 
     68 int findId(int x, int y) {
     69     if (isdigit(matrix[x][y])) return calc(x, y);
     70     memset(vis, 0, sizeof(vis));
     71     std::queue<int> qx, qy;
     72     qx.push(x), qy.push(y);
     73     vis[x][y] = 1;
     74     while (!qx.empty()) {
     75         x = qx.front(), y = qy.front();
     76         qx.pop(), qy.pop();
     77         for (int i = 0; i < 4; i++) {
     78             int xx = x + dx[i], yy = y + dy[i];
     79             if (isdigit(matrix[xx][yy])) return calc(xx, yy);
     80             if (!vis[xx][yy] && matrix[xx][yy] != '|' && matrix[xx][yy] != '-')
     81                 vis[xx][yy] = 1, qx.push(xx), qy.push(yy);
     82         }
     83     }
     84 }
     85 
     86 int goDown(int x, int y) {
     87     while (1) {
     88         for (int i = 0; i <= 3; i++) {
     89             int xx =  x + dx[i], yy = y + dy[i];
     90             if (matrix[x][y] == '|' && matrix[xx][yy] == '-') 
     91                 return findId(xx + 1, yy);
     92             if ((matrix[xx][yy] == '-' || matrix[xx][yy] == '+' || 
     93                         matrix[xx][yy] == '|') && (xx != lx || yy != ly))
     94                 lx = x, ly = y, x = xx, y = yy;
     95         }
     96     }
     97 }
     98 
     99 void solve(int id) {
    100     for (int i = node[id].x_3; i >= node[id].x_1; i--) {
    101         if (matrix[i][node[id].y_1 - 1] == '-') {
    102             lx = i, ly = node[id].y_1;
    103             int tmp = goDown(i, node[id].y_1 - 1);
    104             solve(tmp);
    105             ans.push_back(tmp);
    106         } else if (matrix[i][node[id].y_2 + 1] == '-') {
    107             lx = i, ly = node[id].y_2;
    108             int tmp = goDown(i, node[id].y_2 + 1);
    109             solve(tmp);
    110             ans.push_back(tmp);
    111         }
    112     }
    113 }
    114 
    115 signed main() {
    116     freopen("clickbait.in", "r", stdin);
    117     freopen("clickbait.out", "w", stdout);
    118     scanf("%d%d", &n, &m);
    119     for (int i = 1; i <= n; i++)
    120         scanf("%s", matrix[i] + 1);
    121     for (int i = 1; i <= n; i++) {
    122         for (int j = 1; j <= m; j++) {
    123             if (isdigit(matrix[i][j])) {
    124                 int tmp = 0;
    125                 for (j; isdigit(matrix[i][j]); j++)
    126                     tmp = tmp * 10 + matrix[i][j] - '0';
    127                 --j;
    128                 find(tmp, i, j);
    129             }
    130         }
    131     }
    132     solve(1);
    133     for (auto i : ans)
    134         printf("%d\n", i);
    135     puts("1");
    136     return 0;
    137 }

%%%

Problem B:可爱精灵宝贝

思路很类似于[LG-P1220][] 关路灯。

玩家走过一段区间，这个区间内时间符合要求的宝可梦都会被捕捉。

玩家的移动有一条显然的贪心策略：他只会沿着目前的方向继续前进，或者调头扩展区间。

设f\[l\]\[r\]\[t\]\[0/1\]为玩家走了区间\[l,r\]，时间为t，0为他在左端点，1为在右端点。

关于数组开不下的问题，那么多房子没用，直接离散化就完事了。

DP随便乱搞一下就行了，主要考虑从目前的状态做出上面两种决策。

关于我是怎么死的：我贪空间把\[0/1\]那维压掉了，直接钦定玩家在l。

然后我写着写着忘了，r是从l开始枚举的。。。。

GG。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cctype>
      2 #include <cmath>
      3 #include <cstdio>
      4 #include <cstdlib>
      5 #include <cstring>
      6 #include <ctime>
      7 #include <algorithm>
      8 #include <bitset>
      9 #include <complex>
     10 #include <deque>
     11 #include <iostream>
     12 #include <map>
     13 #include <queue>
     14 #include <set>
     15 #include <stack>
     16 #include <string>
     17 #include <utility>
     18 #include <vector>
     19 
     20 int n, k, m, mxt;
     21 int f[105][105][2005], a[105], b[105], t[105], qwq[105], ans;
     22 
     23 inline int read() {
     24     int a = 0; char c = getchar();
     25     while (!isdigit(c)) c = getchar();
     26     while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
     27     return a;
     28 }
     29 
     30 bool QAQ(int x, int y) {
     31     return a[x] < a[y];
     32 }
     33 
     34 signed main() {
     35     //freopen("go.in", "r", stdin);
     36     //freopen("go.out", "w", stdout);
     37     n = read(), k = read(), m = read();
     38     a[0] = k, b[0] = 0, t[0] = 1, qwq[0] = 0;
     39     for (int i = 1; i <= m; i++) {
     40         a[i] = read(), b[i] = read(), t[i] = read();
     41         mxt = std::max(mxt, t[i]);
     42         qwq[i] = i;
     43     }
     44     std::sort(qwq, qwq + 1 + m, QAQ);
     45     for (int T = 1; T <= mxt; T++) {
     46         for (int l = 0; l <= m; l++) {
     47             for (int r = 0; r <= m; r++) {
     48                 f[l][r][T] = -1;
     49             }
     50         }
     51     }
     52     for (int i = 0; i <= m; i++)
     53         if (a[qwq[i]] == k) f[i][i][1] = 0;
     54     for (int T = 1; T <= mxt; ++T) {
     55         for (int l = 0; l <= m; l++) {
     56             for (int r = 0; r <= m; r++) {
     57                 if (f[l][r][T] != -1) {
     58                     int tim;
     59                     if (l <= r) {
     60                         if (l > 0) {
     61                             tim = T + a[qwq[l]] - a[qwq[l-1]];
     62                             if (tim <= t[qwq[l-1]])
     63                                 f[l-1][r][tim] = std::max(f[l-1][r][tim], 
     64                                         f[l][r][T] + b[qwq[l-1]]);
     65                             else
     66                                 f[l-1][r][tim] = std::max(f[l-1][r][tim],
     67                                         f[l][r][T]);
     68                         }
     69                         if (r < m) {
     70                             tim = T + a[qwq[r+1]] - a[qwq[l]];
     71                             if (tim <= t[qwq[r+1]])
     72                                 f[r+1][l][tim] = std::max(f[r+1][l][tim],
     73                                         f[l][r][T] + b[qwq[r+1]]);
     74                             else 
     75                                 f[r+1][l][tim] = std::max(f[r+1][l][tim],
     76                                         f[l][r][T]);
     77                         }
     78                     } else {
     79                         if (r > 0) {
     80                             tim = T + a[qwq[l]] - a[qwq[r-1]];
     81                             if (tim <= t[qwq[r-1]])
     82                                 f[r-1][l][tim] = std::max(f[r-1][l][tim], 
     83                                         f[l][r][T] + b[qwq[r-1]]);
     84                             else
     85                                 f[r-1][l][tim] = std::max(f[r-1][l][tim],
     86                                         f[l][r][T]);
     87                         }
     88                         if (l < m) {
     89                             tim = T + a[qwq[l+1]] - a[qwq[l]];
     90                             if (tim <= t[qwq[l+1]])
     91                                 f[l+1][r][tim] = std::max(f[l+1][r][tim],
     92                                         f[l][r][T] + b[qwq[l+1]]);
     93                             else 
     94                                 f[l+1][r][tim] = std::max(f[l+1][r][tim],
     95                                         f[l][r][T]);
     96                         }
     97                     }
     98                 }
     99                 ans = std::max(ans, f[l][r][T]);
    100             }
    101         }
    102     }
    103     return !printf("%d\n", ans);
    104 }

QAQ

Problem C:相互再归的鹅妈妈

我不知道这道题是怎么混到NOIP模拟赛的，这道题的难度远超NOIP了。

puts("1")骗了10分。。。

这道题我不会改，估计要等好长一段时间才能会做。。。

转载于:https://www.cnblogs.com/gekoo/p/11340092.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/a2527a3a2c6f4ebc9f42b64ca164aad1.png
[LG-P1220]: https://www.luogu.org/problem/P1220