博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[DFS]JZOJ 4208 线段树什么的最讨厌了qwq
阅读量:6196 次
发布时间:2019-06-21

本文共 1310 字,大约阅读时间需要 4 分钟。

Description

小Y 最近学习了线段树,但是由于她的智商比较低,运用的还不是很熟练。于是小R 给了她一点练习题训练,其中有一道是这样的。
这是小R 写的线段树的一段建树代码:
只要调用buildtree(1,0,n) 就可以得到一颗线段树了。显然,一颗线段树一共有O(n) 个节点,因为每一个节点都代表了一个不同的区间,所以线段树上一共出现了O(n) 个不同的区间。
现在小R 给了你一个区间[l; r],他想要你告诉他一个最小的n 使得区间[l; r] 出现在了用buildtree(1,0,n) 建出来的线段树中。
 

Input

第一行输入一个正整数T 表示数据组数。
接下来T 行每行三个整数L;R; lim 表示一组询问,如果对于所有的0 <= n <= lim 都不存在满足条件的解,输出-1 即可。

Output

对于每组询问输出一个答案。
 

Sample Input

2 0 5 10 6 7 10

Sample Output

5 7
 

Data Constraint

分析

水题

通过小区间往上扩展即可,四种扩展方法

然后有很多奇奇怪怪的特判,lim要取lim和l+r的最小值

 

#include 
#include
#include
using namespace std;typedef long long ll;int T;ll l,r,limit,ans;void DFS(ll l,ll r) { if (l<0||r>limit||r>ans&&ans!=-1) return; if (l==0) { if (ans==-1) ans=r; else ans=min(ans,r); return; } DFS(l,r*2-l);DFS(l,r*2+1-l); DFS(2*(l-1)-r,r);DFS(2*(l-1)-r+1,r);}int main() { for (scanf("%d",&T);T;T--) { scanf("%d%d%d",&l,&r,&limit); if (l==0&&r<=limit||l==r) printf("%lld\n",r); else { if (r>limit) { printf("-1\n"); continue; } limit=min(limit,l+r); ans=-1; DFS(l,r); printf("%d\n",ans); } }}
View Code

 

转载于:https://www.cnblogs.com/mastervan/p/10300826.html

你可能感兴趣的文章
敏捷之道Scrum篇
查看>>
微软的IE中调试JavaScript的工具下载链接
查看>>
设计思维与协作文化
查看>>
虚函数和多态
查看>>
POJ-1011 Sticks
查看>>
Linux系统的启动过程(转)
查看>>
Visual Studio添加dll程序集引用操作步骤
查看>>
Linux系统VNC配置实践总结
查看>>
匿名函数的代码模式
查看>>
swat主流域文件(file.cio)参数详解——引自http://blog.sciencenet.cn/blog-922140-710636.html...
查看>>
马云成功的九大秘籍--这个真的值得学学!
查看>>
IE6不支持CSS的属性选择器
查看>>
怎么让一个div 悬浮在另一个div上
查看>>
回溯法 子集树和排序树
查看>>
根级别上的数据无效。 行 1,位置 1
查看>>
[Unity2D]实现背景的移动
查看>>
5天学会jaxws-webservice编程第一天
查看>>
不常用但很有用的git show 和 git blame
查看>>
SQLLoader2(导入EXCEL或csv格式的文件)
查看>>
微信公众平台开发(105) 分享到朋友圈和发送给好友
查看>>