洛谷 NOIP 2023 模拟赛 P9837 汪了个汪

NOIP 2023 模拟赛 P9837 汪了个汪"/>

洛谷 NOIP 2023 模拟赛 P9837 汪了个汪

洛谷 NOIP 2023 模拟赛 P9837 汪了个汪

文章目录

• 洛谷 NOIP 2023 模拟赛 P9837 汪了个汪
• • 题目大意
  • 思路
  • code

题目大意

构造一个高为 n n n 的棋盘，第 i i i 行有 i i i 个格子。

每个格子里的数是 [ 1 , n ] [1 , n] [1,n]

并且每一行中的每个数各不相同，所有的横向无序二元组不相同，每一行的第一个数各不相同

思路

我们发现一共有 n ( n − 1 ) / 2 n (n -1 ) / 2 n(n−1)/2 的无序二元组，且每一个都要用到。

差为 i ∈ [ 1 , n − 1 ] i\in[1 , n - 1] i∈[1,n−1] 的无序二元组的数量为 n − i n - i n−i

我们考虑把每一列分开讨论，使得每一行的第 i i i 个二元组的差为 n − i n - i n−i

考虑这样的一种构造方案：设这一行的开头为 x x x ，那么这一行中的每一个数为 x , x + 1 , x − 1 , x + 2 , x − 2 ⋯ x , x + 1 , x - 1 , x + 2 , x - 2 \cdots x,x+1,x−1,x+2,x−2⋯

按照总数排序就好了

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 4005;
int mp[N][N] , sz[N] , n , pos[N];
int main () {int x , y;scanf ("%d" , &n);fu (i , 1 , n) {x = i;y = 0;while (x >= 1 && x <= n) {sz[i] ++;mp[i][sz[i]] = x;if (y > 0) y = -y;else y = -y + 1;x = i + y;}pos[sz[i]] = i;}fu (i , 1 , n) {fu (j , 1 , i)printf ("%d " , mp[pos[i]][j]);printf ("\n");}return 0;
}