(51NOD) 1619. 完全二叉树的方差

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1619

首先，經由證明(?)，一定是a_i中最大的跟b_j中最小，a_i第二大跟b_j第二小配。

知道這個後，要怎麼配呢(?)

我們可以枚舉一個數字X，代表你選的數字要盡量接近這個X。

再亂搞一通(?)後，就AC了(?)。

cal(x) 會回傳一個x節點的二元樹直徑。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const double eps = 1e-9;

const int N = 1006;

int a[N],b[N];

int cal(int x)
{
    if (x == 1) return 0;
    return floor(log2(x)+eps) + floor( log2( x - pow(2, (int)(floor(log2(x)) + eps)-1 ) ) + eps );
}

int merge_root(int a,int b)
{
    return max( max( cal(a) , cal(b) ),(int)( floor(log2(a)) + floor(log2(b)) ) + 1 );
}

int merge_leaf(int a,int b)
{
    return cal(a) + cal(b) +1;
}

int d[N];

int L[N],R[N];

const LL INF = (1LL<<60);

int _[N];

int n;

LL solve(LL x)
{
    LL sum=0;
    for (int i=1;n>=i;i++)
    {
        if (R[i] < x) _[i] = R[i];
        else if (L[i] > x) _[i] = L[i];
        else _[i] = x;
        sum += _[i];
    }
    LL ret=0;
    for (int i=1;n>=i;i++)
    {
        ret += (n * _[i] - sum) * (n * _[i] - sum);
    }
    return ret;
}

int main ()
{
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&b[i]);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    reverse(b+1,b+n+1);
    int mx = -1,mn = (1<<20);
    for (int i=1;n>=i;i++)
    {
        L[i] = merge_root(a[i],b[i]);
        R[i] = merge_leaf(a[i],b[i]);
        mx = max(mx,R[i]);
        mn = min(mn,L[i]);
    }
    LL ans = INF;
    for (int i=mn;mx>=i;i++)
    {
        LL ret = solve(i);
        if (ret < ans) ans = ret;
    }
    printf("%lld\n",ans);
}

(51NOD) 1364. 最大字典序排列

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1364

很棒(?)的題目(?)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

struct Treap
{
    Treap *lc,*rc,*fa;
    int sz,val,pri;
    int mx;
    Treap(){}
    Treap(int _val) : lc(NULL),rc(NULL),fa(NULL),sz(1),val(_val),pri(rand()),mx(_val) {}
};

int Sz(Treap* t)
{
    return t?t->sz:0;
}

int Mx(Treap* t)
{
    return t?t->mx:0;
}

void pull(Treap* t)
{
    if (!t) return;
    t->sz = 1;
    t->mx = max( max( Mx(t->lc),Mx(t->rc) ) , t->val );
    if (t->lc)
    {
        t->lc->fa = t;
        t->sz += Sz(t->lc);
    }
    if (t->rc)
    {
        t->rc->fa = t;
        t->sz += Sz(t->rc);
    }
}

Treap* merge(Treap* a,Treap* b)
{
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri)
    {
        a->rc = merge(a->rc,b);
        pull(a);
        return a;
    }
    else
    {
        b->lc = merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b)
{
    if (!t) a=b=NULL;
    else if (Sz(t->lc) + 1 <= k)
    {
        a=t;
        split(t->rc,k - Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

int Q(Treap* t)
{
   int ret = Sz(t->lc) + 1;
   while (t->fa != NULL)
   {
       if (t->fa->rc == t)
       {
           ret += Sz(t->fa->lc) + 1;
       }
       t = t->fa;
   }
   return ret;
}

const int N = 100006;

int a[N];

Treap *p[N];

void show(Treap* t)
{
    if (!t) return;
    show(t->lc);
    printf("%d\n",t->val);
    show(t->rc);
}

int main ()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for (int i=1;n>=i;i++)
    {
        p[i] = new Treap(i);
    }
    Treap* root = NULL;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        root = merge( root, p[ a[i] ] );
    }
    for (int i=1;n-1>=i;i++)
    {
        //find the maximum number among the first k elements
        if (k == 0) continue;
        Treap *tl,*tr;
        split(root,i-1,tl,root);
        split(root,k+1,root,tr);
        int mx = Mx(root);
        int _ = Q(p[mx]);
        k -= (_-1);
        //cout << "mx = "<<mx<< " , _ = "<<_<<endl;
        Treap *_1,*_2;
        split(root,_-1,_1,root);
        split(root,1,_2,root);
        root = merge( merge( _2,_1 ),root );
        root = merge( merge(tl,root),tr );
    }
    show(root);
}