P7630 题解

sgl654321 · 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;
}