您现在的位置是：主页 > news > 阿里服务器怎么做网站服务器吗/广告联盟官网入口

阿里服务器怎么做网站服务器吗/广告联盟官网入口

admin2025/6/8 4:08:34【news】

简介阿里服务器怎么做网站服务器吗,广告联盟官网入口,哪里有建设网站中的视频下载,php 做的应用网站2021杭电多校第一场 Xor sum 题目链接题意给定一个有n个元素的数组a和一个数值k。让你在a中找出一个连续的子序列（aLa_LaL—aRa_RaR），这个子序列需要满足所有元素的异或值不小于k，使得子序列的长度（R-L1&a…

阿里服务器怎么做网站服务器吗,广告联盟官网入口,哪里有建设网站中的视频下载,php 做的应用网站2021杭电多校第一场 Xor sum 题目链接题意给定一个有n个元素的数组a和一个数值k。让你在a中找出一个连续的子序列（aLa_LaL—aRa_RaR），这个子序列需要满足所有元素的异或值不小于k，使得子序列的长度（R-L1&a…

2021杭电多校第一场

Xor sum

题目链接

题意

给定一个有n个元素的数组a和一个数值k。

让你在a中找出一个连续的子序列（ $a_L$ — $a_R$ ），这个子序列需要满足所有元素的异或值不小于k，使得子序列的长度（R-L+1）最短。

如果存在多个最短的，找到L最靠前的（最靠近0）。

$1≤n≤105，0≤k≤230，0≤ai≤2301\le n \le 10^5，0 \le k \le 2^{30}，0 \le a_i \le 2^{30}$

思路

首先对a求前缀异或，得到新的数组pre，将问题转变成找出 $pre_i$ 和 $pre_j$ ( $j > i$ ) 使得 $pre_i \ 异或 \ pre_j) == k$ ，也可以是 $prei≥kpre_i \ge k$ 。

枚举 $a_R$ 向前搜，看是否满足条件，如果暴力搜肯定会炸，需要维护一个字典树来实现先前搜的复杂度为 $O(log_2^n)$ ，算上枚举的复杂度，总的复杂度就是 $O(nlog_2^n)$

下边详细说明一下如何维护字典树

首先，树上存储的字符串为 $pre_i$ 的2进制位。

以下面这组数据为例子，来进行分析。

1
9 7
3 1 3 2 4 0 3 5 1

k=7，二进制位为111。(我这边为了方便将二进制位的长度定义为3，注意数据给的范围是30)

从第一个点开始枚举， $a_1 = 3$ ，二进制位str="011"；需要让 $a_1$ 与某一个数x异或，使得得到的结果不小于k。

考虑是否能大于k，从最高位开始（如果最高位比k大，数值就一定比k大），str[0]与1异或会得到1，但是k的最高位也是1，所以这一位最大也只能相等，所以x二进制位的第一个一定是1，否则就一定小于k。

可以看出来，如果拿到一个数 $a_R$ ，从二进制位最高位开始遍历，就能确定 $a_i$ 需要满足的二进制位的前缀，可以通过字典树来维护这个这个前缀。

这时候字典树中没有存任何数据，所以无法找到满足条件的 $a_i$ 。

将 $a_1=$ 011存入字典树。
枚举第二个点， $a_2=1$ ，二进制位str="001"。定义一个cur表示当前位于哪个节点上，初始位置为根节点。

从二进制位的最高位开始判断，str[0]与1异或会得到1，k的最高位也是1，这一位无法大于k，在字典树中找0（左子树），能够找到，将cur移动到这个节点。

继续判断次高位，这一位需要是0，字典树上不存在这个节点，搜索停止。

将 $a_2=$ 001存入字典树。(这时需要刷新节点上的下标，因为要找离得最近的L和R)

在这里插入图片描述

后边重复同样的操作，先去字典树中搜索，然后将当前点存入字典树。

一些补充：

当k的某一位为0， $a_R$ 的该位与 $a_L$ 的该位异或为1时，后缀无论是什么，两个值异或的值一定大于k，不需要继续搜，直接更新答案。
需要判断一下等于k的情况，这时候二进制位搜索到了最后，特判一下。
需要判断当 $pre_i$ 大于k时的答案，可以先在字典树中存一个0，这样就不用特殊判断这种类型了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 3e6 + 10;
const int M = 30;
const ll inf = LLONG_MAX;
ll tot, res, res_l, res_r;
ll n, k;
ll a[N], pre[N];struct node {int l, r;// 左边表示0，右边表示1int id;
}trie[N];void update(int id) {int x = pre[id];int cur = 1;int i;for (i = M - 1; i >= 0 && cur != -1; i--) {if ((k >> i) & 1) {if ((x >> i) & 1) {cur = trie[cur].l;}else {cur = trie[cur].r;}}else {if ((x >> i) & 1) {if (trie[cur].l != -1) {if (id - trie[trie[cur].l].id < res) {res = id - trie[trie[cur].l].id;res_l = trie[trie[cur].l].id + 1;res_r = id;}}cur = trie[cur].r;}else {if (trie[cur].r != -1) {if (id - trie[trie[cur].r].id < res) {res = id - trie[trie[cur].r].id;res_l = trie[trie[cur].r].id + 1;res_r = id;}}cur = trie[cur].l;}}if (i == 0 && cur != -1) {if (id - trie[cur].id < res) {res = id - trie[cur].id;res_l = trie[cur].id + 1;res_r = id;}}}
}void add(int id) {int x = pre[id];int cur = 1;for (int i = M - 1; i >= 0; i--) {if ((x >> i) & 1) {if (trie[cur].r == -1) {// 不存在这条边，新建上trie[++tot].l = -1;trie[tot].r = -1;trie[tot].id = id;trie[cur].r = tot;}else {// 存在这条边，刷新id trie[trie[cur].r].id = id;}cur = trie[cur].r;}else {if (trie[cur].l == -1) {// 不存在这条边，新建上trie[++tot].l = -1;trie[tot].r = -1;trie[tot].id = id;trie[cur].l = tot;}else {// 存在这条边，刷新idtrie[trie[cur].l].id = id;}cur = trie[cur].l;}}
}void init() {res = inf;res_l = -1;res_r = -1;tot = 1;// 根节点设置为1trie[tot].l = -1;trie[tot].r = -1;add(0);// 加进去一个0
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.exceptions(ios::badbit | ios::failbit);int t;cin>>t;while (t--) {init();// 初始化字典树cin>>n>>k;for (int i = 1; i <= n; i++) {cin>>a[i];pre[i] = a[i] ^ pre[i - 1];// 计算前缀异或}for (int i = 1; i <= n; i++) {update(i);// 更新答案add(i);// 更新字典树}if (res == inf) {cout<<-1<<endl;}else {cout<<res_l<<" "<<res_r<<endl;}}return 0;
}