正文开始

阅读理解

有一个

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>m$ ，这种情况就直接取 $y$ 的最大值就好了。
$x+y<m$ ，这也需要 $y$ 尽可能大，那么就找到第一个 $x+y<m$ 的 $y$ 就好了。

于是在排序后，由于

x

是单调不下降的，那么所取

y

就一定是单调不上升的，于是用一个双指针就可以了。

代码

CPP

#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;
}

题解：AT_abc402_f [ABC402F] Path to Integer

文章操作

正文开始

阅读理解

思路

代码

相关推荐

评论

题解：AT_abc402_f [ABC402F] Path to Integer