非常奇葩的做法但是AC了,是否能够Hack?
查看原帖
非常奇葩的做法但是AC了,是否能够Hack?
378706
MoyunAllgorithm楼主2023/2/2 09:36

思路是这样的:

sum1=1+2++N2sum1= 1+2+ \cdots + \dfrac{N}{2},

sum2=(N2+1)+(N2)++Nsum2= (\dfrac{N}{2}+1)+(\dfrac{N}{2}) + \cdots +N

首先,如果 A+B>sum1+sum2A+B>sum1+sum2 或者 max(A,B)>sum2 \max (A,B)>sum2,无解。

之后,令 i[1,N],ai=ii \in [1,N], a_i=i

之后,从两端开始,对于数 aia_iaNi+1a_{N-i+1},如果两者调换位置后 sum2sum2 依旧大于等于 BB,那么交换,直到 sum1sum1 大于等于 AA。(见代码加星号部分)

个人分析:每次交换相当于给 sum2sum2 减一个奇数,给 sum1sum1 加一个同样的奇数,比如:

a={1,2,3,4,5,6}a=\{1,2,3,4,5,6\}

交换 a1,a6a_1,a_6,则 sum2sum2 加上 55sum1sum1 减去 55

交换 a2,a6a_2,a_6,则 sum2sum2 加上 33sum1sum1 减去 33

交换 a1,a6a_1,a_6,则 sum2sum2 加上 55sum1sum1 减去 11

我发现,若干个从 11 开始的连续奇数,假如有 KK 个,则它们可以组成 [0,K2][0,K^2] 之间的所有数,但不能组成 22K22K^2-2。 因此特判这两种情况,其它的都可以被组成。

时间复杂度为严格的 O(N)O(N)

我自认为逻辑没什么问题,也通过了所有测试点,如果有人能够证伪或给出 hack 数据,或者给出严谨的正确性证明,非常感谢o(〃^▽^〃)o

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
long long A,B;
long long sum1,sum2;
int N,T;
int a[MAXN];
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&N);
		sum1=0,sum2=0;
		for(int i=1;i<=N;i++)
		{
			a[i]=i;
			if(i<=N/2) sum1+=i;
			else sum2+=i;
		}
		scanf("%lld %lld",&A,&B);
		if(A+B>sum1+sum2||max(A,B)>sum2) puts("-1");//判无解
		else if(A+B==sum1+sum2&&(abs(sum1-A)==2||abs(sum2-A)==2)) //特判!
		{
			if(abs(sum1-A)==2)
			{
				swap(a[N/2-1],a[N/2+1]);
			}
			else 
			{
				for(int i=1;i<=N/2;i++) swap(a[i],a[N-i+1]);
				swap(a[N/2-1],a[N/2+1]);
			}
			for(int i=1;i<=N;i++) printf("%lld ",a[i]);
			puts("");
		}
		else//***************************
		{
			bool flag=0;
			for(int i=1;i<=N/2;i++)
			{
				if(sum1>=A&&sum2>=B) 
				{
					flag=1;
					break;
				}
				if(sum2-a[N-i+1]+a[i]>=B) 
				{
					sum2=sum2-a[N-i+1]+a[i];
					sum1=sum1-a[i]+a[N-i+1];
				//	printf("%lld %lld\n",sum1,sum2);
					swap(a[i],a[N-i+1]);
					if(sum1>=A&&sum2>=B) flag=1;
				}
			}
			if(flag==0) printf("-1");
			else for(int i=1;i<=N;i++) printf("%lld ",a[i]);
			puts("");
		}/*******************
	}
	return 0;
}
2023/2/2 09:36
加载中...