UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212681#3828. BJacken1002693ms21540kbC++111.8kb2024-10-20 09:29:562024-10-20 14:36:04

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n;
int a[N];
int f[N];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int m;
int dfs(int x,int y)
{
    if(f[(x-1)*m+y])
    {
        return f[(x-1)*m+y];
    }
    int ans = 0;
    for(int i = 0;i<4;i++)
    {
        int r = dx[i]+x,c = dy[i]+y;
        if(r<=n&&c<=m&&r>=1&&c>=1&&a[(x-1)*m+y]<a[(r-1)*m+c])
        {
            ans = max(dfs(r,c)+1,ans);
        }
    }
    return f[(x-1)*m+y] = ans;
}
int main()
{
	int _;
	scanf("%d",&_);
	while(_--)
	{
		scanf("%d %d",&n,&m);
	    for(int i = 1;i<=n;i++)
	    {
	        for(int j = 1;j<=m;j++)
	        {
	        	scanf("%d",&a[(i-1)*m+j]);
	        }
	    }
	    int maxx = 0;
	    int maxxx = 0;
	    memset(f,0,sizeof(f));
	    for(int i = 1;i<=n;i++)
	    {
	        for(int j = 1;j<=m;j++)
	        {
	        	int t = dfs(i,j);
	        	if(maxx<t||maxx == t&&a[(i-1)*m+j]<a[maxxx])
	        	{
	        		maxx = t;
	        		maxxx = (i-1)*m+j;
				}
	        }
	    }
	    printf("%d\n",maxx+1);
	    set<int>cd;
	    cd.insert(a[maxxx]);
	    int x = maxxx%m == 0?maxxx/m:maxxx/m+1,y = maxxx%m == 0?m:maxxx%m;\
	    while(f[(x-1)*m+y])
	    {
	    	int minn = 1e9;
	    	int minnr = 0;
	    	int minnc = 0;
	    	for(int i = 0;i<4;i++)
	    	{
	    		int r = x+dx[i],c = y+dy[i];
	    		if(r<1||r>n||c<1||c>m)
	    		{
	    			continue;
				}
				if(f[(r-1)*m+c] == f[(x-1)*m+y]-1&&a[(x-1)*m+y]<a[(r-1)*m+c])
				{
					if(minn>a[(r-1)*m+c])
					{
						minn = a[(r-1)*m+c];
						minnr = r;
						minnc = c;
					}
				}
			}
			x = minnr;
			y = minnc;
			cd.insert(minn);
		}
		for(auto it = cd.begin();it!=cd.end();it++)
		{
			printf("%d ",*it);
		}
		printf("\n");
	}
    return 0;
}

详细

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

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 2020kb

input:

10
3 3
0 1 2
3 4 5
6 7 8
3 3
0 1 2
3 4 5
6 8 7
3 3
0 1 2
3 4 5
7 6 8
3 3
0 1 2
3 4 5
7 8 6
3 3
0 1 2...

output:

5
0 1 2 5 8 
6
0 1 2 5 7 8 
5
0 1 2 5 8 
6
0 1 2 5 6 8 
5
0 1 2 5 7 
7
0 1 2 5 6 7 8 
5
0 1 2 6 8 
6...

result:

ok 64 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 2016kb

input:

10
1 10
1 5 0 8 2 9 6 3 4 7
1 10
2 5 8 0 9 7 3 1 6 4
3 3
0 1 2
5 4 3
6 7 8
1 10
3 4 7 2 5 6 9 0 1 8
...

output:

3
3 4 7 
4
1 3 7 9 
9
0 1 2 3 4 5 6 7 8 
4
2 5 6 9 
3
1 7 9 
4
4 5 6 7 
3
0 4 7 
10
0 1 2 3 4 5 6 7 ...

result:

ok 63 numbers

Subtask #2:

score: 20
Accepted

Test #3:

score: 20
Accepted
time: 3ms
memory: 2112kb

input:

10
22 45
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...

output:

990
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 3...

result:

ok 5011 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 2108kb

input:

10
17 58
655 668 708 805 640 926 52 16 9 662 765 129 949 348 678 235 18 464 819 450 211 968 724 754 ...

output:

10
11 42 106 223 265 421 903 923 971 982 
10
227 258 271 479 499 509 574 578 580 918 
8
1 230 308 44...

result:

ok 2052 numbers

Subtask #3:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 447ms
memory: 21540kb

input:

10
2 100000
143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...

output:

13
11306 16007 49522 70570 76999 90088 97453 105217 116458 118241 145649 165150 168193 
9
9688 35806...

result:

ok 600082 numbers

Subtask #4:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 377ms
memory: 21536kb

input:

10
1 200000
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...

output:

200000
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 3...

result:

ok 400095 numbers

Subtask #5:

score: 40
Accepted

Test #7:

score: 40
Accepted
time: 519ms
memory: 21536kb

input:

10
145 1379
140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...

output:

14
8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 
14
701...

result:

ok 799431 numbers

Test #8:

score: 0
Accepted
time: 448ms
memory: 21528kb

input:

10
137 1459
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...

output:

199883
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 3...

result:

ok 599839 numbers

Test #9:

score: 0
Accepted
time: 437ms
memory: 21540kb

input:

10
431 464
73283 114291 153291 121544 122062 142417 169824 87437 63383 123169 5578 161240 12296 2810...

output:

13
8693 46170 58031 84535 85037 98585 107097 109913 125647 135974 173048 173291 193164 
16
5468 1850...

result:

ok 400038 numbers

Test #10:

score: 0
Accepted
time: 462ms
memory: 21536kb

input:

10
287 696
42594 17204 186134 183377 153412 122746 42424 4738 107615 187084 183594 161385 57847 9481...

output:

14
136 58739 82533 100919 115173 123428 128558 129415 134074 151802 155712 174974 184151 184213 
14
...

result:

ok 599743 numbers

Extra Test:

score: 0
Extra Test Passed