题解：P8348 「Wdoi-6」未知之花魅知之旅

P8348 「Wdoi-6」未知之花魅知之旅

还是上面那张图好看 /se，但是可惜的是没法交那道题的题解了。

有一说一，梅莉和莲子真的好看 /se。

如果你猜到结论就是猜到了，没猜到就是没猜到，但是这个结论还是很好猜的。

转化一下题目：给定两个数

(a_0,a_1)

，通过相加 / 减的方式变成

(x,y)

并且中途两个数的取值范围均为

[k,+\infty)

。

补充一下，这个数对是在操作序列中用长度为 2 的滑动窗口滑出来的，所以请保证他们的相对位置不变！

发现没有给上限，那么把

(a_0,a_1)

转成

(x,y)

显然不合理。

转换一下，找到一个中间状态

(x_1,y_1)

满足

(a_0,a_1)

和

(x,y)

都可以通过转换得到这个状态。

反正又没有次数限制 ┑(￣Д ￣)┍。

那就有人要问了，主播主播，你前面都说了

(a_0,a_1)

转成

(x,y)

不合理，那只不过转了一个中间态怎么就合理了？

你说的对，但是我们可以限定

(x_1,y_1)

为

(a_0,a_1)

能变为的最小数对，然后问

(x,y)

的最小数对是否也是

(x_1,y_1)

就行了。

原因就需要推结论了。

结论 1： $(x,y)$ 对应的最小数对 $(a,b)$ 唯一。

求最小数对肯定是做减法，但前提是加法对答案不会有影响。

如果对两者做加法再做减法：

(x,y)\stackrel{+}\longrightarrow(y,y+x)\stackrel{-}\longrightarrow(y+x,x)\stackrel{-}\longrightarrow(x,y)

。

可以发现一次加法可以被两次减法抵消掉，不影响最终答案。

如果只剩下减法了，这玩意其实就是裴蜀定理，辗转相减和辗转相除没啥本质区别，改成辗转相除就行了。

结论 2：如果 $(x,y)$ 能操作成 $(a,b)$ ，那么 $(a,b)$ 也能操作成 $(x,y)$ 。

这个比第一个好证，只需要证明加法和减法可以互相抵消就行了。

结论一中已经证明了一次加法可以被两次减法抵消。

那么两次减法也可以被一次加法抵消：

(x,y)\stackrel{-}\longrightarrow(y,y-x)\stackrel{-}\longrightarrow(y-x,x)\stackrel{+}\longrightarrow(x,y)

。

这就证出来了。

有了这两条，上面的做法的正确性就很显然了。

只不过辗转相减复杂度有点危险，很容易被卡成狗，事实上出题人确实卡掉了直接的辗转相减做法。

主播主播，辗转相减还是太吃操作了，有没有更简单而且强势的做法？

有的兄弟有的，前面说了辗转相减和辗转相除差不多，用类似辗转相除的方法（其实就是能减就一口气减完）就行了。

复杂度

O(T\log V)

。

需要注意的是别写嗨了，

(x,y)

的相对位置不能变，不然你就会跟主播一样盯代码盯了半个小时没找出问题。

同样的，如果你 WA10，那么请检查你是不是改变了数对的相对位置。

总体而言还是一道非常不错的人类智慧题。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;

namespace io
{
	inline int read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
	template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
	template<typename T>inline void write_(T x){write(x),putchar(' ');}
	template<typename T>inline void writeln(T x){write(x),putchar('\n');}
}
using namespace io;

int x,y,xx,yy,k;

void check(int&x,int&y)
{
	while(1)
	{
		int f=0,l=0;//l记录操作次数用来还原相对位置，f记录前面有没有交换
		if(x<y) swap(x,y),f=1;//注意不要改了相对位置，让f=1就行了。
		if(x-k<y)
		{
			if(f) swap(x,y);//就这里我调了半个小时
			break;//减不了那就不用减了。
		}
		l=(x-k)/y,x-=l*y;//修改
		if((l+f)%2==1) swap(x,y);//如果修改了奇数次就要注意交换来还原相对位置。
	}
}

void solve()
{
	x=read(),y=read(),xx=read(),yy=read(),k=read();
	if(min({x,y,xx,yy})<k){puts("no");return;}
	check(x,y),check(xx,yy);
	puts(x==xx&&y==yy?"yes":"no");
	return;
}

signed main()
{
	int t=read();
	while(t--) solve();
	return 0;
}

题解：P8348 「Wdoi-6」未知之花魅知之旅

文章操作

P8348 「Wdoi-6」未知之花魅知之旅

相关推荐

评论

题解：P8348 「Wdoi-6」未知之花魅知之旅