Problem - C - Codeforces
Gildong有一个方形板，由n行n列的方形单元格组成，每个单元格由一个数字(从0到9)组成，第i行第j列的单元格可用(，)表示，每个单元格的边长为1。Gildong喜欢大的东西，所以对于每一个数字d，他想找到一个三角形，这样:三角形的每个顶点都位于单元格的中心。三角形的每个顶点的数字都是d。三角形的至少一条边平行于板子的一条边。你可以假设一条长度为O的边平行于黑板的两边。三角形的面积最大。当然，他不能仅仅满足于找到这些三角形。因此，对于每一个数字d，他要把板子上一个格子的数字换成d，然后找到这样一个三角形。在处理完每个数字后，他把它变回原来的数字。求出他能为每一个数字做出的三角形的最大面积。注意，他可以把三角形的多个顶点放在同一个单元格上，这个三角形可以是简并三角形;即三角形的面积可以是0。另外，请注意，他可以将单元格的数字从d改为d。输入每个测试包含一个或多个测试用例。第一行包含测试用例的数量t (1 S t < 1000)。每个测试用例的第一行包含一个整数n (1 <n < 2000)——棋盘的行数和列数。每个测试用例的下n行都包含一个不带空格的n位数字字符串。第i行第j位是单元格在(i, j)处的数字。每个数字是0到9之间的一个字符。保证所有测试用例的n2和不超过4- 106。输出对于每个测试用例，打印一行10个整数。第i个整数是di-1乘以2后Gildong三角形的最大面积。
Example
input
Copy
5 3 000 122 001 2 57 75 4 0123 4012 3401 2340 1 9 8 42987101 98289412 38949562 87599023 92834718 83917348 19823743 38947912
output
Copy
4 4 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 9 6 9 9 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 49 49 49 49 15 0 30 42 42
题解:
对于每个数字,我们可以找到他的最大最小x,y坐标
把同一个数字的x,y坐标储存到一起
求最大三角形
首先第一个点是我们记录的x,y坐标,要想三角形最大,其中我们可以改变的点应该在四条底边上
这样我们就得到了两个点,已经得到一条边后,看这个点与之前我们记录数字最大最小的x,y坐标,得到高,求最大值即可(说的不是太清楚,代码很清楚)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
//#define int long long
int c[10];
int limit[11][5];
int x[10][4000050];
int y[10][4000040];
void solve()
{
int n;
cin >> n;
for(int i = 0;i <= 9;i++)
{
limit[i][1] = 1e9;
limit[i][2] = -99999;
limit[i][3] = 1e9;
limit[i][4] = -99999;
c[i] = 0;
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
char kk;
cin >> kk;
int k = kk - '0';
if(limit[k][1] > i)
{
limit[k][1] = i;
}
if(limit[k][2] < i)
{
limit[k][2] = i;
}
if(limit[k][3] > j)
{
limit[k][3] = j;
}
if(limit[k][4] < j)
{
limit[k][4] = j;
}
x[k][++c[k]] = i;
y[k][c[k]] = j;
}
}
for(int i = 0;i <= 9;i++)
{
if(c[i] <= 1)
{
cout << 0 <<" ";
continue;
}
int ans = 0;
for(int j = 1;j <= c[i];j++)
{
int tx = max(abs(n - x[i][j]),abs(x[i][j] - 1));
int ty = max(abs(n - y[i][j]),abs(y[i][j] - 1));
ans = max(ans,max(tx*abs(y[i][j] - limit[i][4]),tx*abs(y[i][j] - limit[i][3])));
ans = max(ans,max(ty*abs(x[i][j] - limit[i][1]),ty*abs(x[i][j] - limit[i][2])));
}
cout << ans <<" ";
}
cout << '\n';
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
