code雜記: 2018

耶我又來更新了(# 最近開始在virtual一些IOI題不過這禮拜都在組server 結果2008的Day 2完全是荒廢狀態雖然在打Day 2的時候確實有錄影不過因為太廢了連我都不忍心看下去(X) 後來整場打下來只有銅廢到不行這題在賽中還只拿了20分而已也是Day 2唯一的20分(掩面) 先附個連結 [Linear Garden](https://contest.yandex.com/ioi/contest/567/problems/D/) ### 題目：定義如果一個01序列是好的，那麼這個序列的所有連續子序列的01個數差不能超過2。現在給你一個好的01序列，問你他是所有相同長度當中，所有的好的01序列照字典序排序之後第幾大。字串長度$N \leq 10^6$，輸出答案模$M$，$7 \leq M \leq 10^7$。 ### 不負責題解：一開始寫了某種不能有連續三個同樣的出現的DP，然後00100就爛掉了。後來發現如果把0的看成-1，1的看成+1，那麼前綴和最多只能出現三種數字，這下就好辦了，因為範圍侷限在`-2~2`之間了。不過在 virtual 的時候被某種正的做反的做字典序，然後是前綴和還是後綴和搞到快煩死(#)就拿了個暴力分20就撤了，連個完整的小測資$N \leq 40$都沒吃下來。後來今天先寫了一下 Codeforces 再回來想這題，五分鐘左右就想到了，延續前綴和的想法，然後試著DP。先想一下DP會長成什麼樣子。假設前綴只有`0,1,2`兩種，那麼`1`就會從`0,2`轉，`0,2`就會從`1`轉，看起來有公式可以處理掉，不過先不管。接下來設`dp[i][j]`代表如果自由長度還剩下`i`，此時前綴是`j`的話還有幾種作法，所以可以列出類似這樣的東西： ``` al012[i][0]=al012[i-1][1]; al012[i][1]=(al012[i-1][0]+al012[i-1][2])%m; al012[i][2]=al012[i-1][1]; ``` 然後邊界條件是`dp[0][$]=1`。另外還有`-1,0,1`跟`-2,-1,0`兩種： ``` al901[i][0]=al901[i-1][1]; al901[i][1]=(al901[i-1][0]+al901[i-1][2])%m; al901[i][2]=al901[i-1][1]; al890[i][0]=al890[i-1][1]; al890[i][1]=(al890[i-1][0]+al890[i-1][2])%m; al890[i][2]=al890[i-1][1]; ``` 也有只有`0,1`或`-1,0`的可能性，所以： ``` al01[i][0]=al01[i-1][1]; al01[i][1]=al01[i-1][0]; al90[i][0]=al90[i-1][1]; al90[i][1]=al90[i-1][0]; ``` 這樣只要在掃到`1`的時候假設這格是`0`然後看一下是否合法跟這種case會讓答案加多少就好了。 ....... 我到底在幹嘛。上面三段看起來根本一模一樣，而且每次都是變兩倍。下面兩個根本從頭到尾都是1。所以最後的code其實根本超短。

int n,m;
int p2[1000006];

int main(){
    cin>>n>>m;
    string s; cin>>s;
    p2[0]=1; for(int i=1;i<=n;++i)p2[i]=(p2[i-1]<<1)%m;
    int ans=0,pre=0,mx=0,mn=0;
    for(int i=1;i<=n;++i){
        if(s[i-1]=='P'){
            int tpre=pre+1,tmx=max(mx,tpre),tmn=min(mn,tpre);
#define get(a,b) (p2[(((a)+((b)==1))>>1)])
            if(tmn>=0 && tmx<=2)(ans+=get(n-i,tpre))%=m;
            if(tmn>=-1&& tmx<=1)(ans+=get(n-i,tpre+1))%=m;
            if(tmn>=-2&& tmx<=0)(ans+=get(n-i,tpre+2))%=m;
            if(tmn>=0 && tmx<=1)--ans;
            if(tmn>=-1&& tmx<=0)--ans;
        }
        if(s[i-1]=='L')++pre; else --pre;
        mx=max(mx,pre); mn=min(mn,pre);
    }
    cout<<(ans+1+m)%m<<endl;
}

另外這題字串內容是`L`跟`P`，不過不重要。恩.... 找機會把整份code的字體改的跟上面一樣好了。

怕爆上一篇文是2016/11/10的事了

一時興起回來寫個一篇至於之後會不會繼續更新就再說吧

這題是第一次國培的回家作業其中一題（夭壽上一篇文的時候我還沒進二階www）
重心剖分總之還是不太熟寫了大概四個小時才寫掉

[Tree Coordinates](https://www.hackerrank.com/contests/world-codesprint-8/challenges/tree-coordinates/problem)
### 題目：定義樹上的距離$d(x,y)$就是會經過的邊數，那麼對於兩個點對$(x1,y1), (x2,y2)$的距離就是$d(x1,x2)+d(y1,y2)$。給定一棵樹跟一堆點對，求所有點對對當中距離最遠的那個，輸出距離。
樹上點數$N \leq 75000$，點對數量$M \leq 75000$。
### 不負責題解(?)： ~~既然都說是重心剖分了就先建個重心樹出來吧。~~
那麼對於每個點對$(x,y)$，把y紀錄在x，接下來遍歷一次原樹，在喵點的時候就把所有點對對的x座標的lca為喵點的點對對做過一次(饒舌)~~，這樣就做完了~~。
具體來講，我們在增加一個點對的時候，可以在重心樹上y的位置插入一個$dep[x]$的值，在查詢時就可以直接在重心樹上查離查詢的y距離最大的那個值了（這個距離包含樹上距離跟點值的加權）。不過要注意，為了避免查詢到lca實際上小於自己的點對的答案，merge子樹時要query完一整顆子樹再一次加進去。
另外在重心樹上查詢的時候，可能會需要（至少我要）掃過所有的子樹，這樣如果有太陽就會炸的很慘，所以要建虛點讓每個點的度數保持在定值下。

上code OwO

#define up(x,y) (x=max(x,y))

vector<int> qy[235005],wk,cG[235005];
vector<pair<int,int>> G[235005];
int sz[235005],mxch[235005],ctpa[235005],dep[235005],dis[235005],last[235005],dtc[16][235005],ictd[235005],allval[235005],myval[235005],tpval[235005];
bitset<235005> inct;

void dfs1(int now,int pa){
    wk.pb(now);
    for(pair<int,int> p:G[now]){
        if(inct[p.first] || p.first==pa)continue;
        dis[p.first]=dis[now]+p.second;
        dfs1(p.first,now);
        sz[now]+=sz[p.first];
        mxch[now]=max(mxch[now],sz[p.first]);
    }
    ++sz[now];
}

void dfs1_5(int now,int pa,int dep,int nowd){
    dtc[dep][now]=nowd;
    for(pair<int,int> p:G[now]){
        if(p.first==pa)continue;
        if(inct[p.first])continue;
        dfs1_5(p.first,now,dep,nowd+p.second);
    }
}

int cd(int now,int pa,int dep){
    dfs1(now,now);
    int cen=-1;
    for(int i:wk)if(max(mxch[i],int(wk.size())-sz[i])<=int(wk.size())/2)cen=i;
    dfs1_5(cen,cen,dep,0);
    ictd[cen]=dep;
    ctpa[cen]=pa;
    inct[cen]=1;
    for(int i:wk){
        sz[i]=mxch[i]=0;
    }
    wk.clear();
    for(pair<int,int> p:G[cen]){
        if(inct[p.first])continue;
        dis[p.first]=p.second;
        int chcen=cd(p.first,cen,dep+1);
        cG[cen].pb(chcen);
    }
    return cen;
}

void dfs2(int now,int pa){
    for(pair<int,int> p:G[now]){
        if(p.first==pa)continue;
        dep[p.first]=dep[now]+p.second;
        dfs2(p.first,now);
        sz[now]+=sz[p.first];
    }
    sz[now]+=qy[now].size();
}

set<int> _add_modify_point;
void clearct(){
    for(int i:_add_modify_point){
        allval[i]=-999999;
        tpval[i]=-999999;
        myval[i]=-999999;
    }
    _add_modify_point.clear();
}
void add(int x,int v){
    int ox=x,prv=x;
    up(myval[x],v);
    x=ctpa[x];
    while(x){
        up(tpval[prv],v+dtc[ictd[x]][ox]);
        up(allval[x],v+dtc[ictd[x]][ox]);
        _add_modify_point.insert(x);
        _add_modify_point.insert(prv);
        prv=x;
        x=ctpa[x];
    }
}
int query(int x,int v=-999999){
    int prv=x,ox=x;
    v=max(v,allval[x]);
    v=max(v,myval[x]);
    x=ctpa[x];
    while(x){
        for(int cch:cG[x]){
            if(cch==prv)continue;
            v=max(v,dtc[ictd[x]][ox]+tpval[cch]);
        }
        v=max(v,dtc[ictd[x]][ox]+myval[x]);
        prv=x;
        x=ctpa[x];
    }
    return v;
}

int ans;
vector<pair<int,int>> *dfs3(int now,int pa,bool clean){
    sort(G[now].begin(),G[now].end(),[&](const pair<int,int> &a,const pair<int,int> &b){ 
        if(b.first==pa)return true;
        if(a.first==pa)return false;
        return sz[a.first]<sz[b.first]; });
    vector<vector<pair<int,int>>*> rec;
    for(pair<int,int> p:G[now]){
        if(p.first==pa){
            __is_end:;
            vector<pair<int,int>>* rt;
            if(rec.size()){
                rt=rec.back();
                rec.pop_back();
            }
            else rt=new vector<pair<int,int>>();
            for(auto *v:rec){
                for(auto &p:*v){
                    int Q=query(p.second);
                    ans=max(ans,Q+dep[p.first]-dep[now]*2);
                }
                for(auto &p:*v){
                    add(p.second,dep[p.first]);
                }
            }
            for(auto &sec:qy[now]){
                int Q=query(sec);
                ans=max(ans,Q-dep[now]);
            }
            for(auto &sec:qy[now]){
                add(sec,dep[now]);
            }
            for(auto *v:rec){
                if(v->size()>rt->size())swap(rt,v);
                for(auto &p:*v)rt->pb(p);
                delete v;
            }
            for(auto &sec:qy[now]){
                rt->eb(now,sec);
            }
            return rt;
        }
        else{
            clearct();
            vector<pair<int,int>> *rt=dfs3(p.first,now,p!=G[now].back());
            rec.pb(rt);
            if(p==G[now].back())goto __is_end;
        }
    }
    assert(0);
}

int main(){
    CPPinput;
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;++i)last[i]=i;
    int N=n;
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        int nu=++N,nv=++N;
        G[last[u]].eb(nu,0); G[last[v]].eb(nv,0);
        G[nu].eb(last[u],0); G[nv].eb(last[v],0);
        G[nu].eb(nv,1); G[nv].eb(nu,1);
        last[u]=nu, last[v]=nv;
    }
    int root=cd(1,0,1);
    while(m--){
        int x,y; cin>>x>>y;
        qy[x].pb(y);
    }
    dep[1]=1;
    dfs2(1,1);
    dfs3(1,1,0);
    cout<<ans<<endl;
}

順便還花了一個小時在搞新的style.... 看起來總算是值得了(?

code雜記

2018年6月28日星期四

IOI 2008 Day 2 - Linear Garden

2018年6月22日星期五

Hackerrank - WCS8 - Tree Coordinates

網誌存檔

2018年6月28日 星期四

IOI 2008 Day 2 - Linear Garden

2018年6月22日 星期五

Hackerrank - WCS8 - Tree Coordinates

2018年6月28日星期四

2018年6月22日星期五