CodeForces 1453C. Triangles

题目大意

给你一个矩阵，每个格子是0-9之间的任何一个元素，现在对于0-9这10个不同的数，要在矩阵内构造出最大的三角形
每个三角形的定义如下，设当前要构造的是第$d$个数的最大三角形：
该三角形的三个顶点都要是数d
必须有一条边平行于矩阵
在每次构造三角形的时候可以把矩阵内任意一个点的大小改为d,构造完后改回（每次构造之间修改不影响）
为了简便计算，求三角形面积时不需要/2,直接 底*高 即可

思路1

其实只需要确定两个点的位置，剩下一个点因为可以任意取一个点，所以关键是怎么选择其中两个点，对于第d个数，如果点的数量<=1,那么修改一个也不够凑成三角形，直接输出0

否则记录每个点的x,y坐标，
首先考虑垂直边平行于坐标轴的情况（两个点x值相等），遍历所有点，
对于相同元素d的点按行坐标进行递增排序
则以垂直边为底的高的最大值就是：

$最后一个点减去当前点的横坐标$和$当前点的横坐标减去第一个点的横坐标$
的最大值(不太严谨的可以将当前点看做中点，取左边或者右边），

那么这条平行边的最大值就是 当前点离x轴的距离y或者n-y+1(第三个点的y值）
这样我们就求出了当选择这个点且垂直边平行于坐标轴时的情况，取所有点得出的最大值

然后交换所有点的行和列坐标翻转再来一遍，相当于是求水平边平行于坐标轴的情况

// Author: zengyz
// 2025-06-12 15:55#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using i64 = long long;void solve()
{int n;cin >> n;vector<vector<int>> a(n, vector<int>(n, 0));vector<pair<int, int>> vp[10];for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){char op;cin >> op;a[i][j] =op-'0';vp[a[i][j]].push_back({i, j});}}for (int i = 0; i <= 9; i++){if (vp[i].size() <= 1){cout << "0 " ;}else{int ans=0;for(int k=0;k<2;k++){sort(vp[i].begin(), vp[i].end());for(auto x:vp[i]){int disx=max(vp[i].back().first-x.first,x.first-vp[i][0].first);int disy=max(x.second,n-1-x.second);ans=max(ans,disx*disy);}for(auto &x:vp[i])swap(x.first,x.second);}cout<<ans<<" ";}}cout<<endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

思路2

先考虑水平边平行于x轴的情况
考虑一个点(x,y)，设第三个点会与这个点平行，因为可以任取，所以既可以在最左边长度为(1,y),也可以在最右边(n,y)
那么取max(x,n-x+1)那么剩下一个点就取离这条平行边最远的一个点，设构造第d个三角形时垂直方向出现过的最大值ya和最小值yi,则有高为max(ya-j,j-yi)
那么答案就是$$max(x,n-x+1)\ast max(ya-j,j-yi)$$

竖直方向同理

// Author: zengyz
// 2025-06-12 15:55#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using i64 = long long;void solve()
{int n;cin >> n;vector<vector<int>> a(n, vector<int>(n, 0));vector<int> xi(10, 1e9), xa(10), yi(10, 1e9), ya(10), ans(10);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){char op;cin >> op;int now = op - '0';a[i][j] = now;xi[now] = min(xi[now], i);xa[now] = max(xa[now], i);yi[now] = min(yi[now], j);ya[now] = max(ya[now], j);}}for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){int now = a[i][j];ans[now] = max(ans[now], max(i, n - 1 - i) * max(ya[now] - j, j - yi[now]));ans[now] = max(ans[now], max(j, n - 1 - j) * max(xa[now] - i, i - xi[now]));}}for (int i = 0; i <= 9; i++)cout << ans[i] << " ";cout << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}