清北学堂csps2019-Day1

爆零!!!qwq

今天是集训第一天,上午的考试居然爆零了,有点出乎意料。。。

低仿机器人(robo,1s,64M)

  • 一道很恶心的大模拟,我考场以为调好了,结果。。。

    题目描述

    自从Dji 推出robomaster S1 机器人过后,小文就一直缠着爸爸想要一个机器人。妹想到爸爸最后竟然带了个低仿S1–R1 机器人回来。小文哭笑不得,不过低仿就低仿,不玩白不玩,他决定试试这个小机器人的能耐。
    小文给这个小机器人布置了$n\times m$ 的场地(场地外用障碍围住),在场地上设置了障碍、水池和靶子。其中,障碍是不可以通过并且无法用水晶弹打掉的,靶子无法通过、但是可以被水晶弹打掉,水池也无法通过、但是水晶弹可以通过水池。
    小文检查了一下小机器人,发现它的指令系统很简单。该系统中一共有6 种指令,指令的使用说明如下:
    “FT x” :该指令表示炮台的90°转动,其中$x\in [0,1],x\in Z$并且0、1 分别表示逆时针和顺时针。
    “FF i” :该指令表示填弹,填弹后弹仓剩余弹量减一,弹夹剩余弹量加一,其中$i\in [0,1]$且$i\in Z$,$i$ 为$1$ 表示所填水晶弹为大弹丸,为$0$ 表示所填水晶弹为小弹丸。
    “FE” :该指令表示发射水晶弹,水晶弹的发射方向同炮台的朝向,发射的水晶弹为最后一个填入弹夹的水晶弹,指令执行后弹夹容量减一。
    “WT x” :该指令表示机器人的90°转动, 其中$x\in [0,1],x\in Z$, 并且0、1 分别表示逆时针和顺时针。
    “WG y” :该指令表示机器人前进y 步,其中$y\in [0,max(m,n)),y\in Z$。
    “END” :该指令将返回“Complete”并停机,不同于编译器先编译后运行,END(及其他将造成停机的情况)后的指令均被无视。
    现在小文将要开始测试,但是为了避免自己的指令集让小机器人出现错误,小文给了你场地、小机器人的初始状态和指令集并拜托你帮他计算出小机器人的返回内容、停下的位置、打掉的靶子数量以及小机器人的状态。
    注意:
    (一)弹夹无弹的情况下将跳过FE 指令,弹仓无相应弹丸的情况下将跳过FF 指令;
    (二)大水晶弹一发打掉靶子,小水晶弹需两发打掉靶子,靶子打掉后变成空地可通过;
    (三)小机器人将在以下情况下返回“ERROR”并停机:
  • (1)在弹夹已满的情况下继续填弹;
  • (2)撞上障碍(包括未被打掉的靶子)或者撞进水池;
  • (3)指令后的参数不满足要求(例:“FE 10”);
  • (4)无“END”指令;

输入格式

输入文件的第一行为一个正整数t,表示该题有t 组数据。
对于每一组数据:
第1行为两个正整数n m
第$2$至$(n+1)$行,每行$m$个正整数,表示地图,其中$1$代表障碍,$2$代表靶子,$3$代表水池,$0$代表空地。
第$n+2$行有$6$个正整数,依次为:机器人横坐标$x$和纵坐标$y$,弹夹的容量$a$,弹仓内剩余大水晶弹量$b$,弹仓内剩余小水晶弹量$c$,小文的指令数量$k$。(弹夹初始容量默认为0,
炮台和机器人的默认朝向为向上)。
第$(n+3)$至$(n+3+k)$行,每行一个指令,指令的正确格式和正确参数见题目描述(数据中无双引号)(不满足要求的参数大小$\leq 10$,长度$\leq 3$)。

输出格式

输出文件共$t\times 4$ 行,其中对于每组数据:
第$1$行输出小机器人的返回内容(“Complete”或“ERROR”,不输出双引号)。
第$2$行输出小机器人停下的位置的横纵坐标(用空格隔开)。
第$3$行输出小机器人打掉的靶子数量h。
第$4$行依次输出炮台的朝向、机器人的朝向、弹仓剩余大水晶弹量、弹仓剩余小水晶弹量,用空格隔开,其中0、1、2、3 分别表示上左下右。
若机器人返回“ERROR”后停机,则输出数据为执行错误指令前的数据。(见样例1)

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
5 5
2 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
4 4 3 1 1 6
WG 4
FT 0
WG 1
FE
END
FF

输出样例

1
2
3
4
ERROR
0 4
0
1 0 1 1

这题怎么说呢,反正就写的麻烦,代码注释挺多,看代码吧。

  • 对了这题有几个坑点:
    1. 炮塔不随着车身旋转,也就是说,即使车身转了,炮塔仍然保持原来方向。
    2. 方向0,1,2,3分别代表上左下右而不是上下左右。
    3. 输入的时候,注意即使error了,依然要把接下来的指令输入,不然会出问题。
    4. 输入得getline,有可能有参数的操作却不输入参数。
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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#include<bits/stdc++.h>
using namespace std;

int T, n, m;
int a[209][209];
int val[209][209];
int stx, sty, q, b, c, k;
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
int fx;//炮塔方向
int dc_b, dc_s, djcnt;//弹舱大小弹药和弹夹当前弹药数量
stack<int> dj;
int robotfx;//车辆朝向
int nowx, nowy;//车辆当前位置
int cntbz;//打掉几个靶子
int endok;
bool flag;

void shoot(int x, int y, int way, int op){
x = x + cx[way];
y = y + cy[way];
while(x >= 0 && y >= 0 && x < n && y < m){
if(a[x][y] == 1) break;
if(a[x][y] == 2){
if(op == 1){
cntbz++;
a[x][y] = 0;
val[x][y] = 0;
}
else{
val[x][y]--;
if(val[x][y] <= 0){
cntbz++;
a[x][y] = 0;
}
}
//printf("%d %d : %d %d\n", x, y, a[x][y], op);
break;
}
x = x + cx[way];
y = y + cy[way];
}
}

void ptzx(int op){ //炮塔旋转
if(op == 0){
switch(fx){
case 0:
fx = 1;
break;
case 1:
fx = 2;
break;
case 2:
fx = 3;
break;
case 3:
fx = 0;
break;
}
}
else{
switch(fx){
case 0:
fx = 3;
break;
case 1:
fx = 0;
break;
case 2:
fx = 1;
break;
case 3:
fx = 2;
break;
}
}
}

bool forward(int &x, int &y, int step, int way){
while(step--){
x = x + cx[way];
y = y + cy[way];
if(x < 0 || y < 0 || x >= n || y >= m) return 0;
if(a[x][y] != 0){
return 0;
}
}
return 1;
}

void print(bool ok){
if(ok) printf("Complete\n");
else printf("ERROR\n");
printf("%d %d\n", nowx, nowy);
printf("%d\n", cntbz);
printf("%d %d %d %d\n", fx, robotfx, dc_b, dc_s);
}

int main(){
freopen("robo.in", "r", stdin);
freopen("robo.out", "w", stdout);
scanf("%d", &T);
while(T--){
fx = 0;
robotfx = 0;
djcnt = 0;
flag = 1;
endok = 0;
cntbz = 0;
while(!dj.empty()) dj.pop();
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
scanf("%d", &a[i][j]);
if(a[i][j] == 2) val[i][j] = 2;
}
}
scanf("%d%d%d%d%d%d", &stx, &sty, &q, &b, &c, &k);
nowx = stx;
nowy = sty;
dc_b = b;
dc_s = c;
k++;
for(int i = 1; i <= k; i++){
string ss;
getline(cin, ss);
char s[3];
s[0] = ss[0];
s[1] = ss[1];
int op;
if(ss.length() > 2){
op = ss[3] - '0';
if(ss.length() > 4 && ss[4] != ' ') op = 9;
}
if(!flag || endok) continue;
if(s[0] == 'F' && s[1] == 'T'){
if(!flag) continue;
if(op != 0 && op != 1){
flag = 0;
continue;
}
ptzx(op);
//printf("%d %d\n", robotfx, fx);
}
if(s[0] == 'F' && s[1] == 'F'){
if(!flag) continue;
if(op != 0 && op != 1){
flag = 0;
continue;
}
if(djcnt == q){
flag = 0;
continue;
}
if(op == 0){
if(dc_s > 0){
dc_s--;
djcnt++;
dj.push(0);
}
}
else{
if(dc_b > 0){
dc_b--;
djcnt++;
dj.push(1);
}
}
}
if(s[0] == 'F' && s[1] == 'E'){
if(!flag) continue;
if(djcnt == 0) continue;
shoot(nowx, nowy, fx, dj.top());
dj.pop();
djcnt--;
}
if(s[0] == 'W' && s[1] == 'T'){
if(!flag) continue;
if(op != 0 && op != 1){
flag = 0;
continue;
}
if(op == 0){
switch(robotfx){
case 0:
robotfx = 1;
break;
case 1:
robotfx = 2;
break;
case 2:
robotfx = 3;
break;
case 3:
robotfx = 0;
break;
}
}
else{
switch(robotfx){
case 0:
robotfx = 3;
break;
case 1:
robotfx = 0;
break;
case 2:
robotfx = 1;
break;
case 3:
robotfx = 2;
break;
}
}
//printf("%d %d\n", robotfx, fx);
}
if(s[0] == 'W' && s[1] == 'G'){
if(!flag) continue;
if(op < 0 || op > max(m, n)){
flag = 0;
continue;
}
int lx = nowx, ly = nowy;
int lsf = forward(nowx, nowy, op, robotfx);
//printf("%d %d\n", nowx, nowy);
if(lsf == 0){
nowx = lx, nowy = ly;
flag = 0;
continue;
}
}
if(s[0] == 'E' && s[1] == 'N'){
endok = 1;
continue;
}
}
if(endok == 0){
flag = 0;
}
print(flag);
}
return 0;
}

迷路的刺豚(expand,1.5s,64M)

  • 考场上没做出来。包括下一道题

题目描述

有一只名叫小T的刺豚,一大早它妈妈就让它出门买菜。
它看见了一只可爱的小海马,一路追着它跑啊跑啊。
结果……小T迷路了。但妈妈在家里等得很着急,它要赶紧买完菜回家。
所以!当务之急!它要知道去买菜的路……
它记得所有菜店的坐标,也知道它现在的坐标。请你帮帮她,找到一条买完菜的路吧。
它已经急得快哭了,它想要买完菜回家。因此它需要你找到一条最短的路买菜。
由于它是一条可以膨胀的刺豚,它喜欢自己大大的体格,因此它希望在路径最短的情况下使自己的体格最大,即在移动时离障碍尽可能远。
因为你开着上帝视角,所以你知道小T所在的地图。你能帮它找到一条路吗?

  • 注意:
    1. 此处的离障碍最远是保证在任何时候、在保证路径最短的情况下离障碍最远。当然小T只需要你保证在每个位置的体格之和尽可能大。
    2. 不需要考虑小T回家的路

输入格式

第一行3个数$n,m,s$,表示小T所在的地图大小和小T的最大体格。
体格为表示小T会占据$(2i+1)^2$个格子。
接下来行每行个数字表示地图,其中‘1’表示障碍,’0’表示空地。
接下来一行三个数$x,y,p$表示小T所在的坐标$(x,y)$和菜店数量$p$。
接下来$p$行,第$i$两个数表示菜店$i$所在的坐标。

输出格式

输出两个数,表示最短路长度以及每个位置的体格之和。

输入样例1

1
2
3
4
5
6
7
4 5 3
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 4 1
0 0

输出样例1

1
6 0

输入样例2

1
2
3
4
5
6
7
4 6 3
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 4 1
3 0

输出样例2

1
7 5

数据范围

对于$20%$的数据,所有菜市位置和小T所在的位置在一条水平直线上。
对于另外$30%$的数据,$s=0$ ,其中$20%$的数据还满足$n,m\leq 50$
对于另外$20%$的数据,$p=1$
对于$100%$的数据,$n,m\leq 300$,$s\leq 10$,$p\leq 15$.

题解

比较恶心,详见pdf。。。

第三题

  • 告辞。。。

评论

Your browser is out-of-date!

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

×