D. Sonya and Matrix

题目链接

Codeforces Round #495 (Div. 2)--D. Sonya and Matrix

题解

中档题。题意大概是给定一个序列,求出一个矩阵满足序列中的数字可以填入矩阵中,并且矩阵中每个点的数字为到某一点的哈夫曼距离。
首先统计出每个数字的出现次数与最大数字的大小,由此找出0距离边界的距离(以0为中心的正方形的最大边长)。对于每个x,y可以在O(1)的操作内求出0点的某一位置(0距离边界的距离,最大数字+0距离边界的距离-另一边边长+1),所以枚举每个x,y满足x*y=t,并判断其得到的矩阵是否符合输入的结果。

代码

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int n, temp, maxnum;
int a[1000005], b[1000005];
bool pd(int x, int y, int xx, int yy) {
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            b[abs(i - xx) + abs(j - yy)]++;
        }
    }
    for (int i = 0; i <= maxnum; i++) {
        if (a[i] != b[i])return false;
    }
    cout << x << ' ' << y << endl << xx << ' ' << yy;
    return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        a[temp]++;
        maxnum = max(maxnum, temp);
    }
    if (!a[0]) {
        cout << -1;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] != i * 4) {
            temp = i;
            break;
        }
    }
    if (a[maxnum] == 2) {
        if (pd(2 * temp - 1, n / (2 * temp - 1), temp, maxnum - temp + 2))
            return 0;
        cout << -1;
        return 0;
    }
    else if (a[maxnum] == 4) {
        if (pd(2 * temp - 1, 2 * temp - 1, temp, temp))
            return 0;
        cout << -1;
        return 0;
    }
    else if (a[maxnum] == 1) {
        for (int i = temp * 2 - 1; i <= sqrt(n); i++) {
            if (n%i == 0) {
                if (pd(i, n / i, temp, maxnum + temp - i + 1))
                    return 0;
            }
        }
        for (int i = temp * 2 - 1; i <= sqrt(n); i++) {
            if (n%i == 0) {
                if (pd(i, n / i, maxnum + temp - n / i + 1, temp))
                    return 0;
            }
        }
        cout << -1;
        return 0;
    }
    else cout << -1;
}

由于未知的原因,最后一个if中的两个循环不能合并(我也不知道为什么),合并后会在第七个点wa

标签: implementation, constructive algorithms, brute force

添加新评论