QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671767#5414. Stop, Yesterday Please No MoreYurily#AC ✓17ms19620kbC++203.2kb2024-10-24 14:22:272024-10-24 14:22:28

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 14:22:28]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:19620kb
  • [2024-10-24 14:22:27]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 1e3;
const int NM = 1e6;

	int n, m, k;
	
int c2t(char ch){
	if(ch == 'U')
		return 0;
	if(ch == 'D')
		return 1;
	if(ch == 'L')
		return 2;
	if(ch == 'R')
		return 3;
	return -1;
}

int rev(int t){
	return t ^ 1;
}

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

	int s[N * 2 + 3][N * 2 + 3];

int sum(int stx, int sty, int edx, int edy){
	return s[edx][edy] - s[stx - 1][edy] - s[edx][sty - 1] + s[stx - 1][sty - 1];
}
	
void sol(){
	scanf("%d%d%d\n", &n, &m, &k);
	
//	printf("%d %d %d\n", n, m, k);
	
	char ch = getchar();
	int l = 0, dir;
	int delx, dely;
	int maxu, maxd, maxl, maxr;
	delx = dely = maxu = maxd = maxl = maxr = 0;
	
	int holx, holy;
	for(int i = 1; i <= n * 2; i++)
		for(int j = 1; j <= m * 2; j++)
			s[i][j] = 0;
	s[holx = n][holy = m] = 1;
	
	while(c2t(ch) >= 0){
		dir = c2t(ch);
		
//		printf("%d", dir);
		
		delx += dx[dir];
		dely += dy[dir];
		if(delx < 0)
			maxu = max(maxu, abs(delx));
		else 
			maxd = max(maxd, abs(delx));
		if(dely < 0)
			maxl = max(maxl, abs(dely));
		else 
			maxr = max(maxr, abs(dely));
		
		dir = rev(dir);
		holx += dx[dir];
		holy += dy[dir];
		if(1 <= holx && holx <= n * 2 && 1 <= holy && holy <= m * 2)
			s[holx][holy] = 1;
		
		ch = getchar();
	}
	
//	printf("\n");

	int stx = n + maxu, sty = m + maxl;
	int edx = n + n - 1 - maxd, edy = m + m - 1 - maxr;
	
//	printf("ud[%2d,%2d]  lr[%2d,%2d]\n", maxu, maxd, maxl, maxr);
//	printf("st[%2d,%2d]  ed[%2d,%2d]\n", stx, sty, edx, edy);
//	printf("%3c", ' ');
//	for(int i = 1; i <= m * 2; i++)
//		printf("%3d", i);
//	printf("\n");
//	for(int i = 1; i <= n * 2; i++){
//		printf("%3d", i);
//		for(int j = 1; j <= m * 2; j++)
//			printf("%3d", s[i][j]);
//		printf("\n");
//	}
//	printf("\n");
	
	if(maxu + maxd >= n || maxl + maxr >= m){
		if(k == 0)
			printf("%d\n", n * m);
		else 
			printf("0\n");
		return ;
	}
	
	for(int i = 1; i <= n * 2; i++)
		for(int j = 1; j <= m * 2; j++)
			s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			
//	printf("%3c", ' ');
//	for(int i = 1; i <= m * 2; i++)
//		printf("%3d", i);
//	printf("\n");
//	for(int i = 1; i <= n * 2; i++){
//		printf("%3d", i);
//		for(int j = 1; j <= m * 2; j++)
//			printf("%3d", s[i][j]);
//		printf("\n");
//	}
//	printf("\n");
	
	int size = (edx - stx + 1) * (edy - sty + 1);
	int ans = 0;
	for(int p = 0; p <= n - 1; p++)
		for(int q = 0; q <= m - 1; q++)
			if(size - sum(stx - p, sty - q, edx - p, edy - q) == k){
//				printf("st(%2d,%2d)ed(%2d,%2d)\n", stx - p, sty - q, edx - p, edy - q);
//				printf("s[%2d][%2d]=%2d\n", edx - p, edy - q, s[edx - p][edy - q]);
//				printf("s[%2d][%2d]=%2d\n", stx - p - 1, edy - q, s[stx - p - 1][edy - q]);
//				printf("s[%2d][%2d]=%2d\n", edx - p, sty - q - 1, s[edx - p][sty - q - 1]);
//				printf("s[%2d][%2d]=%2d\n", stx - p - 1, sty - q - 1, s[stx - p - 1][sty - q - 1]);
				ans++;
			}
	
	printf("%d\n", ans);
	
}

int main(){
	memset(s, 0 , sizeof s);

	int T;
	scanf("%d", &T);
	while(T--)
		sol();

	return 0;

}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 19484kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: 0
Accepted
time: 6ms
memory: 19620kb

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
20
99
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

ok 1060 numbers

Test #3:

score: 0
Accepted
time: 9ms
memory: 19548kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 4ms
memory: 19420kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

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

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 8ms
memory: 19536kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 6ms
memory: 19460kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 16ms
memory: 19616kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 8ms
memory: 19540kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 4ms
memory: 19532kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 17ms
memory: 19588kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"