题解：AT_abc402_f [ABC402F] Path to Integer
违规用户名920406
·
·
题解
分析
很微妙的折半搜索题。
首先我们发现每经过一个格子后它的贡献是一定的，找规律可知 A_{i,j} 的贡献为 10^{2n-i-j}A_{i,j} ，这就变成了一个方格取数？
但是它要你求取模后的最大值，不过我们发现如果上一格如果是模后最大值，但是下一个格子加上之后就不一定了。不能 dp ，只能爆搜？
考虑折半搜索，Meet in middle。这个东西简单来说就是先将现在要搜索的东西平分成两段，最后再整合信息，输出答案。这题中怎么分？
用矩阵右上到左下的对角线将它分为两半，对于每个对角线上的数，计算起点和终点到它的路径的所有可能结果，分别存入两个 set 。然后整合结果。遍历第一个 set ，也就是起点到中点的路径，再第二个 set 中找中点到终点的路径。设刚才遍历到的值为 $x$ , $0 \leq x < M$ 。并且第二个 set 中只有两个数有可能成为最好路径。第一个是小于 $M-x$ 的最大值，第二个是直接的最大值。想一想，为什么？
## Code
实现中用了 set 中内置的二分函数，用法和普通的 upper_bound 和 lower_bound 差不多。赛时代码有点丑。仅供参考。
```c++
#include <bits\stdc++.h>
#define int long long
using namespace std;
int n,m,ans,a[21][21],p[39]={1};
set<int> s[21][21];
void dfs(int x,int y,int X,int Y,int S)
{
S=(S+a[x][y])%m;//记得取模
if(x==X&&y==Y)
{
s[x][y].insert(S);//加入set
return;
}
if(x<X) dfs(x+1,y,X,Y,S);
if(y<Y) dfs(x,y+1,X,Y,S);
}//从起点到中点的搜索
void dfs2(int x,int y,int X,int Y,int S)
{
S=(S+a[x][y])%m;
if(x==X&&y==Y)
{
s[x][y].insert(S);//加入set
return;
}
if(x>X) dfs2(x-1,y,X,Y,S);
if(y>Y) dfs2(x,y-1,X,Y,S);
}//从中点到终点的搜索
int main()
{
cin>>n>>m;
for(int i=1;i<=2*n-2;i++) p[i]=10*p[i-1]%m;//预处理10的幂
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
a[i][j]=a[i][j]*p[2*n-i-j]%m;//计算单点贡献
}
if(n==1)
{
cout<<a[1][1]%m;
return 0;
}//记得特判，不然wa两个点
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i+j-1==n) dfs(1,1,i,j,0);
if(i+j-1==n+1)
{
dfs2(n,n,i,j,0);
for(auto k:s[i][j])
{
if(i>1)//最好判一下边界
{
auto p=s[i-1][j].lower_bound(m-k);
if(p!=s[i-1][j].begin()) ans=max(ans,k+*prev(p));//情况1
ans=max(ans,k+*s[i-1][j].rbegin()-m);//情况2
}
if(j>1)
{
auto p=s[i][j-1].lower_bound(m-k);
if(p!=s[i][j-1].begin()) ans=max(ans,k+*prev(p));//情况1
ans=max(ans,k+*s[i][j-1].rbegin()-m);//情况2
}
}
}
}
cout<<ans;//华丽的输出qwq~
return 1;
}
```
呼，写完了。看懂记得点赞哦。