题解：P16343 [科大国创杯初中组 2026] 行走

xiaomi1026 · 2026-04-23 07:16:01 · 题解

题意明确，不说了。

思路

因为 \gcd 没有最优的性质，所以下面的转移是错的，考场时我就被这么坑掉了。

dp[i][j]=max(__gcd(dp[i-1][j],a[i][j]),__gcd(dp[i][j-1],a[i][j])); 

现在考虑正确的解法，因为答案必定是起点与终点的一个公因数，所以可以枚举起点的所有公因数，看看有没有路径能到达终点。此时 dp[i][j] 表示当前位能否到达，为 bool 类型。
如果当前位满足且左边或上边有至少一个满足才算可以到达。
反之则不能到达。
虽然在极端情况有点极限，不过是正解，可以稳过的。

代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long> q;//使用优先队列记录公因数。
long long n,v;
long long a[1100][1100];
bool dp[1100][1100];
bool check(long long x){
    if(a[n][n]%x!=0) return 0;
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        if(a[1][i]%x==0&&dp[1][i-1]==1) dp[1][i]=1;
        else dp[1][i]=0;
    }
    for(int i=2;i<=n;i++){
        if(a[i][1]%x==0&&dp[i-1][1]==1) dp[i][1]=1;
        else dp[i][1]=0;
    }
    for(int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            if(a[i][j]%x!=0||(dp[i-1][j]==0&&dp[i][j-1]==0)) dp[i][j]=0;
            else dp[i][j]=1;
        }
    }
    return dp[n][n];
}
int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i*i<=a[1][1];i++){//求公因数。
        if(a[1][1]%i==0){
            q.push(a[1][1]/i);
            q.push(i);
        }
    }
    while(!q.empty()){//遍历公因数。
        if(check(q.top())){
            cout<<q.top();
            return 0;
        }
        q.pop();
    }
    cout<<1;
    return 0;
}//dk

感觉代码有点长了，不过还是挺直观地。
数据很水，一些复杂度错的严重的都满分了，本人状态转移写错还有 60 分。
AC 记录。