自动搬运

查看原文

来自洛谷，原作者为

	天南星魔芋 我回来了，我就没走

搬运于2025-08-24 22:38:17，当前版本为作者最后更新于2022-05-14 19:28:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意坑点：$a0,a1$ 可能和 $x,y$ 相同并且 $a0$ 或 $a1$ 不大于 k。

思路：

因为让 $a0,a1$ 凑 $x,y$ 肯定不行（1e9），所以考虑将这两对数化作相同的一对数。

然后想到往小凑。（因为往大凑的话没有上界，肯定不行）

若一数对能构成的最小数对的唯一，并且求最小数对方法正确，所以只要求出 $a0,a1$ 构成的最小数对 和 $x,y$ 构成的最小数对，然后比较他俩是否一样就行了。（注意数对中两个数的先后顺序）

然后就是证明一数对能构成的最小数对的唯一，并且方法正确：

1. 对于一对数，若只考虑减法，那么只有一种构造方案。

2. 加入加法，设当前为 $x,y$ ，加一次后就是 $y,y+x$，然后对 $y,y+x$ 持续做减法：$y,y+x$ 变成 $y+x,x$ 变成 $x,y$，也就是我们发现一次加法可以被两次减法抵消，加法对于结果没有影响。

也就是说只要不断做减法，直到无法运算为止，就能得出构成的最小数对。

因为求最小数对方法唯一，所以构成的最小数对唯一。

然后我们模拟减法，即可拿到 $50$ 分。

$code:$ 50 pts

#include<bits/stdc++.h>
using namespace std;
int T;
int x,y,xx,yy,k;
void cl(int &a,int &b){
	while(1){
		int ABS=abs(a-b);
		if(ABS>=k){
			a=b;
			b=ABS;
		}
		else break;
	}
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&k);
		if(k>xx||k>yy||k>x||k>y){
			puts("no");
			continue;
		}
		if(x==xx&&y==yy){
			puts("yes");
			continue;
		}
		cl(x,y);cl(xx,yy);
		if(xx!=x||yy!=y)puts("no");
		else puts("yes");
	}
}

思考为什么 T 了，发现模拟减法算法复杂度高。（比如一个 1e9 ，一个 1，肯定 T）

然后就是对模拟减法的优化，我们对于连减要分类讨论一下：

• $x,y$ 并且 $x>y$ $x,y$ 变成 $y,x-y$ 变成 $x-y,x-y-y$ 变成 $x-y-y,y$。

• $x,y$ 并且 $x<y$ $x,y$ 变成 $y,y-x$ 变成 $y-x,x$ 变成 $x,y-x-x$。

通过观察发现，若大的超过了小的的两倍，那么大的可以直接减去两个小的并且不做交换。

我们每次可以观察大的可以减去多少个小的，若为奇数个，减完交换，否则就直接减。

$code:$ 100 pts

#include<bits/stdc++.h>
using namespace std;
int T;
int x,y,xx,yy,k;
void cl(int &a,int &b){
	while(1){
		if(a<b){
			int now=(b-k)/a;
			if(!now)break;
			b-=now*a;
	    	if(now&1)swap(b,a);
		}
		else if(a>b){
			int now=(a-k)/b;
			if(!now)break;
			a-=now*b;
			if(now&1)swap(a,b);
		}
		else break;
	}
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&k);
		if(k>xx||k>yy||k>x||k>y){
			puts("no");
			continue;
		}
		cl(x,y);cl(xx,yy);
		if(xx!=x||yy!=y)puts("no");
		else puts("yes");
	}
}

所以这有黑题难度吗？