CF1227G Not Same

神仙构造题,先 % 一下 wzy 鸽鸽

首先我们可以手模一下

比如

5 5 4 3 1
4 4 4 3 1
3 3 3 3 1
2 2 2 2 1
1 1 1 1 0
0 1 1 1 0
0 0 0 0 0

或许会有一种感觉就是将大的数削平成小的数,然后再将它们再削平成更小的数,以此类推

或者说,从大到小排序,然后每次将 1,1 2,1 2 3... 削平

结合削平这个感觉,我们可以将其画成一张图来直观感受 手模 一下

图是 wzy 鸽鸽的,我盗来用了,因为真的很清晰

如果画出了这样的一张图,那么思路就很明晰了,题意即为构造一个 n+1n+1nn 列的 0101 矩阵使得每列的染色方格的个数为某个 11nn 的数,最后一步是如何染色

答案是横着削,纵着染

具体的,对于 ai=ja_i=j,若 jni+1j\leq n-i+1,就从下往上依次染,否则先从下往上染满,然后跳到最底部从下往上染到 jj

code,构造题代码不难写,唯一比较坑的就在于要排完序输出时要还原一下