NOIP模拟赛[红魔馆之旅]

NOIP模拟赛--红魔馆之旅

T1.门

题目大意 : 给定你一个长度为\(n\)的字符串, 如果\(n\)不是\(3\)的倍数就用\(\ \0\)补齐, 然后将所有的字符转成\(ASCII\)码后, 再转成八位的二进制, 如果不足八位就用\(0\)补齐高位, 最后将二进制按照六个一分组, 最后转成如下表所示的字符 :

题解 : 直接模拟就好了, 转成二进制, 然后按位分组, 把上图打个表输出就可以了

就是有一些细节注意一下就好了

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 4e3 + 5;
const char out[100]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";

int n, N, tot, len, res, o[maxn];

char s[maxn], ex[maxn][5], ans[maxn][5];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("door.in", "r", stdin);
freopen("door.out", "w", stdout);
#endif
n = read();

//for(register int i = 1; i <= n; i++) s[i] = getchar();

//printf("\n%s", s + 1);

gets(s + 1);

if(n % 3 == 1) res = 2;
else if(n % 3 == 2) res = 1;

N = n + res;

for(register int i = 1; i <= N; i += 3) {
tot++;
for(register int j = 0; j < 3; j++)
ex[tot][j] = s[i + j];
}

for(register int i = 1; i <= tot; i++) {
int cnt = 0, p = -1;
for(register int j = 0; j < 3; j++)
cnt |= (ex[i][j] << (2 - j) * 8);

for(register int j = 23; j >= 0; j--) {
if(j % 6 == 5) p++;
ans[i][p] |= (((cnt >> j) & 1) << (j % 6));
}

for(register int j = 0; j <= p; j++) o[++len] = ans[i][j];
}

for(register int i = 1; i <= res; i++) o[len - i + 1] = 64;

//len = len - 3 + n % 3;

for(register int i = 1; i <= len; i++) {
putchar(out[o[i]]);
if(i % 76 == 0) putchar('\n');
}
if(len % 76 != 0) putchar('\n');
return 0;
}
/*
57
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

*/

T2.逃离

题目大意 : 给你一张无向带权图, 这张图上有\(n\)个节点, \(m\)条边, 还有一个起点\(S\), 一个终点\(T\), 除此之外还有\(k\)个蝙蝠, 集合为\(S\)

一开始二小姐在\(S\)点上

每条边有两个权值\(p_i,q_i\), 二小姐走边权\(q_i\), 蝙蝠走边权\(q_i\), 如果二小姐和某一只蝙蝠相遇了, 蝙蝠和二小姐就会合体, 等价于一只蝙蝠, 问你\(k\)只蝙蝠, 和一个二小姐走到终点\(T\)的边权的和的最小值为多少

题解 : 首先我们设, \[ rnt = \sum_{i \in S} dis_{i, T} \] \(dis_{i, T}\)表示每只蝙蝠到终点\(T\)的最短路

我们考虑枚举一个相遇点\(i\), 最终的答案就是 \[ ans = rnt + min\{ min\{dis_{j,i}-dis_{j,T} | j \in S\} + dis_{S,i} + dis_{T, i}\} \] 关键点在于如何求出这个 \[ min\{dis_{j,i}-dis_{j,T} | j \in S\} \] 难道要求出每个蝙蝠到每个点的最短路, 这样很显然是\(k \cdot nlogn\)的, 这样只能那\(70pts\)那一档分

其实, 如何优化我已经写出来了, 我们发现这个最短路的差值都和\(j\) 有关, 我们不妨一开始直接把所有的蝙蝠所在的点直接丢到队列里去, 然后把这个点的距离初始值设为\(-dis_{j,T}\), 然后直接跑一遍\(SPFA\)就可以求出每个点的这个差值数组了

最后枚举一下这个\(i\)点, 更新一下答案就好了

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e4 + 5;
const int maxm = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m, k, S, T, bi[maxn], pos[maxn];
queue<int> st;

LL ans = 1ll << 60, rnt = 0;

struct Graph {
int cnt, head[maxn], dis[maxn], vis[maxn];
queue<int> q;

struct node {int to, nt, w;} e[maxm << 1];

inline void ini(int x, int y, int w) {e[++cnt] = (node) {y, head[x], w}; head[x] = cnt;}

inline void add(int x, int y, int w) {ini(x, y, w); ini(y, x, w);}

inline void SPFA() {
memset(vis, 0, sizeof(vis));

while(!q.empty()) {
int now = q.front(); q.pop(); vis[now] = 0;

for(register int i = head[now]; i; i = e[i].nt) {
int v = e[i].to;
if(dis[v] > dis[now] + e[i].w) {
dis[v] = dis[now] + e[i].w;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
} G1, G2, G3;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
#endif
n = read(); m = read(); k = read(); S = read(); T = read();

for(register int i = 1; i <= k; i++) pos[read()]++;

for(register int i = 1; i <= m; i++) {
int x = read(), y = read(), w1 = read(), w2 = read();
G1.add(x, y, w1); G2.add(x, y, w1);
G3.add(x, y, w2);
}

//G1.SPFA(st);
G2.q.push(T); memset(G2.dis, 0x3f, sizeof(G2.dis));
G2.dis[T] = 0; G2.SPFA();

G3.q.push(S); memset(G3.dis, 0x3f, sizeof(G3.dis));
G3.dis[S] = 0; G3.SPFA();

for(register int i = 1; i <= n; i++) {
if(pos[i]) {
rnt += 1ll * pos[i] * G2.dis[i];
G1.dis[i] = -G2.dis[i]; G1.q.push(i);
}
else G1.dis[i] = inf;
}

G1.SPFA();

for(register int i = 1; i <= n; i++)
ans = min(ans, 1ll * G1.dis[i] + 1ll * G2.dis[i] + 1ll * G3.dis[i]);

cout << ans + rnt;
return 0;
}

T3.擦弹

题目大意 : 有\(n\)个格子, 和四个二小姐的分身, 一开始每个分身都在\(1\)号格子, 每一个时刻\(i\)二小姐可以将任意一个分身向前移动一步, 对于第\(i\)个时刻的第\(j\)个格子, 每个分身会受到的伤害为\(G_{i,j}\), 对于这个时刻移动的分身可以得到\(G_{i,j-1}\)的分数, 要求求出在所有分身受到的总伤害最小的情况下, 最多可以得到多少分, 输出最小伤害和最大得分

题解 : 这题很显然是一个\(dp\), 而且这个\(dp\)也非常好想到, 我们先不管第二问, 先考虑第一问

我们设\(f[i][j][k][v]\), 为第\(1\)个分身走了\(i\)步, 第二个分身走了\(j\)步, 第三个分身走了\(k\)步, 第四个分身走了\(v\)步的所受到的最小伤害值

因为知道了每个分身走的步数就相当于知道了当前的时刻是多少, 所以当前时刻的这一维可以直接扔掉不管

转移很显然有 :

设当前时刻\(tim = i + j + k + v\), 四个分身受到的总伤害为 \[ Q = G[tim][i + 1] + G[tim][j + 1] + G[tim][k + 1] + G[tim][v + 1] \]

\[ f[i][j][k][v] = min\begin{cases} f[i - 1][j][k][v] + Q \ \ \ \ if \ \ \ \ i > 0\\ f[i][j - 1][k][v] + Q \ \ \ \ if \ \ \ \ j > 0\\ f[i][j][k - 1][v] + Q \ \ \ \ if \ \ \ \ k > 0\\ f[i][j][k][v - 1] + Q \ \ \ \ if \ \ \ \ v > 0\end{cases} \] 这样我们就很简单的得到了第一问的答案, 既然第一问都已经求出来了, 第二问很显然也不是问题

我们设\(g[i][j][k][v]\)为第\(1\)个分身走了\(i\)步, 第二个分身走了\(j\)步, 第三个分身走了\(k\)步, 第四个分身走了\(v\)步的所得到的最大分数

我们直接在转移\(f\)的时候考虑, 如果从上个状态转移过来的\(f\)值小于当前值, 那就直接把上个状态的\(g\)赋过来并加上当前时刻的得分, 否则如果\(f\)值相同, 那么直接取个\(max\)就好了

问题被完美的解决了

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e2 + 5;
const int maxm = 4e2 + 5;

int n, G[maxm][maxm], f[2][maxn][maxn][maxn], g[2][maxn][maxn][maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("graze.in", "r", stdin);
freopen("graze.out", "w", stdout);
#endif
n = read();

for(register int i = 1; i <= 4 * (n - 1); i++)
for(register int j = 1; j <= n; j++) G[i][j] = read();

memset(f, 0x3f, sizeof(f));
//f[0][0][0][0] = 0;

for(register int i = 0; i < n; i++) {
int t = i & 1, t0 = t ^ 1;
memset(f[t], 0x3f, sizeof(f[t]));
memset(g[t], 0, sizeof(g[t]));
if(i == 0) f[0][0][0][0] = 0;

for(register int j = 0; j < n; j++)
for(register int k = 0; k < n; k++)
for(register int v = 0; v < n; v++) {
if(!i && !j && !k && !v) continue;
int tim = i + j + k + v;
int z = G[tim][i + 1] + G[tim][j + 1] + G[tim][k + 1] + G[tim][v + 1];
if(i) {
if(f[t0][j][k][v] + z < f[t][j][k][v]) {
f[t][j][k][v] = f[t0][j][k][v] + z;
g[t][j][k][v] = g[t0][j][k][v] + G[tim][i];
}
else if(f[t0][j][k][v] + z == f[t][j][k][v])
g[t][j][k][v] = max(g[t][j][k][v], g[t0][j][k][v] + G[tim][i]);
}
if(j) {
if(f[t][j - 1][k][v] + z < f[t][j][k][v]) {
f[t][j][k][v] = f[t][j - 1][k][v] + z;
g[t][j][k][v] = g[t][j - 1][k][v] + G[tim][j];
}
else if(f[t][j - 1][k][v] + z == f[t][j][k][v])
g[t][j][k][v] = max(g[t][j][k][v], g[t][j - 1][k][v] + G[tim][j]);
}
if(k) {
if(f[t][j][k - 1][v] + z < f[t][j][k][v]) {
f[t][j][k][v] = f[t][j][k - 1][v] + z;
g[t][j][k][v] = g[t][j][k - 1][v] + G[tim][k];
}
else if(f[t][j][k - 1][v] + z == f[t][j][k][v])
g[t][j][k][v] = max(g[t][j][k][v], g[t][j][k - 1][v] + G[tim][k]);
}
if(v) {
if(f[t][j][k][v - 1] + z < f[t][j][k][v]) {
f[t][j][k][v] = f[t][j][k][v - 1] + z;
g[t][j][k][v] = g[t][j][k][v - 1] + G[tim][v];
}
else if(f[t][j][k][v - 1] + z == f[t][j][k][v])
g[t][j][k][v] = max(g[t][j][k][v], g[t][j][k][v - 1] + G[tim][v]);
}
}
}

cout << f[(n - 1) & 1][n - 1][n - 1][n - 1] << " " << g[(n - 1) & 1][n - 1][n - 1][n - 1];
return 0;
}

Summary

  • 有些题目不仅仅是要思考, 有时候把式子写在纸上可以更快的看出做法
  • \(dp\)转移方程的时候, 不要为了偷懒就直接把类似的转移式子\(copy\)下来, 不然有些东西很可能会忘记修改, 重新打一遍更加保险
  • 打模拟题的时候细心一点, 尽量一遍打对, 这样可以节约大量时间