P8348 题解

robertuu · 2023-08-23 21:07:55 · 题解

题目传送门

这题怎么是黑题？？

关键点：所有的元素都需要大于等于 k，而上限没有边界，需要判断的元素很大，有 10^9。

由于如果同时考虑相邻两项做加法和减法决策太多（你 O(n) 都要 TLE 了还能有决策？），应该简化决策。

很明显，题目给出的元素下限就是一个“风向标”，告诉你要化成只做减法（加法都没边界，不知道得加到什么时候）。

可以假设需要使用加法才能判断是否可以位于一个“k 好”数列，观察加法的性质：x,y,x+y,x+2y,2x+3y,3x+5y,5x+8y

相信规则已经很明显了，x 和 y 的系数都是斐波那契数列的项，设 fib_n 表示斐波那契数列的第 n 项。

设数对 x,y 进行多次加法后得到的数为 fib_nx+fib_{n+1}y。

由于对于第一次加法得到的数 x+y，前一个数 y 的系数不是斐波那契数列（不存在对应 x 的系数的 fib_0），但是这一组数只需要进行两次减法就可以回到原数对 x,y，满足要求。

对于其他情况，它的上一个数一定是 fib_{n-1}x+fib_ny。对这个数对不断做减法：

可以发现，每进行两次减法，x 和 y 的系数都在斐波那契数列上前移一项，最终肯定能移到 fib_1x+fib_2y，即 x+y，变为第一种情况，可以操作回原数对。

因此证明了在原数对基础上使用加法后，若能使得读入的两个数对相同，使用减法也一定能达到相同的结果（把加法操作会原数对后再继续减法就相当于在原数对上使用减法），因此，我们可以只使用减法。

使用减法的朴素算法是 O(n) 的，会超时。但是可以发现减法的操作很像辗转相减的感觉，是不是也能用类似辗转相除的办法加速呢？答案是能的。

不妨设数对 x,y 中 y \ge x,y = ax + b + k（必须要有这个 k，否则会把数对减到 k 一下，不满足题意，这个 k 相当于是个限制）。

对这个数对进行减法：

可以发现 p 为奇数时，每一次出现 (a-p)x+b+k 都在 x 之前，和初始不一样；p 为偶数（包括 0）是恰好相反，出现在 x 之后磨合初始一样。因此可以确定“类辗转相除”策略，如果减的次数是偶数次，不用交换，直接减；如果减的次数是奇数次，需要在减完后交换顺序。

减法终止条件：y = x（相等了） 或 y - x < k（一个也不能再减了）。

AC code：

#include<bits/stdc++.h>
using namespace std;
int k;
void getmin(int &a,int &b) // 要修改具体值，必须传引用
{
    while(true)
        if(a < b)
        {
            int now = (b-k)/a; // 大于k的部分还能减多少次
            if(!now) return; // 减不了也退出
            b -= now * a;
            if(now % 2 == 1) swap(b,a); // 奇数交换偶不换
        }
        else if(a > b)
        {
            int now = (a-k)/b; // 大于k的部分还能减多少次
            if(!now) return; // 减不了也退出
            a -= now * b;
            if(now % 2 == 1) swap(a,b); // 奇数交换偶不换
        }
        else return; // 相等无法变换，退出
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int x,y,xx,yy;
        scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&k);
        if(k > xx || k > yy || k > x || k > y) // 不满足题目限制
        {
            printf("no\n");
            continue;
        }
        getmin(x,y); getmin(xx,yy); // 全部转化成两个数都大>=k的最小数对
        if(xx == x && yy == y) printf("yes\n"); // 同一个最小数对，满足要求
        else printf("no\n");
    }
}