一道字典树异或的题,但是数据比较水,被大家用暴力给干掉了!
以前写过一个类似的题,叫做the longest xor in tree;
两个差不多吧!
好久没写字典树了,复习一下!
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
using namespace std;
int n,v[maxn],node,next[maxn][],end[maxn]; void add(int cur,int k)
{
memset(next[node],,sizeof(next[node]));
end[node]=;
next[cur][k]=node++;
} int cal(int x)
{
int i,k,cur=;
for(i=;i>=;i--)
{
k=((<<i)&x)?:;
if(next[cur][k]) cur=next[cur][k];
else cur=next[cur][-k];
}
return (x^end[cur]);
} int main()
{
int k,x,cur,ans,cp;
while(!scanf("%d%d",&n,&cp)!=EOF)
{
node=,ans=;
memset(next[],,sizeof(next[]));
for(int i=;i<n;i++)
{
scanf("%d",&x);
v[i]=x;
cur=;
for(int j=;j>=;j--)
{
k=((<<j)&x)?:;
if(next[cur][k]==) add(cur,k);
cur=next[cur][k];
}
end[cur]=x;
}
for(int i=;i<n;i++)ans=max(ans,cal(v[i]));
if(ans>cp)puts("YES");
else puts("NO");
}
return ;
}
另一种写法:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std; struct node
{
node *p[];
} no[maxn];
int w[],nocount; node *newnode()
{
node *v=no+nocount++;
for(int i=;i<;i++)v->p[i]=NULL;
return v;
} void insert()
{
node *nono=no;
for(int i=;i>=;i--)
{
if(nono->p[w[i]]==NULL)
nono->p[w[i]]=newnode();
nono=nono->p[w[i]];
}
} int cal()
{
int ans=;
node *nono=no;
for(int i=;i>=;i--)
{
if(nono->p[-w[i]]!=NULL){ans+=(<<i);nono=nono->p[-w[i]];}
else if(nono->p[w[i]]!=NULL){nono=nono->p[w[i]];}
}
return ans;
} int main()
{
int n,m,x;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(no,,sizeof no);
nocount=;
int mm=;
for(int i=; i<n; i++)
{
scanf("%d",&x);
for(int i=;i<;i++){w[i]=x%,x>>=;}
if(i!=)mm=max(mm,cal());
insert();
}
if(mm>m)puts("YES");
else puts("NO");
}
return ;
}
csu 10月 月赛 F 题 ZZY and his little friends的更多相关文章
-
csu 10月 月赛 I 题 The Contest
Description 殷犇有很多队员.他们都认为自己是最强的,于是,一场比赛开始了~ 于是安叔主办了一场比赛,比赛有n个题目,每个题目都有一个价值Pi和相对能力消耗Wi,但是有些题目因为太坑不能同时 ...
-
csu 10月 月赛 H 题 A Very Hard Problem
Description CX老湿经常被人黑,被黑得多了,自己也就麻木了.于是经常听到有人黑他,他都会深情地说一句:禽兽啊! 一天CX老湿突发奇想,给大家出了一个难题,并且声称谁能够准确地回答出问题才能 ...
-
csu 10月 月赛 J 题
Description CSU又到了一年中评奖学金的时候了……各大学霸都或多或少地拿到了各种奖学金(你们自己看着办吧). 在这里,评奖学金有个很奇怪的规矩——每个同学得到的奖学金数一定满足相邻的两个非 ...
-
csu 10月 月赛 D 题 CX and girls
Description CX是要赶去上课,为了不迟到必须要以最短的路径到达教室,同时CX希望经过的路上能看到的学妹越多越好.现在把地图抽象成一个无向图,CX从1点出发,教室在N号点,告诉每个点上学妹的 ...
-
csu 10月 月赛 B 题 Scoop water
一个卡特兰数的应用: 卡特兰数主要有以下几个用途: 1.不同的出栈入栈数: 2.n个点组成的不同的二叉树的数目: 3.凸多边形的三角剖分划分: 4.括号化问题: 通项公式是:h(n) = C(2n-2 ...
-
csu 10月 月赛 A 题
Welcome to CSU OnlineJudge Problem A: Small change Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 15 ...
-
Contest2037 - CSU Monthly 2013 Oct(中南大学2013年10月月赛水题部分题解)
Problem A: Small change 题解:http://www.cnblogs.com/crazyapple/p/3349469.html Problem B: Scoop water 题 ...
-
【LGR-054】洛谷10月月赛II
[LGR-054]洛谷10月月赛II luogu 成功咕掉Codeforces Round #517的后果就是,我\(\mbox{T4}\)依旧没有写出来.\(\mbox{GG}\) . 浏览器 \( ...
-
ECNU 2018 10月月赛 E 盖房子 (bitset + 倍增)
题目链接 ECNU Monthly 2018.10 Problem E 从开场写到结束…… 显然要把三角形分成上下两部分. 把每一部分分成三部分,以上部分为例. 上面和右边,以及左下角的正方形. 也 ...
随机推荐
-
Arcgis与CityEngine安装破解
Arcgis与CityEngine共存,实现同时破解 作为一个GIS背景的技术人员,以前安装了无数次的Arcgis DeskTop,到了新公司后,今天主管让我学习下CityEngine,学渣的我之前没 ...
-
《Entity Framework 6 Recipes》中文翻译系列 (40) ------ 第七章 使用对象服务之从跟踪器中获取实体与从命令行生成模型(想解决EF第一次查询慢的,请阅读)
翻译的初衷以及为什么选择<Entity Framework 6 Recipes>来学习,请看本系列开篇 7-5 从跟踪器中获取实体 问题 你想创建一个扩展方法,从跟踪器中获取实体,用于数 ...
-
【转】SVN库的迁移
转载地址:http://blog.csdn.net/windone0109/article/details/2841294 SVN服务器由于硬盘空间不足,需要将其迁移到另外一台机器上,并且更换Repo ...
-
翻译:使用tbb实现特征检测的例子
A feature-detection example using the Intel® Threading Building Blocks flow graph By Michael V. (Int ...
-
【转】IOS开发资源汇总
转自:http://blog.csdn.net/favormm/article/details/6664970 如何用Facebook graphic api上传视频: http://develope ...
-
将 node.js 的数据保存到 mongo 数据库中
Mongo 数据库 安装 首先到 Mongo 的官方网站下载安装程序:http://www.mongodb.org/,我下载的文件名为:mongodb-win32-x86_64-2008plus-2. ...
-
dpdk-18.11开发库编译安装
简介 dpdk官网 安装 下载 点击下载地址,选择合适的版本下载.这里下载DPDK 18.11.0 (LTS)版本. 编译 将下载的dpdk-18.11.tar.xz上传服务器,解压,这里放在了/op ...
-
Android (Android Studio)无法启动adb 解决方案
打开cmd 输入: netstat -aon|findstr "5037" 回车 taskkill /pid xxxx /f ps:xxxx为占用端口 ...
-
C#原生压缩和解压缩方法
string path = AppDomain.CurrentDomain.BaseDirectory; string startPath = @"c:\Client"; stri ...
-
istringstream和ostringstream的实现
ostringstream是将数据写入string里边的,istringstream是将从string里边读出数据的: #include <sstream> int main() { st ...