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 repe for i="s;i<=e;i++)#define" cl memset in freopen out 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;i0)            {                int bl=nodes[top-1].l, br=nodes[top-1].r, bx=nodes[top-1].x;                if(l>bl && l  <br> <br> <p></p> <p><br> </p> <p><br> </p> </int></int></e></vector></map></iostream></string></algorithm></cstring></cstdio>