题解：AT_abc402_f [ABC402F] Path to Integer

· · 题解

题目跳楼机

正文开始

阅读理解

有一个 n 行 n 列的的矩阵，位置为 (i,j) 的值为 a_{i,j}（0\le a_{i,j}\le9，a_{i,j}\in\Z，0\le i,j\le n），现在需要你从 (1,1) 走到 (n,n)，每遇到一个点将它加入数的末尾，求 sum \mod m 的最大值。

思路

可以看到，n 不超过 20，但就算如此，O(2^{2n-1}) 的时间复杂度还是要炸，所以暴力搜索是不可能的……吗？

既然 O(2^{2n-1}) 要爆炸，那为什么不砍个半呢？我们可以把整个图沿 (1,n) 到 (n,1) 的这条对角线切一半，于是我们就得到了两个图，在这两个图上分别搜索，再将两个图上搜到的答案进行整合，寻找到最优的解不就是了。

那现在问题就变成了如何将这两个答案进行整合。

首先，我们可以发现一个明显的性质：位置为 (i,j) 的数统计答案时的贡献一定是 a_{i,j}\times10^{\lvert 2n-i-j\rvert}，所以我们就可以先算出来每个数最后的贡献取模后的值再进行搜索，当搜索到 i+j=n+1 的地方时就说明在对角线上，于是我们将这条路径的值存在这个点上。

统计答案时，很明显需要两个图（设第一个图答案为 x，第二个为 y）的答案相加，但如果一个一个枚举，也需要花很多时间。注意到要对 m 取模，那么由于 x<m，y<m，所以 x+y<m-1，于是我们就可以分成两种情况：

于是在排序后，由于 x 是单调不下降的，那么所取 y 就一定是单调不上升的，于是用一个双指针就可以了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int b[405];
int ans;
int d[25][25];
int a[25][25];
int c[3][25][1000006],cnt[25][1000006];
inline void dfs(int i,int x,int y,int s){
    if(x+y==n+1){
        if(i)s=(s+a[x][y])%m;
        c[i][x][++cnt[i][x]]=s;return ;
    }
    s=(s+a[x][y])%m;
    if(i){
        dfs(i,x-1,y,s);
        dfs(i,x,y-1,s);
    }
    else {
        dfs(i,x+1,y,s);
        dfs(i,x,y+1,s);
    }

}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int N=2*n-1;b[1]=1;
    for(int i=2;i<=N;i++)b[i]=(b[i-1]*10)%m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>d[i][j],a[i][j]=((d[i][j]%m)*(b[N-i-j+2]%m))%m;
    dfs(0,1,1,0);//从（1，1）开始 
    dfs(1,n,n,0);//从（n，n）开始 
    for(int i=1;i<=n;i++){
        sort(c[0][i]+1,c[0][i]+cnt[0][i]+1);
        sort(c[1][i]+1,c[1][i]+cnt[1][i]+1);
    }
    for(int i=1;i<=n;i++){
        int k=cnt[1][i];
        for(int j=1;j<=cnt[0][i];j++){
            ans=max(ans,(c[0][i][j]+c[1][i][cnt[1][i]])%m);
            for(;k;k--)
                if(c[0][i][j]+c[1][i][k]<m)break;
            if(!k)continue;
            ans=max(ans,(c[0][i][j]+c[1][i][k])%m);
        }
    }
    int s=ans;
    cout<<s;
    return 0;
}