UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213408#2068. 最长公共前缀liuqichen12110028564ms5104kbC++1.1kb2024-11-11 21:39:422024-11-11 23:07:51

answer

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
int read(){
    int s=0,f=1;
    char _z=getchar();
    while(_z<'0'||_z>'9'){
        if(_z=='-')
        f=-1;
        _z=getchar();
    }
    while(_z>='0'&&_z<='9'){
        s=(s<<3)+(s<<1)+(_z-'0');
        _z=getchar();
    }
    return s*f;
}
const int N=2e3+10,Fx[3]={0,1,1},Fy[3]={1,0,1};
char c[N][N];
int main(){
    int n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)
    scanf("%s",c[i]+1);
    while(q--){
        char af[2],bf[2];
        int ax=read(),ay=read();
        scanf("%s",af);
        int bx=read(),by=read();
        scanf("%s",bf);
        int aF=(af[0]=='H'?0:(af[0]=='V'?1:2));
        int bF=(bf[0]=='H'?0:(bf[0]=='V'?1:2));
        int res=0;
        while(ax<=n&&ay<=m&&bx<=n&&by<=m&&c[ax][ay]==c[bx][by]){
            res++;
            ax+=Fx[aF],ay+=Fy[aF];
            bx+=Fx[bF],by+=Fy[bF];
        }
        printf("%d\n",res);
    }
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 18ms
memory: 3140kb

input:

1000 2000 10000
awanannwnnaaawwnwawanwnwaaaanwnaaananwawwwwnannannawwwawwaaaaannwnwnwnnaaawaawawannn...

output:

0
0
0
0
0
0
0
2
0
1
0
0
1
0
1
0
2
0
1
2
0
0
2
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
2
0
1
3
1
0
3
0
...

result:

ok 10000 tokens

Test #2:

score: 0
Accepted
time: 12ms
memory: 5100kb

input:

2000 1000 10000
zzqzqqqqqzqqqqzqqqqzqzqzzzqqzqqqzzqzzqqqqqqqqqqqzzqzqqqzzqqzzqzqzzzqqzqqzzzzzzqzzzqq...

output:

0
3
3
1
0
2
2
2
1
0
1
0
0
0
1
0
2
0
6
1
0
1
1
0
2
1
1
1
2
4
0
1
3
2
1
0
1
2
0
0
0
1
1
0
1
1
0
4
0
3
...

result:

ok 10000 tokens

Subtask #2:

score: 24
Accepted

Test #3:

score: 24
Accepted
time: 2412ms
memory: 5100kb

input:

2000 2000 1000000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

1146
541
203
322
618
166
345
138
520
206
1031
667
741
921
361
1110
1057
372
899
209
491
69
93
639
14...

result:

ok 1000000 tokens

Test #4:

score: 0
Accepted
time: 457ms
memory: 5104kb

input:

2000 2000 1000000
svsvsvvsvssssvsvvvvssvvvssvsvsvssssvvsvvvsvvsssvssssvssvvsvvvssssssvsvvvvsssvvvsss...

output:

2
0
2
1
2
0
0
1
3
1
0
0
0
1
0
1
0
1
0
6
1
2
2
1
3
5
0
0
1
1
0
0
2
1
1
3
1
0
0
2
1
0
0
0
0
0
1
0
5
0
...

result:

ok 1000000 tokens

Test #5:

score: 0
Accepted
time: 1097ms
memory: 5104kb

input:

2000 2000 1000000
qqqqqqqqqqqqqqqqcqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

327
50
54
421
87
4
189
135
200
214
55
578
82
72
335
52
45
110
521
267
123
21
293
105
105
479
85
69
1...

result:

ok 1000000 tokens

Test #6:

score: 0
Accepted
time: 940ms
memory: 5100kb

input:

2000 2000 1000000
ssssssssssssssssssssssssssgsssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

187
336
26
367
487
65
159
30
12
275
628
200
252
742
362
7
316
232
26
82
607
158
56
444
155
262
1
106...

result:

ok 1000000 tokens

Test #7:

score: 0
Accepted
time: 1172ms
memory: 5104kb

input:

2000 2000 1000000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

output:

1281
105
890
1087
24
179
172
588
260
206
238
255
150
346
484
224
369
293
15
275
299
125
19
406
1146
...

result:

ok 1000000 tokens

Test #8:

score: 0
Accepted
time: 429ms
memory: 5104kb

input:

2000 2000 1000000
cschgfyhvrlhmuchmcssqmxypkfkmkrfwpivfljvlascqlphvlbmjnztypqeoyevqecixdhricknhdrero...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #9:

score: 0
Accepted
time: 554ms
memory: 5104kb

input:

2000 2000 1000000
cwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcw...

output:

0
0
0
0
118
0
0
0
0
0
0
0
0
0
0
0
0
0
178
0
0
0
297
0
0
0
0
0
0
63
0
0
0
115
0
0
0
699
955
0
325
0
0...

result:

ok 1000000 tokens

Subtask #3:

score: 22
Accepted

Test #10:

score: 22
Accepted
time: 3557ms
memory: 5104kb

input:

2000 2000 1000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1182
916
1440
420
469
1353
818
143
458
743
25
1414
878
23
284
453
324
1652
10
556
276
448
1143
916
1...

result:

ok 1000000 tokens

Test #11:

score: 0
Accepted
time: 662ms
memory: 5104kb

input:

2000 2000 1000000
ddddoddoodoodooddodododdodododdoooddodddddoodoodddddoodddodooddoddooooodddooodddoo...

output:

4
1
1
1
2
0
0
0
4
2
1
1
3
0
0
0
1
4
1
1
0
0
0
2
1
2
1
0
2
0
2
0
2
0
4
4
1
1
0
0
2
0
5
2
0
1
2
1
0
0
...

result:

ok 1000000 tokens

Test #12:

score: 0
Accepted
time: 1757ms
memory: 5104kb

input:

2000 2000 1000000
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

180
74
19
380
126
169
75
17
53
352
123
150
258
103
65
17
87
109
11
164
407
143
241
407
214
256
84
22...

result:

ok 1000000 tokens

Test #13:

score: 0
Accepted
time: 1465ms
memory: 5100kb

input:

2000 2000 1000000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

36
41
642
9
356
1100
529
595
2
299
253
559
761
245
494
259
43
234
430
885
449
225
404
211
213
32
38
...

result:

ok 1000000 tokens

Test #14:

score: 0
Accepted
time: 2099ms
memory: 5104kb

input:

2000 2000 1000000
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

905
292
231
537
281
229
247
240
1460
110
261
530
378
569
206
163
1185
128
983
117
296
79
123
3
53
81...

result:

ok 1000000 tokens

Test #15:

score: 0
Accepted
time: 483ms
memory: 5100kb

input:

2000 2000 1000000
nvmqmtwqkbpisvkrhgehqvohvizhldbhyiamavjuipxwxeqcqiqwcrjjlxeuvgzpgfwtcdgpymkptfemtv...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #16:

score: 0
Accepted
time: 827ms
memory: 5100kb

input:

2000 2000 1000000
tctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctc...

output:

0
0
0
0
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
344
0
0
0
0
0
0
0
0
0
0
0
1
0
0
546
0
0
0
1
1
...

result:

ok 1000000 tokens

Subtask #4:

score: 43
Accepted

Test #17:

score: 43
Accepted
time: 425ms
memory: 3140kb

input:

1000 2000 1000000
yzyzzyaazyyzzaaayzzayyyaaayyazayyzzyazzyazayzayzyzzayyzyzzayzazzyzzayzaazazaaayzyy...

output:

2
0
2
1
1
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
2
0
1
0
0
0
0
2
1
2
0
1
0
0
0
2
0
0
...

result:

ok 1000000 tokens

Test #18:

score: 0
Accepted
time: 3353ms
memory: 5104kb

input:

2000 2000 1000000
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

255
79
826
62
931
351
68
1020
265
697
2
1101
779
606
176
1568
696
615
106
596
185
311
65
397
816
25
...

result:

ok 1000000 tokens

Test #19:

score: 0
Accepted
time: 581ms
memory: 5100kb

input:

2000 2000 1000000
yyyvvyyyvyyyyvvvyyvyyyyvyyyyyyvvyvvyyyyyvvyyvvyvyvyvvvyyyvyvyvyyvyyyyvyyyvyyyvvyvy...

output:

3
0
0
0
0
1
0
0
0
0
1
2
0
2
1
0
0
0
4
2
0
0
3
1
1
2
3
1
0
1
1
0
0
3
0
0
0
2
0
0
1
0
1
0
0
3
2
0
0
1
...

result:

ok 1000000 tokens

Test #20:

score: 0
Accepted
time: 2344ms
memory: 5104kb

input:

2000 2000 1000000
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

128
57
641
99
820
2
155
264
232
511
552
36
506
522
31
528
574
506
638
59
127
22
103
53
30
56
14
18
1...

result:

ok 1000000 tokens

Test #21:

score: 0
Accepted
time: 1175ms
memory: 5100kb

input:

2000 2000 1000000
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1
33
165
12
417
104
452
86
315
401
295
141
60
41
76
115
118
150
489
69
46
196
373
109
142
34
115
481...

result:

ok 1000000 tokens

Test #22:

score: 0
Accepted
time: 1870ms
memory: 5100kb

input:

2000 2000 1000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

371
247
218
9
492
569
21
454
121
168
207
251
176
236
333
23
138
1501
385
306
342
101
286
204
168
99
...

result:

ok 1000000 tokens

Test #23:

score: 0
Accepted
time: 420ms
memory: 5100kb

input:

2000 2000 1000000
ccbxyakkmwxjxctespteblasatcayufpdpqvjjbmatywntdpcnhmwabgpmsyuxvqjtgxutglopldstpcmq...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #24:

score: 0
Accepted
time: 455ms
memory: 5100kb

input:

2000 2000 1000000
mfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmf...

output:

0
0
0
0
2
0
0
1
0
1
0
0
0
0
0
0
2
1
0
361
0
0
0
1
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
0
323
0
0
0
1
0
0
1
...

result:

ok 1000000 tokens