51nod 1280 前缀后缀集合(set)

1280 前缀后缀集合 题目来源：  Codility 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题  收藏  关注 一个数组包含N个正整数，其中有些是重复的。一个前缀后缀集是满足这样条件的下标对(P,S)， 0<= P,S < N 满足数组元素A[0..P]的值也在A[S..N - 1]的值中出现，并且A[S..N - 1]中的值也再A[0..P]中出现。换句话说前缀的集合A[0..P]与后缀集合A[S..N - 1]包含完全相同的值。求这样的前缀后缀集合的数量。 例如：3 5 7 3 3 5，共有14个集合符合条件：(1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0) 本题由   @javaman 翻译。 Input 第1行：一个数N, 表示数组的长度(1 <= N <= 50000)。 第2 - N + 1行：每行1个数，对应数组中的元素Ai。(1 <= Ai <= 10^9) Output 输出符合条件的集合数量。 Input示例 6 3 5 7 3 3 5 Output示例 14

解：直接开两个set一个从前遍历一个从后遍历，如果后面的元素在前面的元素出现过就加入后面的集合，如果后面的元素存在后面的集合中则累加个数+1，如果两个

集合相等就加上累加个数。一开始图省事直接用set是否相等来做判定条件结果T到死，因为整个集合要一一比较。。。所以用set的大小来做判定条件

#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include <set> #include <bits/stdc++.h> using namespace std; const int N = 3e6+10; typedef long long LL; typedef pair<int,int> pi; set<int>q1,q2; int a[N]; struct FastIO { static const int S = 2*100; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos==len) pos = 0, len = fread(buf, 1, S, stdin); if (pos==len) exit(0); return buf[pos ++]; } inline int xint() { int s = 1, c = xchar(), x = 0; while(c<=32) c = xchar(); if(c=='-') s = -1, c = xchar(); for(;'0'<=c && c<='9';c=xchar()) x = x*10+c-'0'; return x * s; } ~FastIO() { if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } }io; int num[N]; int main() { int n; scanf("%d", &n); for(int i=1;i<=n;i++) a[i]=io.xint(); int cnt=0, ans=0; q1.clear(),q2.clear(); int j=n; for(int i=1;i<=n;i++) { q1.insert(a[i]); while(q1.find(a[j])!=q1.end()&&j>=1) { num[j]=1;q2.insert(a[j]); j--; while(q2.find(a[j])!=q2.end()&&j>=1) { num[j]=num[j+1]+1; j--; } } if(q1.size()==q2.size()) ans+=num[j+1]; } printf("%d\n",ans); return 0; }