自动搬运

查看原文

来自洛谷，原作者为

	sgl654321 风起雨停，天又放晴

搬运于2025-08-24 22:31:43，当前版本为作者最后更新于2024-02-21 09:59:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这一题模拟赛做到的，也作为自己状压 dp 和根号分治的学习笔记，所以比较详细。

题目大意

• 有一个 $n\times n$ 的棋盘，每个点 $(i,j)$（第 $i$ 行，第 $j$ 列）上有一个数 $a_{i,j}$。
• 小马第 $0$ 秒在起点 $(1,1)$ 上，然后他会以中国象棋里面跳马的方式在棋盘里跳跃，每次跳跃会耗费 $1$ 的时间。
• 对于 $(i,j)$ 这个点，若当前时间 $t$ 满足 $a_{i,j}\big|t$，那么它可以经过。否则无法经过，相当于一个障碍。
• 询问经过 $t$ 秒以后，小马可能在哪些位置，并输出它们。

解题思路

考虑设计 dp 状态

首先考虑暴力 dp。设 $F[i][j][k]$ 表示经过 $i$ 秒时间，是否可能在 $(j,k)$ 这个位置上，转移就是直接跳马。当然，作为一道紫题，肯定不会放过这种 $O(n^2t)$ 的大暴力。

那么我们发现，这个 $n\le 30$，值域非常之小。我们自然想到状态压缩的算法，一下子记录一整行的信息。

具体地，我们定义 $f[i][j]$ 表示经过 $i$ 秒时间，$j$ 这一行的状态。即：

$$f[i][j]=\sum_{k=1}^{n}F[i][j][k]\times 2^{n-k}$$

我们考虑弱化一下这个题目，设现在没有 $a_{i,j}\big|t$ 的限制，那么我们就可以简单转移：（由于写公式不好写，我用 C++ 代码呈现）

if(j-2>=1) s|= (f[i-1][j-2]<<1) | (f[i-1][j-2]>>1);
if(j-1>=1) s|= (f[i-1][j-1]<<2) | (f[i-1][j-1]>>2);
if(j+1<=n) s|= (f[i-1][j+1]<<2) | (f[i-1][j+1]>>2);
if(j+2<=n) s|= (f[i-1][j+2]<<1) | (f[i-1][j+2]>>1);

就是上一个时刻的 $8$ 个可能点。最后 $s$ 就是 $f[i][j]$ 了。

但是我们现在有了这个 $a_{i,j}\big|t$ 的限制，我们就要处理出，在 $i$ 这个时刻，$(j,k)$ 是不是障碍，记作 $Can[i][j][k]$。

同理，我们可以状态压缩成二维，变成 $can[i][j]$ 这个二维数组。

有了 $can[i][j]$，就有 $f[i][j]=s \text{ and }can[i][j]$。

现在的问题就转化成处理 $can[i][j]$ 了。

考虑处理 $can[i][j]$

你会发现直接处理它，比较困难，还是会回到最初 $O(n^2t)$ 的复杂度。这个时候我们考虑两种情况：

我们设一个阈值 $d$。

当 $a_{i,j}$ 比较大的时候，即 $a_{i,j}>d$，$a_{i,j}$ 在 $[1,t]$ 之间的倍数会比较少。这个怎么办，我们直接把贡献 $2^{n-j}$ 或到 $can[k\times a_{i,j}][i],k\in \mathbb{N}^+$ 就行了。

当 $a_{i,j}$ 比较小的时候，即 $a_{i,j}\le d$，我们可以直接记录下值为 $i$ 的元素，在第 $j$ 行出现的状态是什么，记作 $cnt_{i,j}$。

在 dp 的时候，对于当前时间 $i$，求出它在 $[1,d]$ 之间的因数有哪些，然后对于所有的因数 $div$，对于每一行 $j$，把 $can[i][j]$ 或上 $cnt[div][j]$ 即可。

考虑下这样的复杂度是什么。

• 对于第一种情况，复杂度显然为 $O(n^2\times \dfrac{t}{d})$，瓶颈在预处理。

• 对于第二种情况，复杂度瓶颈不在预处理，而在 dp 的时候。我们设 $div(i,j)$ 表示数 $i$ 在 $[1,j]$ 内的因数个数。复杂度为 $O(t\times d+n\times \sum_{i=1}^t div(i,d) )$

我们发现这两个复杂度，一个 $d$ 被除了，一个 $d$ 被乘了。这种情况下，就会有均值不等式出现。

但是由于还有一个 $div(i,d)$ 感觉不太好搞，所以我们先考虑放大一下这个下式。我们把它直接放大成 $O(n\times t\times d)$。

那么我们有：

$$n^2\dfrac{t}{d}+ntd\ge nt\sqrt{n},d=\dfrac{n}{\sqrt{n}}\approx 6\text{ 时取等号。} $$

由于我们放大了一些下式，那么其实最优的 $d$ 应当比这个大。事实上，根据后文对于空间复杂度的分析，我们应该把 $d$ 开大很多。

由于这里的时限 1.5s 非常充裕，所以随便了。这下我们就得到了正解代码？……真的是这样吗？这里是提交记录，只 AC 了 4 个点，其他都 MLE 了。

为什么呢？因为我们的空间只有 64MB，你的 $f,can$ 两个数组都开到了 $10^6\times 30$，直接爆炸了！

考虑优化空间

首先，$f$ 这个数组你会发现 $i$ 只与 $i-1$ 有关，这意味着你可以使用滚动数组，直接把它大大压缩到了 $n$ 的级别。

那么 $can$ 这个数组就没那么好办了，因为你预处理的时候有一个枚举 $k$ 的过程，这个影响不能用滚动数组处理。

所以我们不能直接把这个贡献或到 $can[k\times a_{i,j}][i]$ 里面去，而要对每一个时间 $i$ 开一个 vector $v_i$，里面记录预处理时，你有哪些 $(j,k)$。然后在 dp 的时候，再把贡献算到当前的数组 $can$ 里面去。

就像这样：

for(int k=1;k<=t/a[i][j];k++)
	v[ k*a[i][j] ].push_back(make_pair(i,j));

在 dp 时就:

for(auto x:v[i]){
	fi=x.first;
   	se=x.second;
	can[fi]|=1<<(n-se);
}

这样的话，你的空间瓶颈就是 vector 的空间了。vector 里面的 pair，即 $i,j$ 都是小于等于 $30$ 的，我们直接使用 char 类型就可以。

空间复杂度为 $O(n^2\dfrac{t}d)$。常数为 $2$，因为有 $2$ 个 char。注意到 $n=30,t=10^6$ 的最大情况时，$d=\dfrac{2n^2t\text{ Byte}}{64 \text{MB}}\approx 26$，同时由于 vector 初始也有空间，其他变量也有空间等等，我们得把 $d$ 开的比 $26$ 还要大一点点。反正你的时间充裕，我直接开了个 $d=200$。

这样我们这题就解完了。

参考代码

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
typedef int ll;
typedef pair<char,char> pll;
struct node{
	ll x,y;
}ans[1010];
ll n,t,x,y,a[40][40],f[2][40],d,s,now,las,can[40];
ll cnt[1010][40],sum,fi,se;
vector<pll>v[maxn];

int main(){
	cin>>n>>t>>x>>y;
	d=200;
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			cin>>a[i][j];
			/*
			根号分治算法：设立一个阈值 D，对于 x<=D 的，我们用一种解法
			对于 x>D 的，我们使用另一种解法
			
			case 1: 如果 a[i][j]>D 说明，它比较大，是 a[i][j] 倍数的 t 不是很多
			那么我们可以直接 for 过去加贡献 can [ k*a[i][j] ][i] |= ( 1<< n-j )
			-------------------------------------------------------------
			case 2: 如果 a[i][j]<=D 我们考虑首先记录下，对于值为 u 的元素，在第 v 行的状态 f[u][v]
			那么，就是 cnt[ a[i][j] ] [i] |= ( 1<< n-j ) 
			
			然后统计答案的时候该怎么办呢？见下半部分的注释。
			
			
			*/			
			if(a[i][j]<=d)cnt[a[i][j]][i]|=(1<<(n-j));
			else 
				for(k=1;k<=t/a[i][j];k++)
					v[ k*a[i][j] ].push_back(make_pair(i,j));
		}
	f[0][x]=(1<<(n-y));
	for(i=1;i<=t;i++){
		/*我们要把 case 2 的贡献也加到 can 里面去。
		这里的 a[i][j] 都很小 (<=D)，因此我们可以直接 枚举 1 ~ D  
		看看里面是他的因数的有几个，然后处理这个贡献。
		*/
		now=i%2;las=1-now;
		for(j=1;j<=n;j++)can[j]=0;
		for(auto x:v[i]){
			fi=x.first;se=x.second;
			can[fi]|=1<<(n-se);
		}
		
		for(j=1;j<=d;j++)
			if(i%j==0)
				for(int k=1;k<=n;k++)
					can[k]|=cnt[j][k];
	
		for(j=1;j<=n;j++){
			s=0;
			if(j-2>=1) s|= (f[las][j-2]<<1) | (f[las][j-2]>>1);
			if(j-1>=1) s|= (f[las][j-1]<<2) | (f[las][j-1]>>2);
			if(j+1<=n) s|= (f[las][j+1]<<2) | (f[las][j+1]>>2);
			if(j+2<=n) s|= (f[las][j+2]<<1) | (f[las][j+2]>>1);
		
			f[now][j]=s&can[j];
		}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(f[now][i]&(1<<(n-j)))
				ans[++sum]=node{i,j};
	cout<<sum<<endl;
	for(i=1;i<=sum;i++)
		cout<<ans[i].x<<" "<<ans[i].y<<endl;
	/*
	时间复杂度分析： 
	a[i][j] > D 瓶颈在预处理，O(n^2 t/D) 
	a[i][j] < D 瓶颈在 dp 转移时处理贡献， O( t( D+ n* ∑f(t,D) ) ) 
	其中 f(i,j) 表示，值为 i 的元素在 [1,j] 中的因数有几个。
	
	这个东西啊，不好分析，，直接尝试微调阈值当然是一种方法。
	考虑放大一点，直接变成 n^2 t/D + ntD >= nt\sqrt(n)
	这样的话，你取 D = n/sqrt(n)
	由于你放大了 case 2, case 2 是 ×D 的，所以 D 应该更大一点。
	大多少我就不知道了，反正 nt\sqrt(n) 在本题应该也足以通过了。  
	*/ 
	return 0;
}