Codeforces ラウンド #267 (ディビジョン 2) E アレックスと複雑なタスク_html/css_WEB-ITnose

とても良い思考の質問、貪欲です

質問の主な考え方: n 個の数値が与えられた場合、この部分列の 4k-4k+3 項目が a,b,a, となるような最長の部分列を見つける必要があります。 b 形式 (0 から番号が付けられます)。

欲張りですが、思考力はまだまだです…

アイデアはいくつか思いつくのですが、コードが書けません…

参考 http://www.cnblogs.com/ shiina- mahiro/p/3981944.html

考え方:

1. 4 つの数値が等しい状況に対処するには、4 つの数値を直接出力するだけです。出現回数を記録するためにマップを使用するため、離散化 (オンラインマップをクエリするとき、logn はソートする必要があり、大きな数値を 10 進数にマッピングする必要がある場合、nlogn は離散化する必要がないと言われています。)

2. ABAB の状況

まず、何かを理解する必要があります。ABAB を形成するには、2 つの数値が隣接している必要があります。最初は、O(n^2) アルゴリズムが必要になるとは考えていませんでした。書いてください。

次に、2 つの隣接する対数解析のアイデア (a、b) (c、d) を与えます。

d>b 明らかに、d は現在読み取られている番号なので、a、b、c は

前に読み取られた番号です

すると、c と a、b の関係に従って、次の状況が分割されます:

(1 )c

(2)b>c>=a は ABAB を形成します、それを記録してください

(3)c>=b (a,b) (c, d) なので、最初にすべて保存します。次の番号が処理のために読み込まれるのを待っています

//#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;}