Codeforces Round #267 (Div. 2) E Alex and Complicated Task_html/css_WEB-ITnose

A very good thinking question, greedy

The main idea of ​​the question: Given n numbers, you need to find the longest subsequence so that the 4k-4k 3 items of this subsequence are The form of a,b,a,b (numbered from 0).

Awesome greed, but my thinking ability is still not good...

I can think of some ideas, but I can’t write down the code...

Reference http://www.cnblogs.com/shiina-mashiro/p/3981944.html

Idea:

1. To deal with the situation where four numbers are equal, just output the four numbers directly - --- Use map for the number of times the record number appears, so there is no need for discretization (on the Internet, it is said that when querying map, logn, discretization requires sorting, nlogn, when large numbers need to be mapped into decimals, doesn't it need to be discretized? . . )

2. The case of ABAB

First of all, we must understand that two pairs of numbers must be adjacent to form ABAB. This was not considered at first. I thought it would require an O(n^2) algorithm, so I didn’t dare to write it.

Then give two adjacent logarithmic analysis ideas (a, b) (c, d).

d>b Obviously, because d is the number currently read, a, b, c, are the numbers read previously

Then according to the relationship between c and a, b, the following situations can be divided:

(1)c

(2)b>c>=a to form ABAB, record

(3)c>= b I don’t know which one to take from (a, b) (c, d), so save them first and wait for the next number to be read in for processing

//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <iostream>#include <map>#include <vector>using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i<e;i++)#define repe(i,s,e) for(int i=s;i<=e;i++)#define CL(a,b) memset(a,b,sizeof(a))#define IN(s) freopen(s,"r",stdin)#define OUT(s) freopen(s,"w",stdout)const ll ll_INF = ((ull)(-1))>>1;const double EPS = 1e-8;const int INF = 100000000;const int MAXN = 500000+100;struct Node{    int l,r;    int x;}nodes[MAXN];map<int, int>pos,cnt;vector<int>b;int num[MAXN],n,top;void read(){    b.clear();    top=0;    for(int i=1;i<=n;i++)        scanf("%d",&num[i]);}void push(int x, int y){    b.push_back(x);    b.push_back(y);    b.push_back(x);    b.push_back(y);    cnt.clear();    pos.clear();    top=0;}int main(){    //IN("E.txt");    while(~scanf("%d",&n))    {        read();        for(int i=1;i<=n;i++)        {            int x=num[i];            if(cnt[x] != 0) cnt[x]++;            else cnt[x] = 1;            if(cnt[x] == 4){push(x,x);continue;}            if(pos[x] == 0){pos[x] = i; continue;}            //system("pause");            /*下面两行牛逼代码*/            int l=pos[x],r=i;            pos[x]=i;            while(top>0)            {                int bl=nodes[top-1].l, br=nodes[top-1].r, bx=nodes[top-1].x;                if(l>bl && l < br){push(bx,x);break;}                else if(l<=bl)top--;                else                {                        nodes[top].l=l;                        nodes[top].r=r;                        nodes[top].x=x;                        top++;                        break;///                }            }            if(top == 0){nodes[0].l=l;nodes[0].r=r;nodes[0].x=x;top++;}        }        printf("%d\n",b.size());        if(b.size())printf("%d",b[0]);        for(int i=1;i<b.size();i++)            printf(" %d",b[i]);        putchar('\n');    }    return 0;}