Educational Codeforces Round 6 C. Pearls in a Row

• 题意:一个3e5范围的序列；要你分成最多数量的子序列，其中子序列必须是只有两个数相同, 其余的数只能出现一次。

• 策略:

  1. 延伸:这里指的延伸如当发现1…1如果以最后出现重叠的数为右边界则就表示左延伸，若以1.0.1..0第二个0前一个位置作为右边界就为右延伸；
  2. 开始时想是右延伸，考虑到可能只出现一组两个数相同，认为向左延伸会出错，但是直接WA了之后，发现这并不是题目的坑点(其实只需将最后一组改成左右延伸就可以了)，给一组数据就知道向右延伸是错误的:
     
     数据: n = 5, 1 1 0 0 1若是右延伸，则为 【1 1 0】，后面0 1不能配对，其实这里就直接说明了只要存在两个数相同，就不会出现无解的情况；
  3. 左延伸，一遇到里面还存有这个数据，直接往l[],R[]里面存区间，当然l是以上一个r为左边界的；最火一组数据让右边界等于n即可；

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 3e5;

set<int> Set;

int L[MAXN],R[MAXN];

int main()

{

    int i,n,x,l = 1,cnt = 0;

    cin>>n;

    for(i = 1;i <= n;i++){

        scanf("%d",&x);

        if(Set.count(x)){

            L[++cnt] = l;

            R[cnt] = i;

            l = i + 1;

            Set.clear();

        }else Set.insert(x);

    }

    if(cnt == 0) return puts("-1"),0;

    R[cnt] = n;

    printf("%d\n",cnt);

    for(i = 1;i <= cnt;i++)

        printf("%d %d\n",L[i],R[i]);

}