Codeforces Round #688 (Div. 2) C. Triangles(思维,数学)

题目传送
题意:
给你一个n*n的矩阵,上面写着0到9的数字,现在问你:选取同一种数字中的任意三个,组成的三角形的最大面积 * 2是多少,每选取一种数字的时候,你最多可以改动一次,使得某个位置变成你想要的数字,在这个数字选取完后,改动的数字变回原样。

思路:
1.既然每次可以改一次,那么肯定只要存在俩个点那么三角形面积就不会为0.那么我直接枚举俩个点就是了,另外一个点配合选取的俩个点使得面积最大即可,但是暴力选取俩个点会T

2.我们知道三角形面积是 底乘高除二 ,那么既然另外一个点是我们可以控制的,可以配合俩个点达到面积最大值。那么这个俩个点我们要选取的话,什么情况下,他们可能存在最大值。

3.那么我们只需要控制这个三角形的高,然后底我们可以枚举每一个点,再控制另外一个点取最大的底。那么这个高怎么选呢?因为这个三角形的一边必须平行矩形的一边,所以我们先假设这个高平行x轴,那么我们肯定是选x最大和最小的俩个点去枚举,因为在枚举的时候,高 能达到最大值。同理假设这个高平行y轴,那么我们肯定是选y最大和最小的俩个点去枚举, 这样枚举一遍,取最大值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 4e6 + 100;
char str[2005][2005];
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //    freopen("input.txt","r",stdin);
    //    freopen("output.txt","w",stdout);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                cin >> str[i][j];
        for(int num = 0;num < 10;num++)
        {
            int x = 0,y = 0,Max = 0,m = 0,xx = 0,yy = 0,xxx = INF,yyy = INF,xxxx = INF,yyyy = INF;
            for(int i = 1;i <= n;i++)
            {
                for(int j = 1;j <= n;j++)
                {
                    if(str[i][j] - '0' == num)
                    {
                        if(x < i)//x最大的点
                            x = i,y = j;
                            
                        if(yy < j)//y最大的点
                            xx = i,yy = j;
                            
                        if(xxx > i)//x最小的点
                            xxx = i,yyy = j;
                            
                        if(yyyy > j)//y最小的点
                            yyyy = j,xxxx = i;
                            
                        m++;
                    }
                }
            }
            if(m < 2) {cout << 0 << " ";continue;}//如果都没有俩个点,面积为0
            for(int i = 1;i <= n;i++)//枚举每一个点
            {
                for(int j = 1;j <= n;j++)
                {
                    if(str[i][j] - '0' == num)
                    {
                        Max = max(Max,max(n-j,j-1)*(x-i));//另外一点任意取,所以在高固定的情况下,取最大的底
                        Max = max(Max,max(n-y,y-1)*(x-i));

                        Max = max(Max,max(n-i,i-1)*(yy-j));//上底
                        Max = max(Max,max(n-xx,xx-1)*(yy-j));//下底

                        Max = max(Max,max(n-j,j-1)*(i-xxx));
                        Max = max(Max,max(n-yyy,yyy-1)*(i-xxx));

                        Max = max(Max,max(n-i,i-1)*(j-yyyy));
                        Max = max(Max,max(n-xxxx,xxxx-1)*(j-yyyy));
                    }
                }
            }
            cout << Max << " ";
        }
        cout << endl;
    }
}
上一篇:洋流的仿真matlab源码


下一篇:bfs一入不回头