牛客contest5671-E

传送门

题目大意

给定n,k，构造一个1-n的排列P，满足对于1-n中的每个i，P都存在一个长为i的子序列，并且每个子序列的和模n都余k。有解则输出任意P，无解输出-1。

思路

首先考虑判断解存在的问题。根据题意，因为P也是自己的子集，所以一定也应该满足“所有元素的和模n余k”的题设，也就是sum(1~n)%n==k，如果不满足，那自然无解。

假设k满足上述条件，接下来的命题就是判断k了。

这种看似要进行复杂的动态处理的问题大多都有规律，这题也不例外。多写两行数据会发现，当n为奇数时，sum(1~n)一定是n的整数倍，即k==0；n为偶数时，k==n/2。

根据这个写代码就好了。

#include <bits/stdc++.h>

using namespace std;

int n, k;

int main()
{
	scanf( "%d%d", &n, &k );
	
	if ( n % 2 )
	{
		if ( !k )
		{
			for ( int i = 1; i <= n / 2; i++ )
				printf( "%d %d ", i, n - i );
			
			printf( "%d", n );
		}
		else printf( "-1" );
	}
	else  
	{
		if ( (n * (n + 1) / 2) % n == k )
		{
			for ( int i = 1; i < n / 2; i++ )
				printf( "%d %d ", i, n - i );
				
			printf( "%d %d", n / 2, n );
		}
		else printf( "-1" );
	}
	
	return 0;
}

这题赛时就是被吓到了，没找到规律。还是不能慌啊。