当前位置: 首页 > news >正文

忻州网站建设公司企业网站设计文档

忻州网站建设公司,企业网站设计文档,seo网站设计费用,专业网站发展趋势题干#xff1a; 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 给定一个长度为N的数组A1, A2, ... AN#xff0c;请你判断其中有几个元素Ai按如下跳跃规则能跳到最后一个元素AN。 假设你当前位于Ai#xff0c;跳跃的规则是#xff1a; 如果这一步是第奇…题干 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 给定一个长度为N的数组A1, A2, ... AN请你判断其中有几个元素Ai按如下跳跃规则能跳到最后一个元素AN。   假设你当前位于Ai跳跃的规则是 如果这一步是第奇数次跳跃(从1开始计数)可以跳到Ai之后(Ai1 .. AN)比Ai大的最小的元素 如果这一步是第偶数次跳跃可以跳到Ai之后(Ai1 .. AN)比Ai小的最大的元素 如果有多个满足条件的元素则跳到其中下标最小的元素。   如果没有满足条件的元素则在当前的Ai停下来。   例如对于A [3, 2, 4, 1, 5]如果从3开始第一步从3跳到4第二步从4跳到1第三步从1跳到5。 输入 第一行包含一个整数N。   第二行包含N个整数A1, A2, ... AN。   对于30%的数据1 N 100   对于60%的数据1 N 1000   对于100%的数据1 N 100000  1 Ai  1000000 输出 一个整数代表答案 样例输入 5 3 4 1 2 5 样例输出 4 解题报告 先用set倒着扫一遍数组顺便预处理出距离最近的比他大的最小的数的下标和距离最近的比他小的最大的数的下标这一步可以用单调栈O(n)实现但是因为时间允许于是set好写一些。然后dp代表从编号i开始的第偶数/奇数步能不能到达最后。 AC代码 #includecstdio #includeiostream #includealgorithm #includequeue #includemap #includevector #includeset #includestring #includecmath #includecstring #includecctype #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX 2e6 5; setint ss; bool dp[MAX][2]; int big[MAX],small[MAX],pos[MAX],a[MAX];//预处理出后面第一个比他大的和第一个比他小的 int main() {int n;cinn;for(int i 1; in; i) scanf(%d,ai);for(int i n; i1; i--) {if(ss.count(a[i])) pos[a[i]] i;else ss.insert(a[i]),pos[a[i]] i;auto it ss.upper_bound(a[i]);if(it ! ss.end()) big[i] pos[*it];else big[i] -1;it ss.lower_bound(a[i]);if(it ss.begin()) small[i] -1;else {--it;small[i] pos[*it];}} // for(int i 1; in; i ) { // printf(i: %d : %d %d\n,i,big[i],small[i]); // }dp[n][0] 1,dp[n][1] 1;for(int i n-1; i1; i--) {if(big[i] ! -1) dp[i][1] dp[big[i]][0];if(small[i] ! -1) dp[i][0] dp[small[i]][1];}int ans 0;for(int i 1; in; i) {if(dp[i][1]) ans;}printf(%d\n,ans);return 0 ;} 注意因为题中的大于和小于都是严格大于和严格小于所以判断大于必须用upper否则可能set中已经有一个a[i]了你再lower就肯定不对了。 同样的也可以用map实现 #include bits/stdc.h using namespace std; const int N 1e555; int dp[N][2]; int a[N]; int main() {int n;cinn;for(int i1;in;i)cina[i];mapint,int mp;mapint,int ::iterator it;mp[a[n]] n;dp[n][1] 1;dp[n][0] 1;for(int in-1;i0;--i){it mp.lower_bound(a[i]);if(itmp.end()||itmp.begin()) dp[i][0] 0;else dp[i][0] dp[(--it)-second][1];it mp.upper_bound(a[i]);if(itmp.end()) dp[i][1] 0;else dp[i][1] dp[it-second][0];mp[a[i]]i;}int ans 0;for(int i1;in;i){if(dp[i][1]) ans;}coutans;return 0; }
http://wiki.neutronadmin.com/news/243470/

相关文章:

  • wordpress4.8.2下载长沙官网seo诊断
  • 多语言网站(如何实现网站的多语言版本 )大学生网站设计作品
  • 网站开发c谷歌 网站做推广
  • 网站服务器是主机吗厦门网站建设和人才库建设
  • 手表网站海马300米潜水表编程培训机构排名
  • 免费网站建设新技术176网站入口
  • 公司想建个网站怎么弄wordpress进销存插件
  • aqq网站开发菲律宾
  • 海珠区建网站公司域名查询官方网站
  • 做阿里国际网站要收费吗wordpress更新慢
  • 安阳网站制作价格东莞哪里有网页设计
  • 南京网站建设制作wordpress 英文 企业网站模板
  • 上海网站外包建设小米发布会13
  • 我的世界封面制作网站高性能网站建设指南 书
  • 网站的前端和后端wordpress分类目录seo
  • 软件开发模式有哪些kj6699的seo综合查询
  • 廊坊网站建设推广经验eclipse可以做门户网站嘛
  • 网站备案包括做空气开关那个网站推广比较好
  • 肇庆网站开发建立自信
  • 免费建微网站深圳外贸网站建设口报关
  • 如何知道网站是否备案过佛山外贸网站建设方案
  • 做网站网站犯法吗wordpress主题安装完后前台打不开
  • 专业的手机网站建设公司免费高清视频软件
  • 如何做国际贸易网站零食店网站构建策划报告
  • 互联网客户做网站网站建设服务的会计处理
  • 免费黄页营销网站网站开发高级工程师
  • 东莞微网站建设费用有没有一个网站做黄油视频
  • 哪些网站平台可以做推广wordpress国内不使用方法
  • 个人做网站租云服务器最近播放中文版在线观看电视剧
  • 合肥市建设工程市场价格信息网站中国500强企业