题目链接
题目分数:2400
题目描述
输入$T(≤1e5)$表示$T$组数据。所有数据的$n$之和$≤3e5$。每组数据输入$n(2≤n≤3e5)$和长为$n$ 的数组a(O<a[i]≤1e9),下标从0开始。构造一个严格单调递增的,元素范围在$[0,n-1]$的下标数组id。要求id中的所有相邻元素i和j,都满足$a[i]XOR j<a[i] XOR i$。例如$a=[5,2,4,3,1]$,构造$id=[1,2,4]$,满足$a[1]XOR 2<a[2]XOR 1$以及$a[2]XOR 4<a[4]XOR 2$。输出id的最大长度。
样例
输入样例1
3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3
输出样例1
2
3
6
算法
(数位枚举+map) $O(30*n)$
这道题目看起来很像单调上升子序列模型,但是有异或条件,所以不能直接做。那么熟悉异或的朋友们都知道,如果这个式子是等式的话,那么两边都可以异或上$i*j$,这样式子就变成了w[i]^i=w[j]^j,但是可惜是大于号,那么就没有这个性质了。那么我们想一个数怎么样才会大于另一个数呢?在二进制下,一个数大于另一个数,必定是在第$k$位之前,都相等,在第$k$位时,第一个数大于第二个数。
那么在这道题中,想法类似,我们可以枚举位数$k$,表示前$(k+1)$位相等为$g$,在第$k$位时当前的数大于另一个数。那么在看前$(k+1)$位时,两边相等,所以可以直接像上面一样化简,这样就简化了题目。我们用$f[k][g][p][q]$表示当前枚举到第$k$位,前$(k+1)$位是$g$,$p$是当前元素第$k$位$(0或1)$,$q$是当前下标第$k$位$(0或1)$。我们在枚举第$k$位时,g = (w[ i ] ^ i)>>(k + 1),但是通过题目给的公式我们如果想让不等式成立,那么当前第$k$位$w[i]$与$j$应该是相反的,$w[j]$和$i$是相同的。等枚举完后,在更新$f$。
但是这道题我用$map$时反复被卡,最后只能使用$trie$树,使用$trie$就比较简单了,因为$trie$自带大小关系,我们只需要从大到小枚举,就可以维护前$(k+1)$相等这个关系。最后我用$memset$时在$test11$也被卡了,无奈只能将数组开大,每次将起始点换成上一次的值$+1$.
C++ 代码
// 我用map被卡了,memset用也被卡了,这里用的trie树
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 3e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int tr[N*31][2];
int f[N*31][2][2];
int idx;
void solve()
{
scanf("%d", &n);
int res = 0;
int start = idx + 1;
idx++;
for(int i=0;i<n;i++){
int u;
scanf("%d", &u);
int maxn = 0, p = start;
for(int j=29;~j;j--){
int t = (u^i) >> (j+1) & 1;
if(!tr[p][t]) break;
maxn = max(maxn, f[tr[p][t]][i>>j&1][(u>>j&1)^1]);
p = tr[p][t];
}
maxn++;
res = max(res, maxn);
p = start;
for(int j=29;~j;j--){
int t = (u^i) >> (j+1) & 1;
if(!tr[p][t]) tr[p][t]=++idx;
auto &o = f[tr[p][t]][u>>j&1][i>>j&1];
o = max(o, maxn);
p = tr[p][t];
}
}
printf("%d\n", res);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
solve();
}
return 0;
}
想问问主页写的灵神是谁,能给个链接吗
灵茶山艾府 b站链接 https://space.bilibili.com/206214/?spm_id_from=333.999.0.0