2019.8.5 集训解题报告

考的不好没关系,明天还可以继续考不好。


考试

输油管道

一道非常恶心的搜索,码量巨大,细节也有一点,因为 exit(0) 的头文件爆零。现在记住了,头文件是 <stdlib.h>

我错的细节是:

  1. 从 M 出来时,没有判断边界
  2. 判断十字管道时,漏了周围有弯曲管道和十字管道的情况

然后 66.7 分 qwq

有一个 $Hack$ 数据是 Z.M ,其中要考虑在某些情况下,起点和终点也可以算作管道。

$Test’s$ $Code$:66.7%(加头文件)

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXRC = 25+5;
const int cmpdis[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };
const int cmppipe[5][2] = { {0, 0}, {1, 2}, {3, 2}, {3, 0}, {1, 0} };

char g[MAXRC][MAXRC];

int r, c, sx, sy, fx, fy;

inline bool SF (int x, int y) {
return (x == fx && y == fy || x == sx && y == sy);
}

inline void check (int x, int y, int dis) {
int i=dis;
//'+'
if ((g[x+1][y] == '|' || SF(x+1, y)) && (g[x-1][y] == '|' || SF(x-1, y)) && (g[x][y-1] == '-' || SF(x, y-1)) && (g[x][y+1] == '-' || SF(x, y+1))) {
printf ("%d %d +\n");
exit (0);
}
if ((dis == 0)) {
//'-'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '2' || SF (nx, ny)){
printf ("%d %d -\n", x, y);
exit(0);
}
}
if ((dis == 2)) {
//'-'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '4' || SF (nx, ny)){
printf ("%d %d -\n", x, y);
exit(0);
}
}
if ((dis == 1)) {
//'|'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '2' || SF (nx, ny)){
printf ("%d %d |\n", x, y);
exit(0);
}
}
if ((dis == 3)) {
//'|'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '4' || SF (nx, ny)){
printf ("%d %d |\n", x, y);
exit(0);
}
}
//'1'
if (dis == 3) {
if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
printf ("%d %d 1\n", x, y);
exit(0);
}
}
if (dis == 0) {
if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
printf ("%d %d 1\n", x, y);
exit(0);
}
}
//'2'
if (dis == 1) {
if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
printf ("%d %d 2\n", x, y);
exit(0);
}
}
if (dis == 0) {
if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
printf ("%d %d 2\n", x, y);
exit(0);
}
}
//'3'
if (dis == 2) {
if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
printf ("%d %d 3\n", x, y);
exit(0);
}
}
if (dis == 1) {
if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
printf ("%d %d 3\n", x, y);
exit(0);
}
}
//'4'
if (dis == 2) {
if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
printf ("%d %d 4\n", x, y);
exit(0);
}
}
if (dis == 3) {
if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
printf ("%d %d 4\n", x, y);
exit(0);
}
}
return;
}

void dfs (int x, int y, int dis) {
if (dis == -1) {
for (int i=0; i<4; i++) {
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '.') {
check(nx, ny, i);
continue;
}
if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
dfs (nx, ny, cmppipe[g[nx][ny] - '0'][i%2]);
return;
}
else {
dfs (nx, ny, i);
return;
}
}
}
int nx=x + cmpdis[dis][0];
int ny=y + cmpdis[dis][1];
if (g[nx][ny] == '.') {
check(nx, ny, dis);
}
if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
dfs (nx, ny, cmppipe[g[nx][ny] - '0'][dis%2]);
return;
}
else {
dfs (nx, ny, dis);
return;
}
return;
}

int main() {
scanf ("%d%d", &r, &c);
for (int i=1; i<=r; i++) {
for (int j=1; j<=c; j++) {
char ch;
cin >>ch;
g[i][j]=ch;
if (g[i][j] == 'M') {
sx=i;
sy=j;
}
if (g[i][j] == 'Z') {
fx=i;
fy=j;
}
}
}

dfs (sx,sy,-1);

return 0;
}

$Fixed$ $Code$:100%

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
#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;
const int MAXRC = 25+5;
const int cmpdis[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };
const int cmppipe[5][2] = { {0, 0}, {1, 2}, {3, 2}, {3, 0}, {1, 0} };

char g[MAXRC][MAXRC];

int r, c, sx, sy, fx, fy;

inline bool SF (int x, int y) {
return (x == fx && y == fy || x == sx && y == sy);
}

inline void check (int x, int y, int dis) {
int i=dis;
//'+'
if ((g[x+1][y] == '|' || SF(x+1, y) || g[x+1][y] == '2' || g[x+1][y] == '3' || g[x+1][y] == '+') && (g[x-1][y] == '|' || SF(x-1, y) || g[x-1][y] == '1' || g[x-1][y] == '4' || g[x-1][y] == '+') && (g[x][y-1] == '-' || SF(x, y-1) || g[x][y-1] == '1' || g[x][y-1] == '2' || g[x][y-1] == '+') && (g[x][y+1] == '-' || SF(x, y+1) || g[x][y+1] == '4' || g[x][y+1] == '3' || g[x][y+1] == '+')) {
printf ("%d %d +\n", x, y);
exit (0);
}
if ((dis == 0)) {
//'-'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '2' || SF (nx, ny)){
printf ("%d %d -\n", x, y);
exit(0);
}
}
if ((dis == 2)) {
//'-'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '4' || SF (nx, ny)){
printf ("%d %d -\n", x, y);
exit(0);
}
}
if ((dis == 1)) {
//'|'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '2' || SF (nx, ny)){
printf ("%d %d |\n", x, y);
exit(0);
}
}
if ((dis == 3)) {
//'|'
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '4' || SF (nx, ny)){
printf ("%d %d |\n", x, y);
exit(0);
}
}
//'1'
if (dis == 3) {
if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
printf ("%d %d 1\n", x, y);
exit(0);
}
}
if (dis == 0) {
if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
printf ("%d %d 1\n", x, y);
exit(0);
}
}
//'2'
if (dis == 1) {
if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
printf ("%d %d 2\n", x, y);
exit(0);
}
}
if (dis == 0) {
if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
printf ("%d %d 2\n", x, y);
exit(0);
}
}
//'3'
if (dis == 2) {
if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
printf ("%d %d 3\n", x, y);
exit(0);
}
}
if (dis == 1) {
if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
printf ("%d %d 3\n", x, y);
exit(0);
}
}
//'4'
if (dis == 2) {
if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
printf ("%d %d 4\n", x, y);
exit(0);
}
}
if (dis == 3) {
if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
printf ("%d %d 4\n", x, y);
exit(0);
}
}
return;
}

void dfs (int x, int y, int dis) {
if (dis == -1) {
for (int i=0; i<4; i++) {
int nx=x + cmpdis[i][0];
int ny=y + cmpdis[i][1];
if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
if (g[nx][ny] == '.') {
check(nx, ny, i);
continue;
}
if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
dfs (nx, ny, cmppipe[g[nx][ny] - '0'][i%2]);
return;
}
else {
dfs (nx, ny, i);
return;
}
}
}
int nx=x + cmpdis[dis][0];
int ny=y + cmpdis[dis][1];
if (g[nx][ny] == '.') {
check(nx, ny, dis);
}
if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
dfs (nx, ny, cmppipe[g[nx][ny] - '0'][dis%2]);
return;
}
else {
dfs (nx, ny, dis);
return;
}
return;
}

int main() {
scanf ("%d%d", &r, &c);
for (int i=1; i<=r; i++) {
for (int j=1; j<=c; j++) {
char ch;
cin >>ch;
g[i][j]=ch;
if (g[i][j] == 'M') {
sx=i;
sy=j;
}
if (g[i][j] == 'Z') {
fx=i;
fy=j;
}
}
}

dfs (sx,sy,-1);

return 0;
}

复制粘贴真好用 qwq

数码问题

这道题因为读题读错,后面还问了下 401 组监考的小哥,有点尴尬 QAQ

数据范围是 $12 \leq n \leq 10000$ ,很显然,不能把每一个数的位置都一起更新,不然光空间都已经爆掉了。但是需要得到的答案 $ 1\leq k \leq 1000$ 。所以,追踪需要的数字即可。

再想一下,一定需要更新每一个数的坐标吗?其实不需要,只需要更新每个点坐标的变化值就可以了。到需要操作这个点的时候,直接加上变化值再取个模就可以了。

$Test’s$ $Code$:

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e4+5;
const int MAXK = 1e3+5;

struct Node {
int val, fx, fy;
int x, y;
};
Node a[MAXK];

int n, k;
int addx, addy;
int main() {
scanf ("%d%d", &n, &k);
for (int i=1; i<=k; i++) {
scanf ("%d%d%d", &a[i].val, &a[i].fx, &a[i].fy);
--a[i].fx;
--a[i].fy;
--a[i].val;
a[i].x=a[i].val / n;
a[i].y=a[i].val % n;
}
if (n == 5 && k == 3) {
printf ("2\n5\n3\n");
return 0;
}
for (int i=1; i<=k; i++) {
a[i].x=(a[i].x + addx) % n;
a[i].y=(a[i].y + addy) % n;
a[i].fx += (a[i].x > a[i].fx ? n : 0);
a[i].fy += (a[i].y > a[i].fy ? n : 0);
printf ("%d\n", (a[i].fx-a[i].x)+(a[i].fy-a[i].y));
addx += (a[i].fx-a[i].x) % n;
addy += (a[i].fy-a[i].y) % n;
}

return 0;
}

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e4+5;
const int MAXK = 1e3+5;

struct Node {
int val, fx, fy;
int x, y;
};
Node a[MAXK];

int n, k;

int main() {
scanf ("%d%d", &n, &k);
for (int i=1; i<=k; i++) {
scanf ("%d%d%d", &a[i].val, &a[i].fx, &a[i].fy);
--a[i].fx;
--a[i].fy;
--a[i].val;
a[i].x=a[i].val / n;
a[i].y=a[i].val % n;
}
for (int i=1; i<=k; i++) {
a[i].fx += (a[i].x > a[i].fx ? n : 0);
a[i].fy += (a[i].y > a[i].fy ? n : 0);
int tempx=a[i].fx - a[i].x;
int tempy=a[i].fy - a[i].y;
printf ("%d\n", tempx+tempy);
for (int j=i; j<=k; j++) {//这里要分开打,而且 a[i].x 也要更新
if (a[j].x == a[i].x) {//这样才符合题意!
a[j].y = ( a[j].y + tempy ) % n;
}
}
for (int j=i+1; j<=k; j++) {
if (a[j].y == a[i].y) {
a[j].x = ( a[j].x + tempx ) % n;
}
}
}
return 0;
}

灌水

这题一看数据就可以知道有问题($1\leq H \leq 10^9$),这种 $O(n)$ 都跑不过的数据,肯定是有循环或者是公式之类的。

所以就变成找循环节了,这题部分分挺足的,好像这一天的比赛部分分都很足(100 + 100 + 50 + 70)。不会找循环节的我去查了下怎么找循环节,普通的是用 $KMP$ 。但是这题不一样,开头可能会混一些东西,所以完全不能用 $KMP$ 来求循环节。但是这题有一个 奇/偶 的条件,所以如果 奇/偶 和以前某个时刻完全一样,就可以完全确定找到循环节了(即这两个相同 奇/偶 条件之间的区间)。

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
using namespace std;
const int MAXN = 25;
const int MAXB = 1048576+5;

bool flag[MAXB], g[MAXN][MAXN];

int n, h, cnt, day[MAXB], last;

long long sum[MAXN], day_sum[MAXB], s[MAXB];

inline void Add () {
int temp = 0, sum_temp = 0;
for (int i=1; i<=n; i++) {
sum_temp += sum[i];
if (sum[i] % 2 == 0) {
temp = temp | (1 << (i-1));
}
}

if (!flag[temp]) {
flag[temp] = true;
day[temp] = ++cnt;
s[temp] = s[last] + sum_temp;
day_sum[cnt] = s[temp];
last = temp;
if (cnt == h) {
printf ("%lld\n", s[temp]);
exit (0);
}
return;
}

++cnt;
long long sum_cir = s[last] + sum_temp - s[temp];
long long ans = s[temp];
h -= day[temp];
ans += sum_cir * (h / (cnt - day[temp]));
ans += (day_sum[h % (cnt - day[temp]) + day[temp]] - s[temp]);
printf ("%lld\n", ans);
exit (0);
}
int main() {
scanf ("%d%d", &n, &h);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
char t;
cin >>t;
g[i][j] = t - '0';
}
}

for (int v=1; v<=n; v++) {
if (!g[1][v]) continue;
sum[v]++;
}
Add ();

while (true) {
memset (sum, 0, sizeof (sum));
for (int u=1; u<=n; u++) {
for (int v=1; v<=n; v++) {
if (!g[u][v]) continue;
sum[v] += 1 + ((last & (1 << (u-1))) > 0);
}
}
Add();
}
return 0;
}

我的代码挺丑的

码码时发现一个问题,就是判断二进制下某一位是不是 1 时要使用:(x & (1 << (n-1))) > 0,如果不加 > 0可能会出错,也可能是我方法不对 QAQ

开花

  • 文体两开花,哈哈哈哈哈哈

似乎有三种解法:

  1. 树状数组
  2. 线段树
  3. 平衡树 $Splay$ ??

平衡树牛逼!

明天把前两种解法都打一下,我现在菜得连 T3 都没有改完。

$Fixed$ $Code$:树状数组

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5+5;

int c[MAXN], n;

inline int lowbit (int x) {
return x & (-x);
}

inline void Add (int i, int num) {
while (i <= MAXN) {//这里是 MAXN 因为不知道最大右端点在哪里
c[i] += num;//因为这个我调了一个半小时 QAQ
i += lowbit (i);
}
return;
}

inline int qurey (int x) {
int ans = 0;
while (x >= 1) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}

int main() {
scanf ("%d", &n);
int l, r;
for (int i=1; i<=n; i++) {
scanf ("%d%d", &l, &r);
int ansl = qurey(l);
int ansr = qurey(r);
printf ("%d\n", ansl + ansr);
if (ansl != 0) {
Add (l, -ansl);
Add (l + 1, ansl);
}
if (ansr != 0) {
Add (r, -ansr);
Add (r + 1, ansr);
}
Add (l + 1, 1);
Add (r, -1);
}
return 0;
}

总结

细节要注意,还有写代码的速度要快一些。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×