3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二

时间:2022-11-01 18:53:43

3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 21  Solved: 18
[Submit][Status][Discuss]

Description

    洞窟里有一道长长的通道.它由N(1≤N≤25000)段道尾相连构成,编号分别为1到N.每个通道有一个阈值,其范围在[1,10^9]依次通过i..j的通道,那奶牛的体重指数就不能超过i..j通道中阈值的最小值.贝茜有Q(1≤Q≤25000)个问题,想请教你由i到j的通道的阈值的最小值.

Input

    第1行输入N和Q,接下来N行输入每个通道的阈值,之后Q行每行两个整数,对应问题中的i和j(i<j).

Output

   对于每个问题,输出其结果.

Sample Input

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

Sample Output

5
38
20
5

HINT

 

Source

Orange

题解:RMQ模板题。。。感觉自己水水哒

 /**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
i,j,k,l,m,n,h:longint;
a:array[..,..] of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
begin
readln(n,m);
h:=trunc(ln(n)/ln()+);
for i:= to n do readln(a[i,]);
for i:= to h do
for j:= to n-trunc(exp(ln()*i))+ do
a[j,i]:=min(a[j,i-],a[j+trunc(exp(ln()*(i-))),i-]); for i:= to m do
begin
readln(j,k);
l:=trunc(ln(k-j+)/ln());
writeln(min(a[j,l],a[k-trunc(exp(ln()*l))+,l]));
end;
readln;
end.

3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二的更多相关文章

  1. bzoj3381&lbrack;Usaco2004 Open&rsqb;Cave Cows 2 洞穴里的牛之二&ast;

    bzoj3381[Usaco2004 Open]Cave Cows 2 洞穴里的牛之二 题意: RMQ问题.序列长度≤25000,问题数≤25000. 题解: 倍增. 代码: #include &lt ...

  2. P3381&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 2 洞穴里的牛之二

    这题..思维上远没有上一题复杂,是一个裸的RMQ..利用倍增就可以解决了. var n,q,i,j,f,t,c:longint; a:array[..,..] of longint; function ...

  3. Bzoj 3380&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 1 洞穴里的牛之一

    3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 64  Solved ...

  4. bzoj3383&lbrack;Usaco2004 Open&rsqb;Cave Cows 4 洞穴里的牛之四&ast;

    bzoj3383[Usaco2004 Open]Cave Cows 4 洞穴里的牛之四 题意: 平面直角坐标系有n个点,从(0,0)出发,从一个点上可以跳到所有与它横纵坐标距离都≤2的点上,求最少步数 ...

  5. &lbrack;BZOJ3380&rsqb; &lbrack;USACO2004 Open&rsqb;Cave Cows 1 洞穴里的牛之一

    Description ​ 很少人知道其实奶牛非常喜欢到洞穴里面去探险. ​ 洞窟里有N(1≤N≤100)个洞室,由M(1≤M≤1000)条双向通道连接着它们.每对洞室间 至多只有一条双向通道.有K( ...

  6. P3380&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 1 洞穴里的牛之一

    还是蛮简单的一道题,首先dfs一遍,在所有能到达放有干草的洞穴的所有路径中,找出路径上最小伐值的最大值,按这个值由小到大,再来一遍贪心就行了,能放就放,不能放拉倒(也可以理解为,不能放把最前一个删了) ...

  7. bzoj3380&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 1 洞穴里的牛之一&lpar;spfa&plus;状压DP&rpar;

    数据最多14个有宝藏的地方,所以可以想到用状压dp 可以先预处理出每个i到j的路径中最小权值的最大值dis[i][j] 本来想用Floyd写,无奈太弱调不出来..后来改用spfa 然后进行dp,这基本 ...

  8. P3383&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 4 洞穴里的牛之四

    这个系列总算是做完了,这是我第一次高效率做完四道题,虽然中间有两道水题,但是第一和第四题还是蛮好的,但是只要能想到思路就很快能打完的. 像这道题,刚开始在想能不能用DP?但是苦于不知道怎么实施,后来又 ...

  9. P3382&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 3 洞穴里的牛之三

    首先,我们先确定,最长的曼哈顿距离只可能为 x1+y2-(x2+y2) 和 x1-y1-(x2-y2) 所以我们只需要维护四个值, 分别代表 max(x+y) ; max(x-y) ; min(x+y ...

随机推荐

  1. Entity Framework中IQueryable&comma; IEnumerable&comma; IList的区别

    博客园里有这样的总结.这里姑且先列个题目, 提醒自己记忆.

  2. Bootstrap的宽度和分辨率的差别

    首先在bootstrap里面所有的样式并在pc上是根据px的单位来判断的,就是我们说的分辨率, @media(min-width:1200px){ ......里面的样式 } 那么就是说当你的屏幕放大 ...

  3. POJ 2289 Jamie&&num;39&semi;s Contact Groups

    二分答案+网络最大流 #include<cstdio> #include<cstring> #include<cmath> #include<vector&g ...

  4. JavaWeb的国际化(17&sol;4&sol;8)

      国际化的缺点: 因为文字不同,所以带来的排版问题一样严重,通常都是重新在写一个网站反而更加清晰,快捷 1:需要从浏览器中获取到浏览器语言(Accept-Language) 2:利用locale获取 ...

  5. Java学习笔记8(面向对象一:概念、private)

    面向过程的思想:遇到问题,想,我该怎么解决这个问题?然后一步一步解决 面向对象的思想:遇到一件事的时候,思考,我该让谁来做,至于他怎样去做,不是我需要考虑的事情,只要最后做好就行 实际举例:我们要组装 ...

  6. JFinal WEB MVC和Struts简要对比

    JFinal遵循COC原则,零配置,无xml,而struts需要配置来支持action.result.interceptor配置与使用. JFinal开发效率非常之高,相对Struts开发效率能提升五 ...

  7. 向linux服务器上传下载文件方式收集

    向linux服务器上传下载文件方式收集 1. scp [优点]简单方便,安全可靠:支持限速参数[缺点]不支持排除目录[用法] scp就是secure copy,是用来进行远程文件拷贝的.数据传输使用 ...

  8. 腾讯云 服务器 ubuntu 16&period;04 python3 环境

    积分 - 164 排名 - 183650 首先把腾讯云上的服务器,重装系统,选择64位ubuntu16.04,最低配也要用64位的…… 装好后,首先切换 python 版本: sudo update- ...

  9. 视频支持拖动进度条播放的实现(基于nginx)

    http协议下的flv/mp4流式播放支持的三个要点: 1 服务器端要支持flv/mp4流式播放,现在nginx或者lighttpd都是支持这样的应用的,还支持mp4的流式播放(默认编译版本一般都是打 ...

  10. 咏南 DATASNAP LINUX中间件

    咏南 DATASNAP LINUX中间件,一套源码,同时支持WINDOWS和LINUX操作系统. 基于DELPHI 10.2 TOKYO开发 使用FIREDAC数据库引擎,支持MYSQL,MSSQL, ...