Uchiha_Itachi 的博客

Uchiha_Itachi 的博客

题解 CF1203B 【Equal Rectangles】

posted on 2019-08-17 15:08:15 | under 题解 |

咕了两天后过来写写。。。。。。

其实是小奥题......我自己都不知道为啥卡了十几分钟(还不是因为我蔡

先来一手排序,然后就可以从头到尾判一遍,如果有当对于每个奇数i,若 $a_i \neq a_{i +1}$ ,则无法构成足够数量的矩形,可以直接输no处理其他情况。其实貌似不加这段特判也过得去,就是当时敲的时候怕出现一堆无法构成矩形的情况然后T掉 然后算了一下发现这么搞常数反而会增大

然后就是由矩形计算公式 $S=ab$ 推出两个木棒拼成矩形时,若其面积全部相等,则必为最大的与最小的拼,次大的与次小的拼,以此类推。

然后就过掉了。数据与 $a_i$ 无关, $n$ 还很小,面积也不会爆int,总之就很水(

这里吐槽一句这是什么神奇的数据范围啊

代码(极长警告):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;
    while(N--)
    {
        int n;
        cin >> n;
        int arr[401];
        int k = 4 * n;
        for(int i = 1;i <= k;i++)
        {
            cin >> arr[i];
        }
        sort(arr + 1,arr + k + 1);
        bool flaga = true;
        for(int i = 1;i <= k;i += 2)
        {
            if(arr[i] != arr[i + 1])
            {
                flaga = false;
                break;
            }
        }
        if(!flaga)
        {
            cout << "NO" << endl;
            continue;
        }
        int area = arr[1] * arr[k];
        bool flag = true;
        for(int i = 3,j = k - 2;i <= 2 * n;i += 2,j -= 2)
        {
            if(arr[i] * arr[j] != area)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}