latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2017年4月27日 星期四

[ uvaLive 5031 ] Graph and Queries

題目:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=33&problem=3032

解法:
這題很明顯是名次樹的題目。把所有操作存起來,然後再到著做回來,就可以把刪邊變成增邊。用並查集維護那些點連通,用Treap紀錄那些點的權重,當增加邊的操作造成兩個集合要合併時,使用啟發式合併,總複雜度大約為$\ord{n log n log n}$

我的code中沒有用到任何旋轉的操作,全部都用split和merge完成,證明了只需要會split和merge一樣是可以拿來寫名次樹的

code:
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
#define MAXN 100005
#define MAXM 1000005
struct node{
    node *l,*r;
    int key;
    unsigned s;
    node(int k):l(0),r(0),key(k),s(1){}
    void up(){
        s=1;
        if(l)s+=l->s;
        if(r)s+=r->s;
    }
};
inline unsigned ran(){
    static unsigned x=time(0);
    return x=x*0xdefaced+1;
}
inline unsigned size(node *o){
    return o?o->s:0;
}
node *merge(node *a,node *b){
    if(!a||!b)return a?a:b;
    if(ran()%(a->s+b->s)<a->s){
        a->r=merge(a->r,b);
        a->up();
        return a;
    }else{
        b->l=merge(a,b->l);
        b->up();
        return b;
    }
}
void split(node *o,node *&a,node *&b,int k){
    if(!o)a=b=0;
    else{
        if(o->key<k){
            a=o;
            split(o->r,a->r,b,k);
        }else{
            b=o;
            split(o->l,a,b->l,k);
        }
        o->up();
    }
}
void insert(node *&o,int k){
    node *a,*b;
    split(o,a,b,k);
    o=merge(a,merge(new node(k),b));
}
void split2(node *o,node *&a,node *&b,unsigned k){
    if(!o)a=b=0;
    else{
        if(k<=size(o->l)){
            b=o;
            split2(o->l,a,b->l,k);
        }else{
            a=o;
            split2(o->r,a->r,b,k-size(o->l)-1);
        }
        o->up();
    }
}
bool erase(node *&o,int k){
    node *a,*b,*c;
    split(o,a,b,k);
    if(!b)return 0;
    split2(b,b,c,1);
    if(b->key==k){
        delete b;
        return o=merge(a,c),1;
    }
    return o=merge(a,merge(b,c)),0;
}
inline int kth(node *&o,int k){
    if((int)size(o)<k||k<1)return 0;
    //注意這裡他會給你不合法的測資,被坑很久
    node *a,*b,*c;
    split2(o,a,c,size(o)-k);
    split2(c,b,c,1);
    o=merge(a,merge(b,c));
    return b->key;
}
struct edge{
    int u,v,use;
    edge():use(0){}
}E[MAXM];
struct XDD{
    char c;
    int p,w;
}g;
vector<XDD> P;
int n,m,t;
int st[MAXN];
int s[MAXN];
int find(int x){
    return st[x]==x?x:st[x]=find(st[x]);
}
node *sa[MAXN];
void dfs(node *&o,node *&x){
    if(!o)return;
    insert(x,o->key);
    dfs(o->l,x);
    dfs(o->r,x);
    delete o;
    o=0;
}
node *strong_merge(node *&a,node *&b){
    if(size(a)<size(b))swap(a,b);
    dfs(b,a);
    return a;
}
int main(){
    int _=0;
    while(scanf("%d%d",&n,&m),n||m){
        for(int i=1;i<=n;++i){
            scanf("%d",&s[i]);
            st[i]=i;
        }
        for(int i=1;i<=m;++i){
            scanf("%d%d",&E[i].u,&E[i].v);
            E[i].use=0;
        }
        P.clear();
        for(char c[10];scanf("%s",c),c[0]!='E';){
            g.c=c[0];
            if(c[0]=='D'){
                scanf("%d",&g.p);
                E[g.p].use=1;
            }else{
                scanf("%d%d",&g.p,&g.w);
                if(c[0]=='C'){
                    swap(s[g.p],g.w);
                }
            }
            P.push_back(g);
        }
        for(int i=1;i<=n;++i){
            sa[i]=new node(s[i]);
        }
        for(int i=1;i<=m;++i){
            int u=find(E[i].u),v=find(E[i].v);
            if(!E[i].use&&u!=v){
                st[u]=v;
                sa[v]=strong_merge(sa[v],sa[u]);
            }
        }
        vector<int> ans;
        for(int i=(int)P.size()-1;i>=0;--i){
            if(P[i].c=='D'){
                int u=find(E[P[i].p].u),v=find(E[P[i].p].v);
                if(u!=v){
                    st[u]=v;
                    sa[v]=strong_merge(sa[v],sa[u]);
                }
            }else if(P[i].c=='Q'){
                ans.push_back(kth(sa[find(P[i].p)],P[i].w));
            }else{
                int p=find(P[i].p);
                erase(sa[p],s[P[i].p]);
                insert(sa[p],P[i].w);
                s[P[i].p]=P[i].w;
            }
        }
        double V=(double)ans.size();
        long long tot=0;
        for(auto i=ans.rbegin();i!=ans.rend();++i)tot+=*i;
        printf("Case %d: %.6lf\n",++_,tot/V);
    }
    return 0;
}

2017年3月7日 星期二

[ POJ 1741 ] Tree

題目:
http://poj.org/problem?id=1741

解法:
樹分治,找出重心後,算出通過重心且長度$\leq k$的路徑有幾個,因為我是所有路徑一起算的,所以還要扣掉在同一個子樹的路徑,算路徑會花$\ord{n log n}$,樹分治深度最多$\ord{log n}$,因此總複雜度是$\ord{n log^2 n}$

code:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
int n,k;
vector<pair<int,int> >g[MAXN];
int size[MAXN];
bool vis[MAXN];
inline void init(){
    for(int i=0;i<=n;++i){
        g[i].clear();
        vis[i]=0;
    }
}
void get_dis(vector<int> &dis,int u,int pa,int d){
    dis.push_back(d);
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first,w=g[u][i].second;
        if(v!=pa&&!vis[v])get_dis(dis,v,u,d+w);
    }
}
vector<int> dis;//這東西如果放在函數裡會TLE
int cal(int u,int d){
    dis.clear();
    get_dis(dis,u,-1,d);
    sort(dis.begin(),dis.end());
    int l=0,r=dis.size()-1,res=0;
    while(l<r){
        while(l<r&&dis[l]+dis[r]>k)--r;
        res+=r-(l++);
    }
    return res;
}
pair<int,int> tree_centroid(int u,int pa,const int sz){
    size[u]=1;//找樹重心,second是重心
    pair<int,int> res(INT_MAX,-1);
    int ma=0;
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v==pa||vis[v])continue;
        res=min(res,tree_centroid(v,u,sz));
        size[u]+=size[v];
        ma=max(ma,size[v]);
    }
    ma=max(ma,sz-size[u]);
    return min(res,make_pair(ma,u));
}
int tree_DC(int u,int sz){
    int center=tree_centroid(u,-1,sz).second;
    int ans=cal(center,0);
    vis[center]=1;
    for(size_t i=0;i<g[center].size();++i){
        int v=g[center][i].first,w=g[center][i].second;
        if(vis[v])continue;
        ans-=cal(v,w);
        ans+=tree_DC(v,size[v]);
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&k),n||k){
        init();
        for(int i=1;i<n;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
        }
        printf("%d\n",tree_DC(1,n));
    }
    return 0;
}

2016年10月27日 星期四

[ 2007-2008 Summer Petrozavodsk Camp, Japanese Contest ] A. Reading Brackets in English

題目在這裡:http://codeforces.com/gym/100963

這題就是給你一個固定的語法(不是題目輸入的),之後給你n個字串,你要判斷這個字串用給的語法去分析是否ambigous,如果不是就按題目要求輸出他的語法結構。

這裡我把給的語法轉化成形式文法,如下:
$
S \Longrightarrow list \; E \\
S \Longrightarrow list \; L \\
L \Longrightarrow E \; L \\
L \Longrightarrow E \; AND \; E \\
E \Longrightarrow T \\
E \Longrightarrow S
$
這裡的$list$就是原本的"a list of"、$AND$就是"and"、$T$就是所有的合法英文單字。之後利用CYK算法跟earley算法去分析並找出ambiguous。

首先把形式文法轉乘CNF表達式:
 $
S \Longrightarrow W_1 \; S \\
S \Longrightarrow W_1 \; T \\
S \Longrightarrow W_1 \; L \\
L \Longrightarrow S \; L \\
L \Longrightarrow T \; L \\
L \Longrightarrow S \; L^{'} \\
L \Longrightarrow T \; L^{'} \\
L^{'} \Longrightarrow W_2 \; S \\
L^{'} \Longrightarrow W_2 \; T
$
這裡的$W_1$就是原本的"a list of"、$W_2$就是"and"、$T$就是所有的合法英文單字。
接著就可以跑CYK演算法了:
#include<bits/stdc++.h>
using namespace std;
enum P{//symbol
    S,L,LP,T,W1,W2,NUM
};// T="A"|"B"|"C"..., W1="a list of", w2="and" 
struct CNF{
    P s,a,b;// s->ab
    CNF(P s,P a,P b):s(s),a(a),b(b){}
};
vector<CNF> cnf;
inline void cnf_init(){
    cnf.push_back(CNF(S,W1,S));
    cnf.push_back(CNF(S,W1,T));
    cnf.push_back(CNF(S,W1,L));
    cnf.push_back(CNF(L,S,L));
    cnf.push_back(CNF(L,T,L));
    cnf.push_back(CNF(L,S,LP));
    cnf.push_back(CNF(L,T,LP));
    cnf.push_back(CNF(LP,W2,S));
    cnf.push_back(CNF(LP,W2,T));
}
vector<pair<string,P> > tok;
int dp[400][400][P::NUM];
bool amb[400][400][P::NUM];//ambiguous 
inline void CYK(){
    for(size_t i=0;i<tok.size();++i){
        memset(dp[i][i],0,sizeof(dp[i][i]));
        memset(amb[i][i],0,sizeof(amb[i][i]));
        dp[i][i][tok[i].second]=i+1;
    }
    for(int r=0;r<(int)tok.size();++r){
        for(int l=r-1;l>=0;--l){
            memset(dp[l][r],0,sizeof(dp[l][r]));
            memset(amb[l][r],0,sizeof(amb[l][r]));
            for(int k=l;k<r;++k){
                for(size_t i=0;i<cnf.size();++i){
                    if(dp[l][k][cnf[i].a]&&dp[k+1][r][cnf[i].b]){
                        if(dp[l][r][cnf[i].s]){
                            amb[l][r][cnf[i].s]=true;
                        }else{
                            dp[l][r][cnf[i].s]=k+1;
                            amb[l][r][cnf[i].s]=amb[l][k][cnf[i].a]||amb[k+1][r][cnf[i].b];
                        }
                    }
                }
            }
        }
    }
}
vector<string> ans;
void dfs(int l,int r,P type){
    if(l==r){
        if(type==P::T)ans.push_back(tok[l].first);
        return;
    }
    bool is=type==P::S;
    if(is)ans.push_back("(");
    int k=dp[l][r][type]-1;
    for(size_t i=0;i<cnf.size();++i){
        if(dp[l][k][cnf[i].a]&&dp[k+1][r][cnf[i].b]){
            dfs(l,k,cnf[i].a);
            dfs(k+1,r,cnf[i].b);
            break;
        }
    }
    if(is)ans.push_back(")");
}
int n;
string s;
int main(){
    cin.tie(0);
        ios::sync_with_stdio(0);
    cnf_init();
    cin>>n;
    cin.get();
    while(n--){
        getline(cin,s);
        replace(s.begin(),s.end(),',',' ');
        stringstream ss(s);
        tok.clear();
        while(ss>>s){
            if(s=="a"||s=="of")continue;
            if(s=="list"){
                tok.push_back(make_pair("(",P::W1));
            }else if(s=="and"){
                tok.push_back(make_pair(")",P::W2));
            }else tok.push_back(make_pair(s,P::T));
        }
        CYK();
        if(amb[0][tok.size()-1][P::S]){
            cout<<"AMBIGUOUS\n";
        }else{
            ans.clear();
            dfs(0,tok.size()-1,P::S);
            string pre;
            for(size_t i=0;i<ans.size();++i){
                if(pre!="("&&pre!=""&&ans[i]!=")")cout<<' ';
                cout<<(pre=ans[i]);
            }
            cout<<'\n';
        }
    }
    return 0;
}

第二種方式是用earlye直接做,因為earlye可以吃除了空字串之外的任何一種規則,所以可以直接建構語法自動機,我這裡是先建構完自動機後,再從他去建構語法樹:
#include<bits/stdc++.h>
using namespace std;
struct Rule{
    vector<vector<Rule*> > p;
    void add(const vector<Rule*> &l){
        p.push_back(l);
    }
};
map<string,Rule*> NameRule;
map<Rule*,string> RuleName;
inline void init_Rule(){
    for(auto r:RuleName)delete r.first;
    RuleName.clear();
    NameRule.clear();
}
inline Rule *add_rule(const string &s){
    if(NameRule.find(s)!=NameRule.end())return NameRule[s];
    Rule *r=new Rule();
    RuleName[r]=s;
    NameRule[s]=r;
    return r;
}
typedef vector<Rule*> production;
struct State{
    Rule *r;
    int rid,dot_id,start,end;
    State(Rule *r,int rid,int dot,int start):r(r),rid(rid),dot_id(dot),start(start),end(-1){}
    State(Rule *r=0,int col=0):r(r),rid(-1),dot_id(-1),start(-1),end(col){}
    bool completed()const{
        return rid==-1||dot_id>=(int)r->p[rid].size();
    }
    Rule *next_term()const{
        if(completed())return 0;
        return r->p[rid][dot_id];
    }
    bool operator<(const State& b)const{
        if(start!=b.start)return start<b.start;
        if(dot_id!=b.dot_id)return dot_id<b.dot_id;
        if(r!=b.r)return r<b.r;
        return rid<b.rid;
    }
    void print()const{
        cout<<RuleName[r]<<"->";
        if(rid!=-1)for(size_t i=0;;++i){
            if((int)i==dot_id)cout<<" "<<"$";
            if(i>=r->p[rid].size())break;
            cout<<" "<<RuleName[r->p[rid][i]];
        }
        cout<<" "<<"["<<start<<","<<end<<"]"<<endl;
    }
};
struct Column{
    Rule *term;
    string value;
    vector<State> s;
    map<State,set<pair<State,State> > > div;
    //div比較像一棵 左兄右子的樹
    Column(Rule *r,const string &s):term(r),value(s){}
    Column(){}
    bool add(const State &st,int col){
        if(div.find(st)==div.end()){
            div[st];
            s.push_back(st);
            s.back().end=col;
            return true;
        }else return false;
    }
};
inline vector<Column> lexer(string text){
    //tokenize,要自己寫
    //他會把 input stream 變成 token stream,就是(terminal,value)pair
    vector<Column> token;
    replace(text.begin(),text.end(),',',' ');
    stringstream ss(text);
    while(ss>>text){
        if(text=="a"||text=="of")continue;
        if(text=="list"){
            token.push_back(Column(NameRule["("],"("));
        }else if(text=="and"){
            token.push_back(Column(NameRule[")"],")"));
        }else token.push_back(Column(NameRule["T"],text));
    }
    return token;
}
vector<Column> table;
inline void predict(int col,Rule *rul){
    for(size_t i=0;i<rul->p.size();++i){
        table[col].add(State(rul,i,0,col),col);
    }
}
inline void scan(int col,const State &s,Rule *r){
    if(r!=table[col].term)return;
    State ns(s.r,s.rid,s.dot_id+1,s.start);
    table[col].add(ns,col);
    table[col].div[ns].insert(make_pair(s,State(r,col)));
}
inline void complete(int col,const State &s){
    for(size_t i=0;i<table[s.start].s.size();++i){
        State &st=table[s.start].s[i];
        Rule *term=st.next_term();
        if(!term||term->p.size()==0)continue;
        if(term==s.r){
            State nst(st.r,st.rid,st.dot_id+1,st.start);
            table[col].add(nst,col);
            table[col].div[nst].insert(make_pair(st,s));
        }
    }
}
inline pair<bool,State> parse(Rule *GAMMA,const vector<Column > &token){
    table.resize(token.size()+1);
    for(size_t i=0;i<token.size();++i){
        table[i+1]=Column(token[i]);
    }
    table[0]=Column();
    table[0].add(State(GAMMA,0,0,0),0);
    for(size_t i=0;i<table.size();++i){
        for(size_t j=0;j<table[i].s.size();++j){
            State state=table[i].s[j];
            if(state.completed()){
                complete(i,state);
            }else{
                Rule *term=state.next_term();
                if(term->p.size()){
                    predict(i,term);
                }else if(i+1<table.size()){
                    scan(i+1,state,term);
                }
            }
        }
    }
    for(size_t i=0;i<table.back().s.size();++i){
        if(table.back().s[i].r==GAMMA&&table.back().s[i].completed()){
            return make_pair(true,table.back().s[i]);
        }
    }
    return make_pair(false,State(0,-1));
}
struct node{//語法樹的節點
    State s;
    vector<vector<node*> > child;//vector<node*>.size()>1表示ambiguous
    node(const State &s):s(s){}
    node(){}
};
struct State_end_cmp{
    bool operator()(const State &a,const State &b)const{
        return a.end<b.end||(a.end==b.end&&a<b);
    }
};
map<State,node*,State_end_cmp> cache;
vector<node*> node_set;
inline void init_cache(){
    for(auto d:node_set)delete d;
    cache.clear();
    node_set.clear();
}
void _build_tree(const State &s,node *pa,bool amb=0){
    if(cache.find(s)!=cache.end()){
        pa->child.push_back(vector<node*>(1,cache[s]));
        return;
    }
    node *o;
    if(s.completed()){
        o=new node(s);
        if(amb)pa->child.back().push_back(o);
        else pa->child.push_back(vector<node*>(1,o));
    }else o=pa->child.back().back();
    amb=0;
    for(auto div:table[s.end].div[s]){
        if(!amb)_build_tree(div.first,pa);
        _build_tree(div.second,o,amb);
        amb=1;
    }
    if(s.completed())cache[s]=o;
}
inline node *build_tree(const State &s){
    init_cache();
    node o;
    _build_tree(s,&o);
    assert(o.child.size()==1);
    assert(o.child.back().size()==1);
    return o.child.back().back();
}
void print_tree(node *o,int dep=0){
    cout<<string(dep,' '),o->s.print();
    for(auto div:o->child){
        for(auto nd:div){
            print_tree(nd,dep+2);
        }
    }
}
//開始寫code 
inline Rule *get_my_Rule(){
    Rule *S=add_rule("S"),*E=add_rule("E"),*L=add_rule("L");
    Rule *list=add_rule("("),*AND=add_rule(")"),*T=add_rule("T");
    S->add({list,E});
    S->add({list,L});
    L->add({E,L});
    L->add({E,AND,E});
    E->add({T});
    E->add({S});
    Rule *GAMMA=add_rule("GAMMA");//一定要有gamma rule當作是最上層的語法
    GAMMA->add({S});
    return GAMMA;
}
vector<string> ans;
bool dfs(node *o){
    if(o->child.empty()){
        if(o->s.r==NameRule["T"])ans.push_back(table[o->s.end].value);
        return 1;
    }
    bool is=o->s.r==NameRule["S"];
    if(is)ans.push_back("(");
    for(auto div:o->child){
        if(div.size()>1)return 0;
        if(!dfs(div[0]))return 0;
    }
    if(is)ans.push_back(")");
    return 1;
}
int n;
string s;
vector<string> tok;
int main(){
    init_Rule();
    Rule *GAMMA=get_my_Rule();
    cin.tie(0);
        ios::sync_with_stdio(0);
    cin>>n;
    cin.get();
    while(n--){
        getline(cin,s);
        State END=parse(GAMMA,lexer(s)).second;
        init_cache();
        node *root=build_tree(END);
        ans.clear();
        if(!dfs(root)){
            cout<<"AMBIGUOUS\n";
        }else{
            string pre;
            for(size_t i=0;i<ans.size();++i){
                if(pre!="("&&pre!=""&&ans[i]!=")")cout<<' ';
                cout<<(pre=ans[i]);
            }
            cout<<'\n';
        }
    }
    return 0;
}

2016年2月20日 星期六

[ IOICAMP2016 ] 動態曼哈頓最短距離

題目:
因為IOICAMP的judge是暫時性的,所以有人備份了題目
http://codingsimplifylife.blogspot.tw/2016/02/ioi-camp-judge-37_4.html

解法:
CDQ分治不會寫,所以就用老派的kd tree去解吧,這裡提供兩種寫法:
  • 第一種寫法是動態的將點進行插入,因為必須要做到動態的插入操作,而一般kd tree不能用旋轉的方式來平衡,所以利用替罪羊樹的概念來平衡。(3.10s)
  •  第二種寫法是把所有操作讀入,把所有要插入的點先建成一顆kd tree,接著倒著作回來,如果遇到插入操作就把點從kd tree裡刪除,但是刪除的速度很慢,所以是壓線過的。(7.16)
兩種寫法如果再kdt.clear()時不做delete操作只把root=0的話會加快約2秒的時間(3.02s跟3.73s)

第一種作法code:
#include<stdio.h>
#include<limits.h>
//using namespace std;
#ifndef SUNMOON_DYNEMIC_KD_TREE
#define SUNMOON_DYNEMIC_KD_TREE
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
template<typename T,size_t kd>//kd表示有幾個維度
class kd_tree{
    public:
        struct point{
            T d[kd];
            inline T dist(const point &x)const{
                T ret=0;
                for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]);
                return ret;
            }
            inline bool operator<(const point &b)const{
                return d[0]<b.d[0];
            }
        };
    private:
        struct node{
            node *l,*r;
            point pid;
            int s;
            node(const point &p):l(0),r(0),pid(p),s(1){}
            inline void up(){
                s=(l?l->s:0)+1+(r?r->s:0);
            }
        }*root;
        const double alpha,loga;
        const T INF;//記得要給INF,表示極大值
        std::vector<node*> A;
        int qM;
        std::priority_queue<std::pair<T,point > >pQ;
        struct __cmp{
            int sort_id;
            inline bool operator()(const node*x,const node*y)const{
                return x->pid.d[sort_id]<y->pid.d[sort_id];
            }
        }cmp;
        void clear(node *o){
            if(!o)return;
            clear(o->l);
            clear(o->r);
            delete o;
        }
        inline int size(node *o){
            return o?o->s:0;
        }
        node* build(int k,int l,int r){
            if(l>r)return 0;
            if(k==kd)k=0;
            int mid=(l+r)/2;
            cmp.sort_id=k;
            std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp);
            node *ret=A[mid];
            ret->l=build(k+1,l,mid-1);
            ret->r=build(k+1,mid+1,r);
            ret->up();
            return ret;
        }
        inline bool isbad(node*o){
            return size(o->l)>alpha*o->s||size(o->r)>alpha*o->s;
        }
        void flatten(node *u,typename std::vector<node*>::iterator &it){
            if(!u)return;
            flatten(u->l,it);
            *it=u;
            flatten(u->r,++it);
        }
        bool insert(node*&u,int k,const point &x,int dep){
            if(!u){
                u=new node(x);
                return dep<=0;
            }
            ++u->s;
            if(insert(x.d[k]<u->pid.d[k]?u->l:u->r,(k+1)%kd,x,dep-1)){
                if(!isbad(u))return 1;
                if((int)A.size()<u->s)A.resize(u->s);
                typename std::vector<node*>::iterator it=A.begin();
                flatten(u,it);
                u=build(k,0,u->s-1);
            }
            return 0;
        }
        inline int heuristic(const int h[])const{
            int ret=0;
            for(size_t i=0;i<kd;++i)ret+=h[i];
            return ret;
        }
        void nearest(node *u,int k,const point &x,T *h,T &mndist){
            if(u==0||heuristic(h)>=mndist)return;
            point now=u->pid;
            int dist=u->pid.dist(x),old=h[k];
            /*mndist=std::min(mndist,dist);*/
            if(dist<mndist){
                pQ.push(std::make_pair(dist,u->pid));
                if((int)pQ.size()==qM+1){
                    mndist=pQ.top().first,pQ.pop();
                }
            }
            if(x.d[k]<u->pid.d[k]){
                nearest(u->l,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest(u->r,(k+1)%kd,x,h,mndist);
            }else{
                nearest(u->r,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest(u->l,(k+1)%kd,x,h,mndist);
            }
            h[k]=old;
        }
        std::vector<point>in_range;
        void range(node *u,int k,const point&mi,const point&ma){
            if(!u)return;
            bool is=1;
            for(int i=0;i<kd;++i)
                if(u->pid.d[i]<mi.d[i]||ma.d[i]<u->pid.d[i]){
                    is=0;break;
                }
            if(is)in_range.push_back(u->pid);
            if(mi.d[k]<=u->pid.d[k])range(u->l,(k+1)%kd,mi,ma);
            if(mi.d[k]>=u->pid.d[k])range(u->r,(k+1)%kd,mi,ma);
        }
    public:
        kd_tree(const T &INF,double a=0.75):alpha(a),loga(log2(1.0/a)),INF(INF){}
        inline void clear(){
            clear(root),root=0;
        }
        inline void build(int n,const point *p){
            clear(root),A.resize(n);
            for(int i=0;i<n;++i)A[i]=new node(p[i]);
            root=build(0,0,n-1);
        }
        inline void insert(const point &x){
            insert(root,0,x,std::__lg(size(root))/loga);
        }
        inline T nearest(const point &x,int k){
            qM=k;
            T mndist=INF,h[kd]={};
            nearest(root,0,x,h,mndist);
            mndist=pQ.top().first;
            pQ=std::priority_queue<std::pair<T,point > >();
            return mndist;/*回傳離x第k近的點的距離*/
        }
        inline const std::vector<point> &range(const point&mi,const point&ma){
            in_range.clear();
            range(root,0,mi,ma);
            return in_range;/*回傳介於mi到ma之間的點vector*/
        }
        inline int size(){return root?root->s:0;}
};
#endif
kd_tree<int,2> kdt(INT_MAX);
int t,n,a;
kd_tree<int,2>::point x;
int main(){
    scanf("%d",&t);
    while(t--){
        kdt.clear();
        scanf("%d",&n);
        while(n--){
            scanf("%d%d%d",&a,&x.d[0],&x.d[1]);
            if(a)printf("%d\n",kdt.nearest(x,1));
            else kdt.insert(x);
        }
    }
    return 0;
}

第二種做法code:
#include<stdio.h>
#include<limits.h>
#include<assert.h>
//using namespace std; 
#ifndef SUNMOON_DYNEMIC_KD_TREE
#define SUNMOON_DYNEMIC_KD_TREE
#include<algorithm>
#include<vector>
template<typename T,size_t kd>
class kd_tree{
    public:
        struct point{
            T d[kd];
            inline T dist(const point &x)const{
                T ret=0;
                for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]);
                return ret;
            }
            inline bool operator<(const point &b)const{
                return d[0]<b.d[0];
            }
        };
    private:
        struct node{
            node *l,*r;
            point pid;
            node(const point &p):l(0),r(0),pid(p){}
        }*root;
        const T INF;
        std::vector<node*> A;
        int s;
        struct __cmp{
            int sort_id;
            inline bool operator()(const node*x,const node*y)const{
                return x->pid.d[sort_id]<y->pid.d[sort_id];
            }
        }cmp;
        void clear(node *o){
            if(!o)return;
            clear(o->l);
            clear(o->r);
            delete o;
        }
        node* build(int k,int l,int r){
            if(l>r)return 0;
            if(k==kd)k=0;
            int mid=(l+r)/2;
            cmp.sort_id=k;
            std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp);
            node *ret=A[mid];
            ret->l=build(k+1,l,mid-1);
            ret->r=build(k+1,mid+1,r);
            return ret;
        }
        inline int heuristic(const int h[])const{
            int ret=0;
            for(size_t i=0;i<kd;++i)ret+=h[i];
            return ret;
        }
        node **mnp;
        int mnk;
        void findmin(node*&o,int d,int k){
            if(!o)return;
            if(!mnp||o->pid.d[d]<(*mnp)->pid.d[d]){
                mnp=&o;
                mnk=k;
            }
            findmin(o->l,d,(k+1)%kd);
            if(d==k)return;
            findmin(o->r,d,(k+1)%kd);
        }
        void nearest_for_erase(node *&u,int k,const point &x,T *h,T &mndist){
            if(u==0||heuristic(h)>=mndist)return;
            point now=u->pid;
            int dist=u->pid.dist(x),old=h[k];
            if(dist<mndist){
                mnp=&u;
                mnk=k;
                if(!(mndist=dist))return;
            }
            if(x.d[k]<u->pid.d[k]){
                nearest_for_erase(u->l,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest_for_erase(u->r,(k+1)%kd,x,h,mndist);
            }else{
                nearest_for_erase(u->r,(k+1)%kd,x,h,mndist);
                h[k]=abs(x.d[k]-u->pid.d[k]);
                nearest_for_erase(u->l,(k+1)%kd,x,h,mndist);
            }
            h[k]=old;
        }
    public:
        kd_tree(const T &INF):INF(INF),s(0){}
        inline void clear(){
            clear(root),root=0;
        }
        inline void build(int n,const point *p){
            clear(root),A.resize(s=n);
            for(int i=0;i<n;++i)A[i]=new node(p[i]);
            root=build(0,0,n-1);
        }
        inline bool erase(point p){
            T mndist=1,h[kd]={};
            nearest_for_erase(root,0,p,h,mndist);
            if(mndist)return 0;
            for(node **o=mnp;;){
                if((*o)->r);
                else if((*o)->l){
                    (*o)->r=(*o)->l;
                    (*o)->l=0;
                }else{
                    delete *o;
                    (*o)=0;
                    --s;
                    return 1;
                }
                mnp=0;
                findmin((*o)->r,mnk,(mnk+1)%kd);
                (*o)->pid=(*mnp)->pid;
                o=mnp;
            }
        }
        inline T nearest(const point &x){
            T mndist=INF,h[kd]={};
            nearest_for_erase(root,0,x,h,mndist);
            return mndist;/*回傳離x最近的點的距離*/
        }
        inline int size(){return s;}
};
#endif
kd_tree<int,2> kdt(INT_MAX);
int t,n;
kd_tree<int,2>::point x[200005],in[200005];
int ans[200005],a[200005],top;
int main(){
    scanf("%d",&t);
    while(t--){
        kdt.clear();
        scanf("%d",&n);
        top=0;
        for(int i=0;i<n;++i){
            scanf("%d%d%d",&a[i],&x[i].d[0],&x[i].d[1]);
            if(!a[i])in[top++]=x[i];
        }
        kdt.build(top,in);
        top=0;
        while(n--){
            if(a[n])ans[top++]=kdt.nearest(x[n]);
            else assert(kdt.erase(x[n]));
        }
        while(top--)printf("%d\n",ans[top]);
    }
    return 0;
}

2016年1月25日 星期一

[ codeforces ] Round #340 (Div. 2) E. XOR and Favorite Number

題目:
http://codeforces.com/contest/617/problem/E
給一個序列a1,a2,a3......an,再給一個k
接下來有m個詢問,給兩個數字l,r,問:
對於所有的i,j滿足l<=i<=j<=r,ai 到 aj所有數字的xor值=k的(i,j)有幾個

解法:
很直接就想到莫隊,關於該算法的實作就不多說了
先把序列做前綴xor再進行處理
注意計數用的陣列大小必須大於2^20 (1000000的二進位是11110100001001000000,但是兩個<1000000的數xor起來可以到11111111111111111111=(2^20)-1)
還有add,sub裡面操作的順序也要注意

code:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define MAXQ 100000
struct Q{
    int l,r,i,block;
    inline bool operator<(const Q &b)const{
        return block==b.block?r<b.r:block<b.block;
    }
}q[MAXQ+5];
int n,m,k;
int s[MAXN+5];
long long ans[MAXQ+5];
int p[(1<<20)+1];
long long cur_ans;
inline void add(int x){
    cur_ans+=p[x^k];
    ++p[x];
}
inline void sub(int x){
    --p[x];
    cur_ans-=p[x^k];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]);
        s[i]^=s[i-1];
    }
    int lim=1+(int)sqrt(n);
    for(int i=0;i<m;++i){
        scanf("%d%d",&q[i].l,&q[i].r);
        --q[i].l;
        q[i].block=q[i].l/lim;
        q[i].i=i;
    }
    sort(q,q+m);
    for(int i=0,L=0,R=-1;i<m;++i){
        while(R<q[i].r)add(s[++R]);
        while(R>q[i].r)sub(s[R--]);
        while(L>q[i].l)add(s[--L]);
        while(L<q[i].l)sub(s[L++]);
        ans[q[i].i]=cur_ans;
    }
    for(int i=0;i<m;++i)printf("%lld\n",ans[i]);
    return 0;
}

2016年1月20日 星期三

[ codeforces ] ACM ICPC 2015–2016, Northeastern European Regional J Jump

題目:
http://codeforces.com/gym/100851
互動題,猜字串遊戲,輸入n表示字串長度,你要輸出一個字串給他
他會輸入你猜的字串的回傳值,只有當猜對的字元數=n/2或n時回傳值才會是猜對的字元數,否則回傳值是0
n<=1000,你要在n+500次內猜出他的字串是什麼

解法:
根據斯特靈(Stirling)公式
可知隨機找出剛好一半字元是正確的機率近似於
幾乎可以在sqrt(n)次內找出剛好一半字元是正確的字串,接下因為字串有一半是錯的,所以可以把字元分成兩堆,設字串為s,分法如下:

分成A、B兩堆
設s[0]屬於A,對於s[1]~s[n-1],把他們分別跟s[0]取not,假設現在是第i個字元
s[0]^=1;
s[i]^=1;
輸出答案進行判斷,如果回傳值仍是n/2表示s[i]屬於A,否則s[i]屬於B
如果過程中出現回傳值=n就結束程式

最後先對A裡面所有字元取not,如果不是答案再把整個字串取not即可
記住記得要清空輸出的緩衝區確保及時輸出
c用fflush(stdout);
c++用cout.flush();

code:
#include<bits/stdc++.h>
using namespace std;
int n,an;
char s[1005];
bool is[1005];
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(;;){
        for(int i=0;i<n;++i){
            s[i]=rand()%2+'0';
        }
        puts(s);fflush(stdout);
        scanf("%d",&an);
        if(an)break;
    }
    if(an==n)return 0;
    s[0]^=1;
    for(int i=1;i<n;++i){
        s[i]^=1;
        puts(s);fflush(stdout);
        scanf("%d",&an);
        if(an==n)return 0;
        if(an)is[i]=1;
        s[i]^=1;
    }
    s[0]^=1;
    for(int i=0;i<n;++i){
        if(is[i])s[i]^=1;
    }
    puts(s);fflush(stdout);
    scanf("%d",&an);
    if(an==n)return 0;
    for(int i=0;i<n;++i){
        s[i]^=1;
    }
    puts(s);fflush(stdout);
    scanf("%d",&an);
    return 0;
}

2016年1月5日 星期二

[ UVA ] 741 - Burrows Wheeler Decoder

題目:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=682

解法:
BWT逆轉換,可以參考Morris的這篇,透過觀察題目範例:

1. A B A N A N
2. A N A B A N
3. A N A N A B
4. B A N A N A
5. N A B A N A
6. N A N A B A
(我們只知道最後一行(設為字串s)的NNBAAA和原字串在第4個位置)

發現我們只能利用排序求出第一行的AAABNN,因為BWT轉換是利用字串rotate,所以可以把s和它結合起來
NA
NA
BA
AB
AN
AN
在排序就可以得到前兩行了
AB
AN
AN
BA
NA
AN
同樣發現因為rotate的關係,所以可以再開頭加上s求出前三行.....以此類推

code:
#include<bits/stdc++.h>
using namespace std;
int main(){
    bool is=0;
    string s;
    for(int p;cin>>s>>p;){
        if(s=="END")break;
        if(is)cout<<endl;
        is=1;
        int n=s.length();
        string a[n];
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)a[j]=s[j]+a[j];
            sort(a,a+n);
        }
        cout<<a[p-1]<<endl;
    }
    return 0;
}