福州大学算法作业题 - 最长子串
程序员文章站
2022-10-16 17:00:13
★实验任务 ★数据输入 ★数据输出 ★数据范围 代码1: 代码2: 代码3: ......
★实验任务
给你一个长度为 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; }
下一篇: 霍金警告:人类正处于最危险的时候