蒟蒻太菜了,看不懂图论的做法,就只好找规律了。
分析题目,可以得到一些信息:\(n\) 个不同的数最多能组成 \(\dfrac{n(n-1)}{2}\) 个不相同的无序二元组,而一个 $n \times n $ 的下三角形同行相邻的数对数量为 \(\dfrac{n(n-1)}{2}\),因此可以确定每个无序二元组必须恰好用一次。
观察二元组的差。显然,差为 \(1\) 的二元组有 \(n-1\) 个,差为 \(2\) 的无序二元组有 \(n-2\) 个……以此类推。于是,我们可以大胆猜想,将差相同的无序二元组放在同一行或相邻的两列上,这样可能可以构造出合法的答案。
模拟一下,不难发现,横着放会存在一个问题:例如 \(n=5\),第 \(2\) 行要放差为 \(4\) 的两个数对,显然放不下 \(4\) 个不相同的数,因此这样的方法不可行。
接下来考虑竖着摆放。第 \(1\) 列填 \(1,2,\cdots,n\),第 \(2\) 列填前一个数加 \(1\)(可以填 \(n-1\) 个,若超出 \(n\) 则该行填完),以此类推。但不能一直加,否则该行就无法填满。证明十分简单,此处不详解。
反向思考,既然差不变,那么我们可以加减交替操作,这样在确保符合要求的同时尽可能地多填数,从而保证该方案是一定可行的。
总体思路大致如上,注意输出前要先计算好每行的长度,再按行的长度从小到大地输出每一行。
具体细节实现详见代码:
#include <iostream>
#include <cstdio>
using namespace std;
int n,TT,len[100001],nw;
int main()
{
cin >> n >> TT;
for( int i = 1 ; i <= n ; i ++ )
{
nw = i;
for( int j = 1 ; nw >= 1 && nw <= n ; j ++ )
{
if( j & 1 ) nw += j;
else nw -= j;
len[i] ++;
}
}
for( int i = 1 ; i <= n ; i ++ )
{
for( int j = 1 ; j <= n ; j ++ )
if( len[j] == i )
{
nw = j;
for( int k = 1 ; nw >= 1 && nw <= n ; k ++ )//确保在 1 到 n 的范围内
{
cout << nw << ' ';
if( k & 1 ) nw += k;
else nw -= k;
}
cout << endl;
break;
}
}
return 0;
}
标签:二元,组有,int,无序,LG9837,include,nw
From: https://www.cnblogs.com/-lilong-/p/17976922