求序列完美度(trie+贪心)
2024-08-25 15:12:58
题目链接:
题目描述
给出由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;
}
最新文章
- 从源码浅析MVC的MvcRouteHandler、MvcHandler和MvcHttpHandler
- java中的内部类总结
- Resize Instance 操作详解 - 每天5分钟玩转 OpenStack(41)
- Effective Objective-C 2.0 — 第五条用枚举表示状态、选项、状态码 (未看完)
- code vs 1506 传话
- T-SQL 批处理
- 【vc】1_Windows程序内部运行机制
- javascript高级知识分析——上下文
- Java数据结构与算法(5) - ch05链表(LinkList)
- maven项目打包发布时跳过测试
- webpack2进阶之多文件,DLL,以及webpack-merge
- 大数据基础篇(一):联机分析处理(OLAP) 与 联机事务处理(OLTP)
- Codeforces Round #432 (Div. 1) B. Arpa and a list of numbers
- mysql 分组内 排序
- document.getElementById动态的Node集合随时变化, 和document.querySelector静态的后续无法变化
- tcp 三次握手 转
- Linux下安装jdk1.7
- SaaS的中年危机(转)
- EFCore中SQLSERVER 2008 的分页问题