囧仙 的博客

囧仙 的博客

题解 P7264 【Mirror】

posted on 2021-01-10 22:45:51 | under 题解 |

由于出题人提供的题解的证明不甚清晰,于是打算自己写一篇题解谈一谈想法。

$\verb!upd 2021.1.10 23:14!$ 修正了一些笔误。管理审核太快了还没来得及勘误 $\verb!qwq!$

题目大意

  • 一个无穷大的矩阵,坐标为 $(x,y)$ 的格子可以通过当且仅当 $x\operatorname{and} y=0$ ,其中 $\operatorname{and}$ 是二进制下的与操作。

  • 现在矩阵上有 $n$ 个位置 $(x_i,y_i)$ 为炸弹。询问从 $(s_x,s_y)$ 到 $(t_x,t_y)$ 的最短路径上有哪些炸弹。

题解

通过大眼观察法,我们能够从题目中所给的 $64\times 64$ 的矩阵图上观察到这样两个很重要的结论:

  • 这张图形成了一个树形结构。也就是说,两点之间的路径唯一确定

  • 假使满足 $x>0,y>0$ 的点 $(x,y)$ 可以通过,那么 $(x-1,y)$ 和 $(x,y-1)$ 中有且仅有一个点可以通过。

我们先考虑第二个结论,因为根据这个结论可以反过来证明第一个结论。

事实上,假使 $x>0,y>0$ 的 $(x,y)$ 可以通过,那么 $x\operatorname{and} y=0$ 。于是对于不存在某个二进制位,使得 $x,y$ 的这一位同时相同。怎么样考虑 $x-1$ 后它的二进制值的变化呢?考虑 $x,y$ 的最右侧的为 $1$ 的位,因为减 $1$ 操作只会影响到这一位以及更低位的二进制值。不妨设 $x$ 最右侧的位是 $p$ , $y$ 最右侧的位是 $q$ ,其所对应的二进制位是 $2^p$ 和 $2^q$ 。显然, $p\neq q$ (不然 $x,y$ 的与值就不为 $0$ 了) 那么要么 $p<q$ ,要么 $p>q$ 。

当 $p<q$ 时, $2^p-1$ 的末尾 $p-1$ 位全部都是 $1$ ,并且不会影响到 $x$ 的 $p+1$ 位以后的数位。但是由于 $p<q$ ,于是这部分 $1$ 和 $y$ 的与值仍然为 $0$ ,于是 $(x-1) \operatorname{and} y=0$ ,于是 $(x-1,y)$ 可以通过。同时, $2^q-1$ 的末尾 $q-1$ 位全部都是 $1$ ,由于 $p<q$ ,于是此时 $x \operatorname{and} (y-1)\neq 1$ ,也就是 $(x,y-1)$ 不可通过

当 $p>q$ 时如法炮制,可以发现 $(x-1,y)$ 与 $(x,y-1)$ 中有且仅有一个可以通过。我们不妨将其与其左侧/上侧那个可达的点连边。

考虑第 $0$ 行和第 $0$ 列的数字。显然,除了 $(0,0)$ ,都可以向左侧或者上侧的点连边。于是所有点联通,并且边数是总点数 $-1$ 。这时已经满足整张图是树形结构这样的结论了。

下面考虑如何构造解法。事实上,在刚刚的论证过程中,我们提到了最低的为 $1$ 的位。我们可以用 $\operatorname{lowbit}$ 函数进行求值,其中 $\operatorname{lowbit}(x)$ 表示 $x$ 的最低位的 $1$ 对应的二进制数的值,并且 $\operatorname{lowbit}(x)=x\operatorname{and}(-x)$ (树状数组中也经常用到这个结论)。由于路径唯一,并且每个点只能向上或者向左走,我们可以考虑每个点每次走的时候最远走多少

我们先找出 $(s_x,s_y),(t_x,t_y)$ 如果分别向左上角走,最终会走到哪里(不妨设为 $(p_x,p_y)$ ) 。观察可得该图为一个分形,并且每一个子正方形的第 $0$ 行第 $0$ 列都是可通过的位置。于是从小到大枚举这个子正方形的边长 $2^k$ 。我们能够通过 $\left\lfloor\dfrac{s_x}{2^k}\right\rfloor,\left\lfloor\dfrac{s_y}{2^k}\right\rfloor$ 计算出 $(s_x,s_y)$ 所在的这个正方形是第几排第几个的正方形。只要判断起点和终点是否在同一个正方形中就行了,可以计算出 $(p_x,p_y)$ 。由于是一个子图,我们可以将刚刚出现过的所有坐标(包括起点终点和炸弹坐标)向左平移 $p_x$ 、向上平移 $p_y$ ,于是起点和终点最终应当在第 $0$ 行或者第 $0$ 列会合了。

假设当前点在 $(x,y)$ ,满足 $x\neq 0$ 且 $y \neq 0$ 。考虑每次向左或者向上走尽可能远的距离。同样,我们求出 $x,y$ 的最低位 $p,q$ 。不妨设 $p<q$ ,那么该点可以不停向左走。什么时候这个点要改变方向了呢?

不妨举个例子:

$$\begin{aligned} x&=554_{(10)}&=1000101010_{(2)} \cr y&=336_{(10)}&=0101010000_{(2)} \cr \end{aligned}$$

显然,由于 $p<q$ ,我们要不断减去 $x$ 的值,也就是向上走。可以发现,对于 $x$ 的后 $q$ 位,无论它的值如何,与上 $y$ 都是 $0$ 。那么也就是说,我们要不断减去这后 $q$ 位,直到他们全部为 $0$ 。

$$\begin{aligned} x&=544_{(10)}&=1000100000_{(2)} \cr y&=336_{(10)}&=0101010000_{(2)} \cr \end{aligned}$$

此时 $p,q$ 的大小关系就对调了。于是我们应当向左走了。这一部分一共花费了 $554-544=10$ 步。

可以证明,全过程中走的步数不会超过 $\log_2(x+y)$ 。因为每走一段路, $x$ 或 $y$ 的 $\operatorname{lowbit}$ 值至少加上 $1$ 。

然后这条路就被我们拆分成了 $\log_2(x+y)$ 个线段。分别对 $(s_x,s_y),(t_x,t_y)$ 执行这些操作,直到他们的横坐标或者列坐标到达了 $0$ 。

考虑最后一步。事实上我们要考虑他们会不会在 $(0,0)$ 相遇,而这取决于他们是否在同一行或者同一列上了。这部分只需要判断一下,留给读者自几处理

那么最后线段总数应该是 $\log_2v$ 级别的( $v$ 是值域)。对于每个炸弹,枚举所有线段,判断这个炸弹是否在这条线段上。总复杂度 $\mathcal O(n\log v)$ 。由于不像题解中用到比较麻烦的递归,所以速度飞起,拿到了赛时最块。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN =2e5+3,MAXM=500+3;
i64 n,X[MAXN],Y[MAXN],s1,s2,t1,t2,ans;
i64 A[MAXM],B[MAXM],C[MAXM],p;
i64 P[MAXM],Q[MAXM],R[MAXM],q;
void del(i64 &x,i64 &y){
    while(x!=0&&y!=0){
        if(!((x-1)&y)){i64 t=y&-y,l=x&(t-1); A[++p]=y,B[p]=x-l,C[p]=x,x-=l,ans+=l;}
        else          {i64 t=x&-x,l=y&(t-1); P[++q]=x,Q[q]=y-l,R[q]=y,y-=l,ans+=l;}
    }
}
i64 qread(){
    i64 w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int main(){
    n=qread(); up(1,n,i) X[i]=qread(),Y[i]=qread();
    s1=qread(),s2=qread(),t1=qread(),t2=qread();
    up(1,60,i){
        i64 l=1ll<<i,a1=s1/l,a2=s2/l,b1=t1/l,b2=t2/l,p1,p2;
        if(a1==b1&&a2==b2){
            p1=a1*l,p2=a2*l,s1-=p1,s2-=p2,t1-=p1,t2-=p2;
            up(1,n,j) X[j]-=p1,Y[j]-=p2; break;
        }
    }
    del(s1,s2),del(t1,t2);
    printf("%lld\n",ans+llabs(s1-t1)+llabs(s2-t2));
    P[++q]=min(s1,t1),Q[q]=min(s2,t2),R[q]=max(s2,t2);
    A[++p]=min(s2,t2),B[p]=min(s1,t1),C[p]=max(s1,t1);
    up(1,n,i){
        bool f=0;
        up(1,p,j) if(Y[i]==A[j]&&X[i]>=B[j]&&X[i]<=C[j]) f=true;
        up(1,q,j) if(X[i]==P[j]&&Y[i]>=Q[j]&&Y[i]<=R[j]) f=true;
        putchar(f?'1':'0');
    }
    return 0;
}