首页 > 代码库 > 求序列完美度(trie+贪心)
求序列完美度(trie+贪心)
题目链接：
求序列完美度
题目描述
给出由n个数组成的序列s，规定第i个数s[i]到第j个数s[j]组成的子序列的完美度为该子序列中所有数的和与任意一个不在该子序列中的数进行异或运算得到的值中的最大值，即perfect(s[i]~s[j])=max(sum(s[i]~s[j])^x)，x为非子序列的数。现求完美度最大的子序列与它的完美度是多少
输入
第一行输入一个数T表示共有T组数据
输入一个数n表示序列有n个数
接下来有n个数，角标为1-n，表示序列的组成
1<=T<=100
3<=n<=1000
0<=s[i]<=1000000
输出
输出四个数:i,j,x,perfect[s[i]~s[j]],分别表示完美度最大的子序列的左端点(1<=i<=n)，右端点(i<=j<=n)，x(参见题目描述)和序列的完美度(如有多组子序列完美度相同，输出左端点靠前的，若左端点相同输出右端点靠前的)
样例输入
2
3
1 2 3
3
1 3 2
样例输出
2 3 1 4 1 2 2 6
题意：
思路：一个trie树，然后贪心就行，感觉题目描述有问题，还有数据范围有问题，看代码就知道了;
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,a[maxn];
struct node
{
int l,r,x,mx;
}ans;
int ch[maxn*30][2],sz,val[maxn*30],vis[maxn*maxn];
void insert(int x)
{
int u=0;
for(int i=29;i>=0;i--)
{
int c=((x>>i)&1);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
val[u]++;
}
}
inline void del(int x)
{
int u=0;
for(int i=29;i>=0;i--)
{
int c=((x>>i)&1);
u=ch[u][c];
val[u]--;
}
}
int get_ans(int x)
{
int u=0,tep=0;
for(int i=29;i>=0;i--)
{
int c=(((x>>i)&1)^1);
if(val[ch[u][c]])u=ch[u][c],tep|=(1<<i);
else u=ch[u][c^1];
}
return tep;
}
inline void init()
{
sz=1;memset(ch[0],0,sizeof(ch[0]));
for(int i=1;i<=n;i++)insert(a[i]);
}
inline void solve(int p)
{
init();
int sum=0;
for(int i=p;i<=n;i++)
{
del(a[i]);
sum+=a[i];
int g=get_ans(sum);
if(g>ans.mx)ans.mx=g,ans.l=p,ans.r=i,ans.x=sum^g;
else if(g==ans.mx)
{
if(p<ans.l)ans.l=p,ans.r=i,ans.x=sum^g;
else if(p==ans.l&&i<ans.r)ans.r=i,ans.x=sum^g;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
ans.mx=-1;
for(int i=1;i<=n;i++)solve(i);
printf("%d %d %d %d\n",ans.l,ans.r,ans.x,ans.mx);
}
return 0;
}
求序列完美度(trie+贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。