1453C Triangles（贪心、模拟）

Myth丶恋晨 2021-07-16 23:56 318阅读 0赞

[传送门][Link 1]

题意：对于n行m列给定的数组，数组每个元素的值为0-9，我们需要构造出一个三角形,三角形顶点的坐标即为元素所在的行数和列数，三角形三个顶点的元素值应该相同，对于0-9我们需要分别求出每个数字构造出的三角形的面积最大值\*2。额外条件：对于构造出的三角形我们要求其一定要有一条边平行于行或列，对于每一个点我们还可以任意指定一个元素使其值变为和自己的值相等以方便构造三角形。

思路：首先对于一个给定点我们怎样使得其构造的三角形面积最大呢？我们已经确定了一个点P，然后我们还可以任选一个点使其值和这个点相等，使其成为构造这个三角形的第二个点，那么我们有两种方案1.选择P所在行的最右方的点或最左方的点（谁与P的行数相差大就选谁，保证了一条边平行）2.选择P所在列最上方或最下方的点。选出这两种方案中行数差值最大的或列数差值最大的即为最优的（没理解可以模拟一下选取过程）。那么我们确定了第二个点，对于第三个点其实对于我们所要求的面积我们已经确定了底边的长度现在我们只需找到和P高度差最大那个点即可，如果我们前面选取的是行数相差最大，那么现在找到列数相差最大的点即可（而其必然是在列数最大的点和列数最小的点中得到，先遍历一篇预先求出来就好了）。然后遍历所有点求出面积最大值，细节见代码。

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]对应分别为值为k的元素中最大的行数、最小的行数、最大的列数、最小的列数
    int g[11];//0-9个元素各自的数目
    
    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;
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1453/C