专栏文章

题解：P11846 [USACO25FEB] Transforming Pairs P

PPurslaneM2GA
P11846题解参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miq2c3nl
此快照首次捕获于
2025/12/03 21:48
3 个月前
此快照最后确认于
2025/12/03 21:48
3 个月前
查看原文

Solution

简单模拟题。
先考虑 a,b≥0a,b \ge 0 的情况（显然 a,b≤0a,b \le 0 可以转化过来）。发现过程中一定有 a′≥0a' \ge 0、b′≥0b' \ge 0 恒成立。如果出现 c<0c<0 或 d<0d<0 无解。
所以如果我们知道了 (c,d)(c,d)，往前推一步，要么是 (c−d,d)(c-d,d)，要么是 (c,d−c)(c,d-c)。显然如果 c≠dc \neq d，肯定是大的减去小的。而如果 c=dc=d，则 (c,0)(c,0) 和 (0,c)(0,c) 都可以作为上一步。
所以我们直接模拟辗转相除即可。最小步数存在且唯一。
接下来考虑 a>0a>0、b<0b<0 的情况。（因为 aa 和 bb 高度对称，所以可以大量化归。）
如果 c<0c<0 且 d>0d>0，显然不可能成功了。
否则，如果 c≥0c \ge 0 且 d≤0d \le 0，不妨设 a′=aa' = a、b′=−bb' = -b，则 (a,b)→(a+b,b)(a,b) \to (a+b,b) 可以改写为 (a,−b′)→(a−b′,−b′)(a,-b') \to (a-b',-b')。所以我们可以把他倒过来写，也就是等价于求解 (c,−d)→(a,−b)(c,-d) \to (a,-b)。
否则，不妨设 c,d>0c,d > 0。
显然一定会出现某一个时刻满足 a′,b′≥0a',b' \ge 0。如果我们能找到这样一个位置，那么也就转化为最开始的情形了。
如果当前 a+b=0a+b=0，那么下一步一定就会出现 (0,b)(0,b) 或者 (a,0)(a,0)，可以直接暴力检验。
否则，如果 a>−ba > -b，下一步可以是 (a+b,b)(a+b,b)，也可以是 (a,a+b)(a,a+b)。发现后者就满足我们所需的“出现 a′,b′≥0a',b' \ge 0”，检验他。
我们会不断执行 a←a+ba \leftarrow a+b 直到 a≤−ba \le -b。所以我们会对若干个 kk 计算 (a+kb,a+(k+1)b)(a+kb,a+(k+1)b) 如何转移到 (c,d)(c,d)，最后令 a←a+tba \leftarrow a+tb。
此时不妨设 a<−ba < -b。那么转移到 (a+b,b)(a+b,b) 或者 (a,a+b)(a,a+b)。前者没有任何前途，因为会直接出现 a′,b′<0a',b' < 0。所以我们直接辗转相除跳到下一个端点即可。
但是我们会计算非常多次 (a,b)→(c,d)(a,b) \to (c,d)，这及其不友好。
发现我们可以将这样的 (a,b)(a,b) 划分为 O(log⁡V)O(\log V) 段，每一段的 a−ba-b 为定值，且这个东西随着段的增加是递增的。
而将 (c,d)(c,d) 反方向往前推的时候，c−dc-d 在 c>dc > d 的时候是严格递减的，所以可以直接维护几个等差数列，使用双指针优化即可做到 O(log⁡V)O(\log V) 单组询问。（不过你直接写 O(log⁡2V)O(\log^2 V) 的能过，而且还挺快）
CPP
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,a,b,c,d;
int solve(int a,int b,int c,int d) {
	if(c<0||d<0) return -1;
	int ans=0;
	if(a==c&&b==d) return 0;
	while(c!=0&&d!=0) {
		if(c==d) {
			if(a==0&&b==c||a==c&&b==0) return ans+1;
			if(a==c&&b==d) return ans;
			return -1;
		}
		if(c<d) swap(c,d),swap(a,b);
		if(c%d==0&&(a==0&&b==d||a==d&&b==0)) return ans+c/d;
		if(b==d&&a<=c&&(c-a)%d==0) return ans+(c-a)/d;
		ans+=c/d,c%=d;
	}
	if(a==c&&b==d) return ans;
	return -1;
}
void check(int &ans,int mzx,int nv) {
	if(mzx==-1) return ;
	ans=min(ans,mzx+nv);	
}
struct INFO {int l1,l2,r,d;};
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>a>>b>>c>>d;
		if(a==c&&b==d) {cout<<0<<'\n';continue ;}
		if(a<=0&&b<=0) a=-a,b=-b,c=-c,d=-d;
		if(a>=0&&b>=0) {cout<<solve(a,b,c,d)<<'\n';continue ;}
		if(a<0) a=-a,b=-b,c=-c,d=-d;
		if(c>=0&&d<=0) {cout<<solve(c,-d,a,-b)<<'\n';continue ;}
		if(c<0) swap(a,b),swap(c,d),a=-a,b=-b,c=-c,d=-d;
		if(c<0&&d>0) {cout<<-1<<'\n';continue ;}
		vector<INFO> vc;
		int cc=c,dd=d;
		while(cc!=0&&dd!=0) {
			if(cc<=dd) {dd%=cc;continue ;}
			vc.push_back({cc%dd+dd,cc,dd,dd}),cc%=dd;
		}
		int v=__gcd(c,d);
		int ans=LONG_LONG_MAX,al=0;
		while(a>0&&b<0) {
			if(a+b==0) {check(ans,solve(a,0,c,d),al+1);break ;}
			if(a+b<0) {al+=(-b)/a,b=-((-b)%a);continue ;}
			if(-b==v) {
				int dl1=v,dl2=v,rr=0,ll=v;
				if(ll<=a&&(a-ll)%(-b)==0) check(ans,solve(ll,rr,c,d),al+(rr-a)/b);
			}
			for(auto id:vc) {
				int dl1=id.l1-id.r,dl2=id.l2-id.r;
				if(dl1<=-b&&-b<=dl2&&(-b-dl1)%id.r==0) {
					int rr=id.r,ll=rr-b; 
					if(ll<=a&&(a-ll)%(-b)==0) check(ans,solve(ll,rr,c,d),al+(rr-a)/b);
				}
			}
			al+=a/(-b),a=a%(-b);
		}
		if(a>=0&&b>=0) check(ans,solve(a,b,c,d),al);
		if(ans!=LONG_LONG_MAX) cout<<ans<<'\n';
		else cout<<-1<<'\n';
	}
	return 0;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...