CF1517C Fillomino 2

发布于 2021-05-08  1.45k 次阅读


题目链接

分析

从左下往右上依次考虑每一条从左上至右下的对角线。

显然在 $y-x+1=v$ 的对角线上只能放置值在 $[v,n]$ 范围内的数字。

同时显然每一条对角线上的数字的相对排列顺序一定与输入的相对排列顺序相同。

按照我们上面考虑的顺序遍历每一条对角线,并动态维护该对角线上的数字序列:当前对角线上的数字序列仅会比上一条访问到的对角线的数字序列多一个数字。将该数字按照输入的相对排列顺序插入到对应位置即可。

如果觉得解释比较抽象可以对着样例,或是自己手造几个输出对着看一看,就能看出上面说的几个规律了。

代码

代码比解释简洁很多

CF 比赛时打的比较急,直接写 sort 了。可以使用插入排序以获得更好的时间复杂度。

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

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

namespace io {

// fread

}  // namespace io
using io::getch;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 505

int a[maxn][maxn], pos[maxn];

vector<int> vec;

inline bool cmp(int a, int b) { return pos[a] < pos[b]; }

int main() {
    int n = read<int>();
    for (register int i = 1; i <= n; i++) pos[read<int>()] = i;
    for (register int t = 1; t <= n; t++) {
        vec.push_back(n - t + 1);
        sort(vec.begin(), vec.end(), cmp);
        for (register int i = 0; i < t; i++) a[n - t + i + 1][i + 1] = vec[i];
    }
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= i; j++)
            write(a[i][j]), putch(" \n"[j == i]);
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话