福州大学算法作业题 - 最长子串
2018-10-29 15:26:12来源:博客园 阅读 ()
★实验任务
给你一个长度为 N 的数组,现在需要求出异或和为零的最长连续子串。 一个子串的异或和指的是将子串中所有的数异或起来得到的值,比如给定 {1,1,2,2},异或和为零的连续子串有{1,1},{2,2},{1,1,2,2}。其中最长的连续 子串为{1,1,2,2}。
★数据输入
输入数据占两行,第一行输入一个正整数 N,第二行输入 N 个非负整数,任 意两个数之间由空格隔开。
★数据输出
输出三个整数 L、S、T 分别代表子串的长度以及子串的左右端点坐标(数组 下标从 1 开始),如果存在多解,则输出 S 值最小的解。 如果不存在这样的子串,则只需要输出一个-1。
★数据范围
50%的得分点,N<=100; 80%的得分点,N<=1000; 100%的得分点,N<=100000。 N 个整数取值范围在 int 范围内。
代码1:
#include <stdio.h> #include <map> using namespace std; int main(){ int n; scanf("%d", &n); int * a = new int[n]; int i; for(i=0;i<n;i++){ scanf("%d", &a[i]); } map<int,int> m; m[0] = -1; map<int , int>::iterator ite; int con = 0; int l=-1,s=1,t=1; int tl; for(i=0;i<n;i++){ con^=a[i]; ite = m.find(con); if( ite != m.end() ){ tl = i - ite->second; if(tl > l){ l = tl; s = ite->second+2; t = i+1; } }else{ m[con] = i; } } if(l == -1){ printf("%d", l); }else{ printf("%d %d %d", l, s, t); } return 0; }
代码2:
#include<iostream> #include<cstdio> #include<map> using namespace std; map<int,int> tag; int num[100005]; int main(){ int n,i,length,start,end; start = end =-1; length=-1; tag[0]=0; num[0]=0; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&num[i]); num[i]=num[i-1]^num[i]; if(tag.find(num[i])==tag.end()){ tag[num[i]]=i; } else{ if(i-tag[num[i]]>length){ length=i-tag[num[i]]; start=tag[num[i]]+1; end=i; } } } if(length==-1){ printf("%d\n",-1); } else{ printf("%d %d %d\n",length,start,end); } return 0; }
代码3:
#include<iostream> #include<map> #include<cstdio> using namespace std; int n, l=-1, s, e; int total = 0, tmp; map<int, int> m; int main(){ int i; scanf("%d", &n); for(i=1; i<=n; i++){ scanf("%d", &tmp); total = total ^ tmp; if(total == 0){ l = i; s = 1; e = i; } // 不为0就一直记录,为零单独考虑,存一个最开始total为0的节点 else{ if(m.find(total) == m.end()) m[total] = i; else{ if(i - m[total] > l){ l = i - m[total]; s = m[total] + 1; e = i; } } } } if(l > 0) printf("%d %d %d\n", l, s, e); else printf("-1\n"); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash