牛客练习赛45 C.Buy Fruits(构造)

传送门

n = 1 n=1 n=1时,把第一个位置设置为 0 0 0可以知道一定有解

然后一个合法的解,最后一定走到 A i = 0 A_i=0 Ai=0的位置

奇数情况

在此之前一共走了 1 + 2 + 3... + ( n − 1 ) = n ∗ ( n − 1 ) 2 1+2+3...+(n-1)=\frac{n*(n-1)}{2} 1+2+3...+(n1)=2n(n1)

n n n为奇数时有 n − 1 n-1 n1为偶数,那么 n ∗ ( n − 1 ) 2 \frac{n*(n-1)}{2} 2n(n1)一定是模 n n n 0 0 0

也就是最后走回第一个位置,但第一个位置为 0 0 0显然不满足条件

偶数情况

n n n为偶数,有比较简单的构造方式

因为 n ∗ ( n − 1 ) 2 \frac{n*(n-1)}{2} 2n(n1) n 2 \frac{n}{2} 2n 0 0 0,所以位置 n 2 \frac{n}{2} 2n一定是 0 0 0

由第零个位置走到最后一个位置

再由最后一个位置走到第一个位置…

这样正向是一个 n − 1 n-1 n1开头的公差为 − 2 -2 2的等差数列

然后填数字 0 0 0(位置 n 2 \frac{n}{2} 2n)

然后是一个 n − 2 n-2 n2开头的公差为 − 2 -2 2的等差数列

#include bits/stdc++.h
using namespace std;
int n;
int main()
{
	cin  n;
	if( n==1 ){	cout  0; return 0; }
	if( n%2==0 )
	{
		int id = n-1;
		for(int i=1;i=n;i++)
		{
			cout  id  " ";
			id-=2;
			if( id==-1 )	id=0;
			else if( id==-2 )	id = n-2;
		}
	}
	else
	{
		cout  -1;
	}
}
最新回复(0)
/jishuUk_2FHVry1nH8ANm7knPrl7NiNXxP9gDiSFcwpzq5jgxw_3D4834424
8 简首页