混乱邪恶

· · 题解

P7606 [THUPC2021] 混乱邪恶

by jr_zch 博客食用更佳~

题目大意

给你一个蜂窝网络，你一开始在坐标 (0,0)，你一共有两种属性：L、R，起初都是 0，这两种属性都是在 \pmod p 意义下存在的。现在你有 n 张卡片，第 i 张卡片使用后，可以选择向六个方向之一前进一步，如果向方向 j 前进，会使得 L+l_{i,j}，R+r_{i,j}。

问：你是否有一种方案使得自己最后回到 (0,0)，且 L= *L，R=*R。

思路 & 解法

看见诸如使用，增加属性一类的词语，很容易想到背包问题，在不考虑坐标问题的情况下，这题可以转化为最基础的背包模型：

有了坐标限制之后也很简单，容易发现所谓蜂窝状的图可以转化为普通的网格图，只是在副对角线上多了一条边。若当前在 (x,y)，下一步可以走到 (x+1,y)、(x-1,y)、(x,y+1)、(x,y-1)、(x+1,y+1)、(x-1,y-1)。所以可以在原状态的基础上加两维表示当前的坐标。

这样一来，时间复杂度和空间复杂度都骤然升至了 O(n^5)，空间好说，滚动一维即可（最后其实可以不用），考虑优化时间。

回到最开始的题面，发现这是一个很经典的模型：随机游走。

一只蜘蛛原本在蛛网中央，现在它开始在网上乱走，步长为 1 个单位长度，但是最后又回到了原点，假设它一共走了 step 步，求它期望走到的相对于原点的最远距离为多少？

答案为 \sqrt n 步。

或者换一个说法：

给你一个长度为 n 的数列 a，要求从其中随机选取元素，每个元素只能选一次，一直选完整个数列，并且最后的和为 0，如果对于任意 1\leq i \leq n 都有 -c \leq a_i \leq c，求在整个选取过程中，已选元素之和的期望最大值和最小值分别为多少？

答案是 -c \cdot \sqrt n \leq sum \leq c \cdot \sqrt n。

关于证明，推荐大家看出题人 E_Space 的证明。

结合上述模型，我们先把输入随机排序，在将后面表示坐标的两维都改为 \sqrt n 级别的，因为会有负坐标，所以整体要加上一个 \sqrt n 的偏移量，时空复杂度均为 O(n^4)，常数约为 12。

如果时限为 1s，现在的时间复杂度足矣通过，可是该题时限为 700ms，而且常数相当大，还得优化。发现状态表示的是 0/1，可以加上 bitset，这样一来就可以通过该题了。

时间复杂度 O(\frac {n^4} w)。

Code：

无滚动数组：10.99s/246.03MB

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=1e2+7,maxm=30; //2*sqrt(n)
int n,m,p,q,lmt;
int a[maxn][maxm];
bitset<maxm> f[maxn][maxn][maxn][maxm]; //bitset优化

signed main(){
    srand(time(0));
    scanf("%lld%lld",&n,&m),lmt=sqrt(n)+3;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=12;j++) scanf("%lld",&a[i][j]);
    }
    random_shuffle(a+1,a+1+n); //随机排序
    scanf("%lld%lld",&p,&q),f[0][0][0][lmt][lmt]=1;
    for(int i=1;i<=n;i++){
        for(int l=0;l<m;l++){
            for(int r=0;r<m;r++){
                for(int x=0;x<=lmt<<1;x++){
                    //分别转移六个方向
                    f[i][l][r][x]|=f[i-1][(l-a[i][1]+m)%m][(r-a[i][2]+m)%m][x]<<1; //左移一位相当于y-1
                    f[i][l][r][x]|=f[i-1][(l-a[i][3]+m)%m][(r-a[i][4]+m)%m][x+1]; //y不变
                    f[i][l][r][x]|=f[i-1][(l-a[i][5]+m)%m][(r-a[i][6]+m)%m][x+1]>>1; //右移一位相当于y+1
                    f[i][l][r][x]|=f[i-1][(l-a[i][7]+m)%m][(r-a[i][8]+m)%m][x]>>1;
                    f[i][l][r][x]|=f[i-1][(l-a[i][9]+m)%m][(r-a[i][10]+m)%m][x-1];
                    f[i][l][r][x]|=f[i-1][(l-a[i][11]+m)%m][(r-a[i][12]+m)%m][x-1]<<1;
                }
            }
        }
    }
    if(f[n][p][q][lmt][lmt]) printf("Chaotic Evil");
    else printf("Not a true problem setter");
    return 0;
}

滚动数组：5.05s/6.44MB

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=1e2+7,maxm=30;
int n,m,p,q,lmt;
int a[maxn][maxm];
bitset<maxm> f[2][maxn][maxn][maxm];

signed main(){
    srand(time(0));
    scanf("%lld%lld",&n,&m),lmt=sqrt(n)+3;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=12;j++) scanf("%lld",&a[i][j]);
    }
    random_shuffle(a+1,a+1+n);
    scanf("%lld%lld",&p,&q),f[0][0][0][lmt][lmt]=1;
    for(int i=1;i<=n;i++){
        for(int l=0;l<m;l++){
            for(int r=0;r<m;r++){
                for(int x=0;x<=lmt<<1;x++){
                    f[i&1][l][r][x].reset();
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][1]+m)%m][(r-a[i][2]+m)%m][x]<<1;
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][3]+m)%m][(r-a[i][4]+m)%m][x+1];
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][5]+m)%m][(r-a[i][6]+m)%m][x+1]>>1;
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][7]+m)%m][(r-a[i][8]+m)%m][x]>>1;
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][9]+m)%m][(r-a[i][10]+m)%m][x-1];
                    f[i&1][l][r][x]|=f[i-1&1][(l-a[i][11]+m)%m][(r-a[i][12]+m)%m][x-1]<<1;
                }
            }
        }
    }
    if(f[n&1][p][q][lmt][lmt]) printf("Chaotic Evil");
    else printf("Not a true problem setter");
    return 0;
}