6pts(SpJ)求助,找不出错误(答案层面)
  • 板块学术版
  • 楼主zcy_0v0
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/26 20:52
  • 上次更新2023/11/2 17:58:05
查看原帖
6pts(SpJ)求助,找不出错误(答案层面)
121404
zcy_0v0楼主2023/9/26 20:52

题目: P7999

情况:

属SpecialJudge
没有WA的点的样例,但是自己并不知道哪里出错了(换而言之,自己以为AC了然而WA了)

代码如下(带注释)

#include<bits/stdc++.h>
const int N=1e5+10;
using namespace std;
int n,a[N],x,pl[N],pr[N],now1,now2,pcnt,opr[3];
/*
	n,a,x:同题面
	pl,pr:存输出
	opr:归位 
	cnt:同m 
	ggg:见下方右/左移 

*/
long long cnt;
int ggg;
void _swap(int x1,int y)//交换距离为x的两个数 
{
	if(x1==y)
	return;
	if(x1>y)
	swap(x1,y);
	pl[cnt]=x1-1000;pr[cnt]=y-1000;
	cnt++;
	if(x!=1)
	{
		pl[cnt]=x1-999;pr[cnt]=y-1001;
		cnt++;
	}
	swap(a[x1],a[y]);
}
void solve(int l,int r)//交换任意距离的两个数  思想类似于题解2 大概率没问题 
{
	opr[1]=0;
	opr[2]=0;
	if(l==r)
	return;
	if(l>r)
	swap(l,r);
	if(r-l==x)
	{
		_swap(l,r);
		return;
	}
	while(r-l>x)
	{
		_swap(r-x,r);
		r=r-x;
		opr[1]++;
		if(r-l==x)
		{
			_swap(l,r);
			return;
		}
	}
	int R=l+x;
	if(r%2==R%2)
	{
		_swap(r,r+x);
		r=r+x;
		opr[2]=1;
	}
	opr[0]=r;
	int mid=(R+r)/2-1000;
	int L0_=1000+mid-x/2+1,R0_=1000+mid+x/2;
	if(L0_<R0_)
	{
		L0_=1000+mid-x/2+1;
		R0_=1000+mid+x/2;
	}
	else
	{
		R0_=1000+mid-x/2+1;
		L0_=1000+mid+x/2;
	}
	reverse(a+L0_,a+R0_+1);
	pl[cnt]=mid-x/2+1;pr[cnt]=mid+x/2;
	cnt++;
	_swap(l,R);
	reverse(a+L0_,a+R0_+1);
	pl[cnt]=mid-x/2+1;pr[cnt]=mid+x/2;
	cnt++;
	if(opr[2]==1)
	{
		_swap(opr[0],opr[0]-x);
		opr[0]-=x;
	}
	for(int i=1;i<=opr[1];i++)
	{
		_swap(opr[0],opr[0]+x);
		opr[0]+=x;
	}
}




int main()
{
//	freopen("std.txt","r",stdin);
//	freopen("a.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1001;i<=n+1000;i++)
		cin>>a[i];
	//输入	
	
	x=n/4;
	if(x%2==0)
	x--;
	if(n<4)
	x=1;ggg=(n/x/4)*x;
	//x的计算 
	
	for(int i=n;i>=1;i--)
	{
		long long x1=i,y;
		for(int j=1;j<=n/x/4;j++)
		{
			y=x1+x;
			pl[cnt]=x1-ggg;pr[cnt]=y-ggg;
			cnt++;
			if(x!=1)
			{
				pl[cnt]=x1+1-ggg;pr[cnt]=y-1-ggg;
				cnt++;
			}
			x1=y;
		}
	}
	//整体右移,防止端点为负 
	
	
	int acnt=0,bcnt;
	for(int i=1001;i<=1000+n;i++)
	{
		now2=11451419;
		now1=0;
		for(int j=1001;j<=1000+n;j++)
		{
			if(abs(a[j]+1000-j)<abs(now2-now1)&&abs(a[j]+1000-j)!=0)
			{
				now2=a[j]+1000;
				now1=j;
			}
		}
		if(abs(now2-now1)>=11451410)break;
		solve(now2,now1);
	}//排序,每次选择距离最小的两个数交换 
	
	
	for(int i=1;i<=n;i++)
	{
		long long x1=i+ggg,y;
		for(int j=1;j<=n/x/4;j++)
		{
			y=x1-x;
			pl[cnt]=y-ggg;pr[cnt]=x1-ggg;
			cnt++;
			if(x!=1)
			{
				pl[cnt]=y+1-ggg;pr[cnt]=x1-1-ggg;
				cnt++;
			}
			x1=y;
//		pcnt++;
		}
	}//整体左移归位 
	
	
	cout<<x<<endl<<cnt<<endl;
	for(int i=0;i<cnt;i++)
	{
		cout<<pl[i]+ggg<<" "<<pr[i]+ggg<<endl;
	}
//	for(int i=1001;i<=n+1000;i++)
//	cout<<a[i]<<" ";
	return 0;
}

参考程序(不保证完全正确)

造样例的

#include<bits/stdc++.h>
using namespace std;
int e=1000;
bool a[10002];
void solve(int c)
{
	int d=rand()%e+1;
	while(a[d]==1||d==0)
	{
		
		d%=e;
		d++;
	}
	cout<<d<<" ";
	a[d]=1;
}
int main()
{
	freopen("std.txt","w",stdout);
	cout<<e<<endl;
	for(int i=1;i<=e;i++)
	{
		solve(i);
	}
	return 0;
}

类SpecialJudge

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
const int N=1e5+10;
int n,cnt,l,r,a[N],x;
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	freopen("std.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	freopen("a.txt","r",stdin);
	cin>>x>>cnt;
	for(int i=1;i<=cnt;i++)
	{
		cin>>l>>r;
		if(r-l!=x&&r-l!=x-2)
		{
			cout<<"WA"<<endl<<i<<endl<<l<<" "<<r;
			return 0;
		}
		reverse(a+l,a+r+1);
	}
	cout<<cnt<<endl<<n<<endl;
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
}

2023/9/26 20:52
加载中...