返乡(home
)
不给大样例是怕我找规律出答案吗?但是我还是找到规律了。
题解说是结论题,但是这个结论即使观察小样例也很好猜(如果我是出题人就把样例打乱一下顺序)。
首先考虑只有二维偏序时的最优放置方法:
首先第一个数是不能重复的,因为一旦重复,第二个数无论怎么选,都会构成偏序;第二个数同理,也不能重复。所以最多有 \((n+1)\) 个二元组。
那么我们将 \(0 \sim n\) 全部放上去,并且将第一个数排序,试试看能不能抵满上限。
因为不能构成偏序,所以对于第二个数,后面的不能比前面的更大(这样的话,因为后面的第一个数本来就比前面的第一个数更大,两个都更大就构成偏序了),所以后面的需要是从大到小的顺序排列。
当 \(N=4\) 时,一种最优放法如下:
(如果最左侧多了一列数字,请忽略,那是代码块行号,下同)
0 4
1 3
2 2
3 1
4 0
再来考虑三维偏序的情况:
如果第一个数相同,第二三个数可以转化成上面的二维偏序形式,放法与上面所述相同。
观察样例,第一个数为 \(0\) 有两个,\(1\) 有三个,\(2\) 有两个,所以我们先放 \(1\) 试试看:
1 0 2
1 1 1
1 2 0
放了 \(1\) 以后,对于第一个数小于 \(1\) 的,后面两个数的值域需要更大才能够不被 \(1\) 开头的三元组偏序,所以我们从 \(1\) 开始放(这个观察样例也很好发现吧)。
0 1 2
0 2 1
1 0 2
1 1 1
1 2 0
而第一个数大于 \(1\) 的三元组,后面数的值域应当更小才不会偏序 \(1\) 开头的三元组,我们只能放到 \(1\):
0 1 2
0 2 1
1 0 2
1 1 1
1 2 0
2 0 1
2 1 0
所以规律即为:从中间开始放数,前面的三元组后两个数的最小值逐渐增加,后面的三元组后两个数的最大值逐渐减小。
正确性严格证明不会,但是可以感性理解一下:第一个数递增或递减的时候,所可以构成的三元组数量每次都一定要减一的,把最开始三元组最多的那一个放在正中间可以让所减的值最小。
int n;
struct Triple{
int x,y,z;
}ans[300000];
int tot=0;
int main()
{
freopen("home.in","r",stdin);
freopen("home.out","w",stdout);
read(n);
for(int i=0;i<=n>>1;i++)
{
int s=(n>>1)-i; //start point
for(int j=s;j<=n;j++)
ans[++tot]={i,j,s+n-j};
}
for(int i=(n>>1)+1;i<=n;i++)
{
int t=n-(i-(n>>1)); //end point
for(int j=0;j<=t;j++)
ans[++tot]={i,j,0+t-j};
}
write(tot,'\n');
for(int i=1;i<=tot;i++)
write(ans[i].x,' '),write(ans[i].y,' '),write(ans[i].z,'\n');
return 0;
}