当前位置：首页 > news >正文

[题解]2024CCPC郑州站——Z-order Curve

news 2026/6/14 4:18:40

题目简介

题源：L. Z-order Curve | GYM
题意：对于如下Z曲线，给定曲线端点 \([L,R]\)，找出最小的 \(L^{'}\)，使得 \([L^{'},R^{'}-L+1]\) 与 \([L,R]\) 曲线形状相同。注意\([L,R]\)为有向线段。
数据范围：\(0\le L,R\le 10^{18}\)
关键词：递归，二进制(签到)

题解1:递归

观察可知Z曲线具有自相似性。每一个大小为\(2^k\)的大Z曲线，均由4个大小为\(2^{k-1}\)的小Z曲线拼接而成，我们称其分别为左上、右上、左下、右下。这天然启发我们使用递归求解。具体而言：

若 \([L,R]\) 位于同一层，则可通过取模，将其平移到位于左上角的小Z曲线中，同时向下一层递归；
否则，代表已找到能表示出该曲线形状的最小Z曲线，无法再继续分解。此时左端点即为答案。

观察到 \(R\le 10^{18}\)，使用换底公式求得其 \(<2^{60}\)，故直接从第60层向下递归。复杂度\(O(\log R)\)。

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
#define int i64
#define endl '\n'
int solve(int L,int R,int k) {int size=1LL<<k;if (L/size!=R/size) return L;return solve(L%size,R%size,k-1);
}
signed main() {ios::sync_with_stdio(0),cin.tie(0);int t;cin>>t;while (t--) {int l,r;cin>>l>>r;cout<<solve(l,r,60)<<endl;}return 0;
}