题解归档 - cf2231F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2231F
• 本地来源：problems/cf2231F/idea.md
• 题目链接：https://codeforces.com/contest/2231/problem/F
• 原始标题：cf2231F Quadratic Jumps

思路

cf2231F Quadratic Jumps

数学记录

• pattern: shortest path on square-difference graph / sum and difference of squares.
• claim: 答案只需要判断 1,2,3，否则为 4。
• one step: b-a 是平方数。
• two steps: 若差值是两个平方和，可同向走；若差值是两个平方差，可先越过一侧再回来，只要中间点还在 [1,n]。
• three steps: 枚举从 a 走一个平方到 y，若 y 到 b 可两步，则答案为 3。
• brute/check: 小 n 建完整图 BFS。

做法

预处理：

• isSq[x]：x 是否平方。
• sum2[x]：x 是否两个正平方和。
• needDiff[x]：把 x=big-small 写成两平方差时所需的最小 big。

判断 can2(a,b,n)：

• 差是平方或两个平方和；
• 或能用两平方差，且需要越出的最大空间不超过 max(b-1,n-a)。

每个询问先判 1、2；否则枚举所有平方第一跳，能接 can2 则 3，否则 4。

验证

• python tools/run_exe.py cf2231F 通过官方样例。
• python tools/stress2.py cf2231F -n 1000 --keep-fail 通过。
• n=200000,q=100000 随机大输入冒烟通过。

代码

来源：problems/cf2231F/solution.cpp

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

struct Test{
    int n,q;
    vector<pair<int,int> > ask;
};

int main(){
    int T;
    scanf("%d",&T);
    vector<Test> tests(T);
    int maxn=0;
    for(int tc=0;tc<T;tc++){
        scanf("%d%d",&tests[tc].n,&tests[tc].q);
        maxn=max(maxn,tests[tc].n);
        tests[tc].ask.resize(tests[tc].q);
        for(int i=0;i<tests[tc].q;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            tests[tc].ask[i]={a,b};
        }
    }
    vector<int> squares;
    vector<char> isSq(maxn+1,0),sum2(maxn+1,0);
    for(int i=1;i*i<=maxn;i++){
        squares.push_back(i*i);
        isSq[i*i]=1;
    }
    for(int x:squares){
        for(int y:squares){
            if(x+y<=maxn) sum2[x+y]=1;
            else break;
        }
    }
    const int INF=1000000000;
    vector<int> needDiff(maxn+1,INF);
    for(int big:squares){
        for(int small:squares){
            if(small>=big) break;
            int diff=big-small;
            if(diff<=maxn) needDiff[diff]=min(needDiff[diff],big);
        }
    }
    auto can2 = [&](int u,int v,int n)->bool{
        if(u>v) swap(u,v);
        int x=v-u;
        if(x<=0) return false;
        if(isSq[x]) return true;
        if(sum2[x]) return true;
        int lim=max(v-1,n-u);
        return needDiff[x]<=lim;
    };
    for(auto &te:tests){
        for(auto [a,b]:te.ask){
            int x=b-a;
            if(isSq[x]){
                printf("1\n");
                continue;
            }
            if(can2(a,b,te.n)){
                printf("2\n");
                continue;
            }
            int ans=4;
            for(int sq:squares){
                if(sq>=te.n+1) break;
                int y=a+sq;
                if(y<=te.n && can2(y,b,te.n)){
                    ans=3;
                    break;
                }
                y=a-sq;
                if(y>=1 && can2(y,b,te.n)){
                    ans=3;
                    break;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}