SG5. 数字序列
描述
一个由若干个取值范围在[1,2^31-1]的整数构成长度为N的数字序列，其中N<=5,000,000；求该数字序列上一段最小的连续区间的长度，要求该区间内正好包含了所有不同的数字，如果存在多个这样的区间，按照出现的顺序有序输出所有的区间起始和结束位置，序列的位置编号从1到N，其中最小的区间长度不会超过10,000。输入描述
第一行：N输出描述
第一行：最小的区间长度 区间个数X (以空格进行分隔）示例1
输入:
10 1 1 3 4 6 6 5 1 3 3
输出:
6 3 [2,7] [3,8] [4,9]
C++ 解法, 执行用时: 570ms, 内存消耗: 19960KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define endl "\n"
#define FIN freopen("1.txt","r",stdin)
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
inline int read() {char c;int ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
inline LL readl() {char c;LL ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
const int N = 5000010;
vector<int> s;
vector<int> t;
map<int,int> mp;
int ans = 100000;
int n,a[N];
int q;
int cnt = 0;
int tran[N];
int main()
{
n = read();
//mp.clear();mem(tran,0);
repn(i,1,n){
int &t = a[i];t = read();
if(mp.count(t)==0){
mp[t] = cnt;
t = cnt;
tran[cnt++]++;
}else{
t = mp[t];
tran[t]++;
}
}
int l = 1, r = n;
while(tran[a[r]]>1){
tran[a[r]]--;
r--;
}
while(1){
while(tran[a[l]]>1){tran[a[l]]--;l++;}
//cout<<l<<" "<<r<<endl;
if(ans==(r-l+1)){s.pb(l);t.pb(r);}
else if(ans>(r-l+1)){
s.clear();t.clear();
s.pb(l);t.pb(r);
ans = r-l+1;
}
q = a[l];
tran[a[l]]--;l++;
if(r==n) break;
while(r<n){
r++;tran[a[r]]++;
if(a[r]==q) break;
}
if(a[r]!=q) break;
}
printf("%d %d\n",ans,s.size());
rep(i,0,s.size()-1)printf("[%d,%d] ",s[i],t[i]);
printf("[%d,%d]\n",s[s.size()-1],t[t.size()-1]);
return 0;
}
C++ 解法, 执行用时: 579ms, 内存消耗: 20036KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define endl "\n"
#define FIN freopen("1.txt","r",stdin)
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
inline int read() {char c;int ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
inline LL readl() {char c;LL ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
const int N = 5000010;
vector<int> s;
vector<int> t;
map<int,int> mp;
int ans = 100000;
int n,a[N];
int q;
int cnt = 0;
int tran[N];
int main()
{
n = read();
//mp.clear();mem(tran,0);
repn(i,1,n){
int &t = a[i];t = read();
if(mp.count(t)==0){
mp[t] = cnt;
t = cnt;
tran[cnt++]++;
}else{
t = mp[t];
tran[t]++;
}
}
int l = 1, r = n;
while(tran[a[r]]>1){
tran[a[r]]--;
r--;
}
while(1){
while(tran[a[l]]>1){tran[a[l]]--;l++;}
//cout<<l<<" "<<r<<endl;
if(ans==(r-l+1)){s.pb(l);t.pb(r);}
else if(ans>(r-l+1)){
s.clear();t.clear();
s.pb(l);t.pb(r);
ans = r-l+1;
}
q = a[l];
tran[a[l]]--;l++;
if(r==n) break;
while(r<n){
r++;tran[a[r]]++;
if(a[r]==q) break;
}
if(a[r]!=q) break;
}
printf("%d %d\n",ans,s.size());
rep(i,0,s.size()-1)printf("[%d,%d] ",s[i],t[i]);
printf("[%d,%d]\n",s[s.size()-1],t[t.size()-1]);
return 0;
}
C++ 解法, 执行用时: 595ms, 内存消耗: 19904KB, 提交时间: 2020-12-23
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define endl "\n"
#define FIN freopen("1.txt","r",stdin)
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
inline int read() {char c;int ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
inline LL readl() {char c;LL ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
const int N = 5000010;
vector<int> s;
vector<int> t;
map<int,int> mp;
int ans = 100000;
int n,a[N];
int q;
int cnt = 0;
int tran[N];
int main()
{
n = read();
//mp.clear();mem(tran,0);
repn(i,1,n){
int &t = a[i];t = read();
if(mp.count(t)==0){
mp[t] = cnt;
t = cnt;
tran[cnt++]++;
}else{
t = mp[t];
tran[t]++;
}
}
int l = 1, r = n;
while(tran[a[r]]>1){
tran[a[r]]--;
r--;
}
while(1){
while(tran[a[l]]>1){tran[a[l]]--;l++;}
//cout<<l<<" "<<r<<endl;
if(ans==(r-l+1)){s.pb(l);t.pb(r);}
else if(ans>(r-l+1)){
s.clear();t.clear();
s.pb(l);t.pb(r);
ans = r-l+1;
}
q = a[l];
tran[a[l]]--;l++;
if(r==n) break;
while(r<n){
r++;tran[a[r]]++;
if(a[r]==q) break;
}
if(a[r]!=q) break;
}
printf("%d %d\n",ans,s.size());
rep(i,0,s.size()-1)printf("[%d,%d] ",s[i],t[i]);
printf("[%d,%d]\n",s[s.size()-1],t[t.size()-1]);
return 0;
}
C++ 解法, 执行用时: 602ms, 内存消耗: 19932KB, 提交时间: 2020-11-01
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define endl "\n"
#define FIN freopen("1.txt","r",stdin)
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
inline int read() {char c;int ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
inline LL readl() {char c;LL ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
const int N = 5000010;
vector<int> s;
vector<int> t;
map<int,int> mp;
int ans = 100000;
int n,a[N];
int q;
int cnt = 0;
int tran[N];
int main()
{
n = read();
//mp.clear();mem(tran,0);
repn(i,1,n){
int &t = a[i];t = read();
if(mp.count(t)==0){
mp[t] = cnt;
t = cnt;
tran[cnt++]++;
}else{
t = mp[t];
tran[t]++;
}
}
int l = 1, r = n;
while(tran[a[r]]>1){
tran[a[r]]--;
r--;
}
while(1){
while(tran[a[l]]>1){tran[a[l]]--;l++;}
//cout<<l<<" "<<r<<endl;
if(ans==(r-l+1)){s.pb(l);t.pb(r);}
else if(ans>(r-l+1)){
s.clear();t.clear();
s.pb(l);t.pb(r);
ans = r-l+1;
}
q = a[l];
tran[a[l]]--;l++;
if(r==n) break;
while(r<n){
r++;tran[a[r]]++;
if(a[r]==q) break;
}
if(a[r]!=q) break;
}
printf("%d %d\n",ans,s.size());
rep(i,0,s.size()-1)printf("[%d,%d] ",s[i],t[i]);
printf("[%d,%d]\n",s[s.size()-1],t[t.size()-1]);
return 0;
}
C++ 解法, 执行用时: 760ms, 内存消耗: 19960KB, 提交时间: 2020-12-28
#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int main()
{
int n;
scanf ("%d", &n);
vector<int> A(n);
unordered_set<int> Set;
unordered_map<int, int> winHash;
for (int i = 0; i < n; ++i)
{
scanf("%d", &A[i]);
Set.insert(A[i]);
}
vector<pair<int, int>> ans;
int count = Set.size(), winnum = 1;
int left = 0, right = 0;
int minlen = INT_MAX;
winHash[A[0]] = 1;
while (right < n)
{
if (left <= right && winnum == count)
{
if (right-left+1 < minlen)
{
minlen = right-left+1;
ans.clear();
}
if (right-left+1 == minlen)
ans.push_back({left+1, right+1});
if (--winHash[A[left]] == 0)
winnum--;
left++;
}
else
{
right++;
if (right == n) break;
if (winHash[A[right]]++ == 0) winnum++;
}
}
int nans = ans.size();
printf("%d %d\n", minlen, nans);
for (int i = 0; i < nans; ++i)
{
printf(" [%d,%d]"+!i, ans[i].first, ans[i].second);
}
printf("\n");
return 0;
}