当前位置:网站首页>1453c triangles (greed, simulation)

1453c triangles (greed, simulation)

2020-12-07 09:12:49 osc_ vuza8uho

Portal

The question : about n That's ok m Column the given array , The value of each element of the array is 0-9, We need to construct a triangle , The coordinates of the vertex of a triangle are the number of rows and columns of the element , The element values of the three vertices of a triangle should be the same , about 0-9 We need to find the maximum area of the triangle constructed by each number *2. Additional conditions : For the constructed triangle, we must have an edge parallel to the row or column , For each point, we can also arbitrarily specify an element to make its value equal to its own value to facilitate the construction of triangles .

Ideas : First of all, for a given point, how can we maximize the area of the triangle it constructs ? We have identified a point P, Then we can choose any point to make its value equal to this point , Make it the second point to construct the triangle , So we have two options 1. choice P The rightmost or leftmost point of the line ( Who and P If the number of rows is different, choose who , Ensures that one side is parallel )2. choice P At the bottom or top of the column . The difference between the two columns is the largest ( I don't understand. I can simulate the selection process ). So we identified the second point , For the third point, we have determined the length of the bottom edge for the area we require. Now we just need to find and P The point where the height difference is the biggest can be , If we select the row number in front of us, the difference is the largest , So now find the point with the largest difference in the number of columns ( And it must be obtained from the point with the largest number of columns and the point with the smallest number of columns , It's good to traverse an article and find it in advance ). Then traverse all the points to find the maximum area , See code for details .

Code

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 4e6 + 25;
ll lst[Max];
int Mod = 1e9 + 7;
struct P
{
   
   
	P(int a=0, int b=0) :x(a), y(b) {
   
    ; }
	int x, y;
};

P po[11][Max];
int ma[11][5];//ma[k][1-4] The corresponding values are respectively k The maximum number of rows in the element of 、 The minimum number of rows 、 The maximum number of columns 、 Minimum number of columns 
int g[11];//0-9 The number of each element 

int main()
{
   
   
	FAST;
	int t;cin >> t;
	while (t--)
	{
   
   
		int n;cin >> n;
		memset(g, 0, sizeof(g));
		for (int i = 0;i <= 9;i++)
		{
   
   
			ma[i][1] = -999999;
			ma[i][2] = 1e9;
			ma[i][3] = -99999;
			ma[i][4] = 1e9;
		}
		for(int i=1;i<=n;i++)
			for (int j = 1;j <= n;j++)
			{
   
   
				char kk;cin >> kk;
				int k = kk - '0';
				if (i > ma[k][1])ma[k][1] = i;
				if (i < ma[k][2])ma[k][2] = i;
				if (j > ma[k][3])ma[k][3] = j;
				if (j < ma[k][4])ma[k][4] = j;
				po[k][++g[k]].x = j;po[k][g[k]].y = i;
			}

		for (int i = 0;i <= 9;i++)
		{
   
   
			int ans = 0;
			if (g[i] <= 1) {
   
   
				cout << 0 << " ";continue;
			}
			for (int j = 1;j <= g[i];j++)
			{
   
   
				int xt = max(abs(n - po[i][j].x), po[i][j].x - 1);
				int yt = max(abs(n - po[i][j].y), po[i][j].y - 1);
				ans = max(ans, xt * max(abs(ma[i][2] - po[i][j].y), abs(ma[i][1] - po[i][j].y)));
				ans = max(ans, yt * max(abs(ma[i][3] - po[i][j].x), abs(ma[i][4] - po[i][j].x)));
			}
			cout << ans << " ";
		}
		cout << endl;
	}
}

版权声明
本文为[osc_ vuza8uho]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207091151251z.html