C. Triangles(枚举)
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(); }
}
