(TOJ) 245 / 逆序數對2

http://sprout.tw/oj/pro/245/

我的想法：
用treap維護好之前的數字，然後查詢 -q+aj ~ -p+aj 之間的數字XD

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

struct Treap {
 Treap* lc;
 Treap* rc;
 int key,pri,size;
 Treap(int _key) {
  lc=rc=NULL;
  key=_key;
  pri=rand();
  size=1;
 }
};

int Size(Treap* t) {
 return t ? t->size : 0;
}

void pull(Treap* t) {
 t->size = 1 + Size(t->lc) + Size(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 (t->key <= k) {
  a=t;
  split(t->rc,k,a->rc,b);
  pull(a);
 }
 else {
  b=t;
  split(t->lc,k,a,b->lc);
  pull(b);
 }
}

//p<=aj-ai<=q
//-q+aj<=ai<=-p+aj

int query(Treap* root,int val,int p,int q) {
 Treap* tl;
 Treap* tr;
// cout<<-q+val-1<<" ~ "<<-p+val <<endl;
 split(root,-q+val-1,tl,root);
 split(root,-p+val,root,tr);
 if (root!=NULL) {
//  cout<<"root->key = "<<root->key<<endl;
  pull(root);
 }
 else {
//  cout<<"empty\n";
 }
 int ret=Size(root);
 root=merge(merge(tl,root),tr);
 return ret;
}

void dfs(Treap* t) {
 cout<<t->key<<' ';
 if (t->lc) dfs(t->lc);
 if (t->rc) dfs(t->rc);
}

int main () {
 srand(time(NULL));
 int T;
 scanf("%d",&T);
 while (T--) {
  int n,p,q;
  scanf("%d %d %d",&n,&p,&q);
  long long ans=0;
  Treap* root=NULL;
  for (int x=0;n>x;x++) {
//   cout<<"x="<<x<<endl;
   int i;
   scanf("%d",&i);
   ans+=query(root,i,p,q);
   //root=merge(root,new Treap(i)); ==> 錯的 
   Treap* tl;
   Treap* tr;
   split(root,i-1,tl,root);
   split(root,i,root,tr);
   root=merge(root,new Treap(i));
   root=merge(merge(tl,root),tr);
  }
  
  printf("%lld\n",ans);
 }
}

(TOJ) 80 / RMQ 練習(1) [treap 區間max,min]

http://sprout.tw/oj/pro/80/

Treap 解

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

struct Treap {
 Treap* lc;
 Treap* rc;
 int val;
 int pri;
 int key;
 int mx;
 Treap(int _val,int _key) {
  lc=rc=NULL;
  val=_val;
  key=_key;
  pri=rand();
  mx=_val;
 }
};

const int INF= 1e9+7;

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

void pull(Treap* t) {
 t->mx = min(Mx(t->lc),Mx(t->rc));
 t->mx = min(t->mx,t->val);
}

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 (t->key <= k) {
  a=t;
  split(t->rc,k,a->rc,b);
  pull(a);
 }
 else {
  b=t;
  split(t->lc,k,a,b->lc);
  pull(b);
 }
}

void insert(Treap* root,int k,int val) {
 Treap* tl;
 Treap* tr;
 split(root,k-1,tl,root);
 split(root,k,root,tr);
 root->val = root->mx = val;
 merge(merge(tl,root),tr);
}

int query(Treap* root,int l,int r) {
 Treap* tl;
 Treap* tr;
 split(root,l-1,tl,root);
 split(root,r,root,tr);
 int ret=root->mx;
 merge(merge(tl,root),tr);
 return ret;
}

int main () {
 srand(time(NULL));
 int T,n;
 while (scanf("%d %d",&T,&n) != EOF) {
  Treap* root=NULL;
  for (int x=0;n>x;x++) {
//   cout<<"x="<<x<<endl;
   int i;
   scanf("%d",&i);
   root = merge(root,new Treap(i,x));
   
  }
  while (T--) {
   int i,j,k;
   scanf("%d %d %d",&i,&j,&k);
   if (i==1) {
    printf("%d\n",query(root,j,k));
   }
   else {
    insert(root,j,k);
   }
  }
 }
}

(TOJ) 386 西瓜愛算術 [Python : tree]

http://sprout.tw/oj/pro/386/

主要想法就是如果遇到括號，就一直遞迴下去

Python班完了再放到codepad上XDDD

http://sprout.tw/oj/chal/53947/

def get_pivot( s ):    
    cnt = 0
    for i in range( 3 , len( s ) ):
        if s[ i ] == '(':
            cnt += 1
        elif s[ i ] == ')':
            cnt -= 1
        elif cnt == 0 and s[ i ] == ' ':
            return i
    return -123456789;
        

def f(s) :
    #print("in " + s);
    t = get_pivot(s);
    #print("t = "+str(t));
    a=0;
    b=0;
    if (s[t-1] == ')') :
        tmpt=t-1;
        check=1;
        while (s[tmpt]!='(') or check!=0:
            tmpt-=1;
            if (s[tmpt]==')') :
                check+=1;
            elif (s[tmpt]=='(') :
                check-=1
        a = f(s[tmpt:t])
    else :
        tmpt=t-1;
        tmp=[];
        while (s[tmpt]!=' ') :
            tmp.append(s[tmpt]);
            tmpt-=1;
        a=0;
        for i in range(len(tmp)-1,-1,-1) :
            a=a*10 + int(tmp[i]);
            
    if (s[t+1] == '(') :
        tmpt=t+1;
        check=1;
        while (s[tmpt]!=')') or check!=0:
            tmpt+=1;
            if (s[tmpt]==')') :
                check-=1;
            elif (s[tmpt]=='(') :
                check+=1;
        b = f(s[t+1:tmpt+1])
    else :
        tmpt=t+1;
        tmp=[];
        while (s[tmpt]!=')') :
            tmp.append(s[tmpt]);
            tmpt+=1;
        b=0;
        for i in range(0,len(tmp)) :
            b=b*10 + int(tmp[i]);
            
    #print(s + " : a=" + str(a) +" b= "+str(b));
            
    if s[1]=='+' :
        return a+b;
    elif s[1]=='-' :
        return a-b;
    elif s[1]=='*' :
        return a*b;
    elif s[1]=='/' :
        return a//b;
        
    

n=int(input());
for i in range(0,n) :
    s=input()
    tmp=get_pivot(s)
    
    if tmp==-123456789:
        print(s);
    else :
        if (s[0]!='(') :
            s = "(" + s + ")";
        print(f(s));

(TOJ) 157 [rolling hash]

http://sprout.tw/oj/pro/157/

一定要用rolling hash!!!

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int a[2][1000001];
int w[101];
int v[101];

int main () {
int T;
scanf("%d",&T);
while (T--) {
int n,m;
scanf("%d %d",&n,&m);
for (int x=1;n>=x;x++) scanf("%d %d",&w[x],&v[x]);
memset(a,0,sizeof(a));
for (int x=1;n>=x;x++) {
for (int y=1;m>=y;y++) {
if (y - w[x] < 0) a[1][y] = a[0][y];
else a[1][y] = max(a[0][y],a[0][y-w[x]] + v[x]);
}
for (int y=1;m>=y;y++) a[0][y] = a[1][y];
}
printf("%d\n",a[1][m]);
}
}

(TOJ) 47. 1d-kd-tree

http://sprout.tw/oj/pro/47/

其實這題主要是要讓你實作一棵二元搜尋樹啦，但是我的code不是這樣寫(delete有點麻煩XD)

如果是走二元搜尋樹，insert就是依照key值走下去就對了，query就認真找吧，delete的話，最麻煩的case是要找左子樹的max或右子樹的min。(有點籠統，抱歉~~)

我的離線(off-line)作法是，先把所有數值離散化後，開一棵數值線段樹，記錄說離散化後的這個數字有沒有出現過，沒有的話設成INF，對於每個區間，我要維護說這個區間的Max和Min。

接下來講query的部分，當如果你今天要往左子樹query的時候，右子樹的Min可能是你右邊的答案，往右子樹走的時候，左邊樹的Max可能是你的答案。

所以，綜合一下，就會發現，這題不難XDDD。

(用Treap寫也或許可以，找機會有天來試試看XDDD)

Code :
http://codepad.org/YRd2ghje

(TOJ) 293.樹重心

http://sprout.tw/oj/pro/293/

本題就是要求樹的重心

樹重心定義：使得「拔除某節點後，形成的若干棵樹分別的節點數量中的最大值」<=樹的大小/2。

題目中有範例。

要怎麼解呢？

如果把它看成一棵樹，我們會需要維護的是 1.兒子的總合 2.眾多兒子中的最大的那個

因為我們要取若干棵節點數量中的最大值，那父節點就是(全部節點 - 兒子節點總合 - 自己)，那就是max (父節點, 眾多兒子中的最大)。

那就一次dfs就可以完成了！

阿對了，哪個點當根都可以，所以我的code是用random

//樹重心


#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;

const int MAX_N = 100003;

vector<int> edg[MAX_N];

struct Node {
    int val;
    int sum;
    int max;
} node[MAX_N];

bool visit[MAX_N];

int dfs(int id) {
    visit[id]=true;
    int len=edg[id].size();
    for (int x=0;len>x;x++) {
        int tmp=edg[id][x];
        if (visit[tmp]==true) ;  //回到父親
        else {
            int t=dfs(tmp);
            node[id].sum+=t;
            node[id].max = max(node[id].max,t);
        }
    }
    return node[id].sum+1;
}

int main () {
    srand(time(NULL));
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        //init
        for (int x=0;n>x;x++) {
            edg[x].clear();
            node[x].sum=node[x].max = 0;
            node[x].val = x;
            visit[x]=false;
        }
        for (int x=0;n-1>x;x++) {
            int a,b;
            scanf("%d %d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        int id = rand() % n;
        dfs(id);
        int ans=n;
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            ans=min(ans,tmp);
        }
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            if (tmp==ans) {
                printf("%d\n",x);
                break;
            }
        }
        
    }
}