题解：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，那么请检查你是不是改变了数对的相对位置。

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

#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;
}