首页 > 代码库 > CF 19C 思维题STL应用

CF 19C 思维题STL应用

2024-10-27 21:28:39   211人阅读

http://codeforces.com/problemset/problem/19/C

Once Bob saw a string. It contained so many different letters, that the letters were marked by numbers, but at the same time each letter could be met in the string at most 10 times. Bob didn‘t like that string, because it contained repeats: a repeat of length x is such a substring of length 2x, that its first half coincides character by character with its second half. Bob started deleting all the repeats from the string. He does it as follows: while it‘s possible, Bob takes the shortest repeat, if it is not unique, he takes the leftmost one, and deletes its left half and everything that is to the left of this repeat.

You‘re given the string seen by Bob. Find out, what it will look like after Bob deletes all the repeats in the way described above.

Input

The first input line contains integer n (1?≤?n?≤?105) — length of the string. The following line contains n space-separated integer numbers from 0 to 109 inclusive — numbers that stand for the letters of the string. It‘s guaranteed that each letter can be met in the string at most 10 times.

Output

In the first line output the length of the string‘s part, left after Bob‘s deletions. In the second line output all the letters (separated by a space) of the string, left after Bob deleted all the repeats in the described way.

Sample test(s)
input
6
1 2 3 1 2 3
output
3
1 2 3
input
7
4 5 6 5 6 7 7
output
1
7 


/**
CF19C STL
题目大意：给定一个数组有重复，让求出删除重复后的数组。所谓重复即为；123123，而123124不算重复。必须是2n长度1-n和n+1~n*2完全对应相等
          现在寻找最右边的一个重复的，将其1~n部分和其前面所有的数全部删掉。
解题思路：利用list存储所有相同数字依次出现的位置，从前往后匹配，并一边删除，比vector时间复杂度低
*/
#include <stdio.h>
#include <iostream>
#include <map>
#include <list>
using namespace std;
map<int,list<int> > t;
list<int>::iterator it;
int a[200000];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for (int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            t[a[i]].push_back(i);
        }
        a[n]=-1;
        int ans;
        for (int i=0; i<n; i++)
        {
            list<int> e=t[a[i]];
            t[a[i]].pop_front();
            for (it=e.begin(); it!=e.end(); it++)
            {
                int x=i+1;
                int y=(*it)+1;
                while (x<(*it)&&a[x]==a[y])
                {
                    x++;
                    y++;
                }
                if (x==(*it))
                {
                    i=(*it)-1;
                    ans=(*it);
                }
            }
        }
        printf("%d\n",n-ans);
        for (int i=ans; i<n; i++)
            printf(i==n-1?"%d\n":"%d ",a[i]);
    }
    return 0;
}


CF 19C 思维题STL应用


联系
我们