1453c triangles (greed, simulation)

2020-12-07 09:12:49

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[Max];
int ma;//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;//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] = -999999;
ma[i] = 1e9;
ma[i] = -99999;
ma[i] = 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])ma[k] = i;
if (i < ma[k])ma[k] = i;
if (j > ma[k])ma[k] = j;
if (j < ma[k])ma[k] = 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] - po[i][j].y), abs(ma[i] - po[i][j].y)));
ans = max(ans, yt * max(abs(ma[i] - po[i][j].x), abs(ma[i] - po[i][j].x)));
}
cout << ans << " ";
}
cout << endl;
}
}

https://chowdera.com/2020/12/20201207091151251z.html