2018年6月28日 星期四

IOI 2008 Day 2 - Linear Garden

耶我又來更新了(# 最近開始在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的字體改的跟上面一樣好了。
張貼者： 於 沒有留言:

2018年6月22日 星期五

Hackerrank - WCS8 - Tree Coordinates

怕爆 上一篇文是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.... 看起來總算是值得了(?
張貼者： 於 沒有留言:

2016年11月10日 星期四

TIOJ 1297 - 第三題　發人的經驗獎勵

http://tioj.infor.org/problems/1297

 其實直接除基本上就好了(?
但是因為是浮點數 怕會有誤差啥的
所以求出原本的值之後怕爛掉所以在那附近掃一下就好了

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main(){
    int d;
    while(cin>>d){
        if(d<0){cout<<"stupid\n";continue;}
        if(d==0){cout<<"0\n";continue;}
        int res = (int)(((long double)d)*100/101)-2;
        for(;res<1026;res++){
            if((int)(((long double)res)*101/100)==d) break;
        }
        if(res<0 || res>1024)cout<<"stupid\n";
        else cout<<res<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1126 - 尋找對稱字串

http://tioj.infor.org/problems/1126

 長度短短的 $n^2$ 硬幹就好了

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int mx=0;
        for(int i=0;i<(int)s.length();i++){
            for(int j=0;i-j>=0 && i+j<(int)s.length();j++){
                if(s[i-j]==s[i+j]){
                    mx=max(mx,2*j+1);
                    continue;
                }
                else{
                    mx=max(mx,2*j-1);
                    break;
                }
            }
        }
        for(int i=0;i<(int)s.length();i++){
            for(int j=0;i-j>=0 && i+1+j<(int)s.length();j++){
                if(s[i-j]==s[i+1+j]){
                    mx=max(mx,2*j+2);
                    continue;
                }
                else{
                    mx=max(mx,2*j);
                    break;
                }
            }
        }
        cout<<mx<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1110 - [入門] Bat-Bogey

http://tioj.infor.org/problems/1110

統計統計就好



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;

int alp[30];

int main(){
    int n;
    cin>>n;
    while(n--){
        memset(alp,0,sizeof(alp));
        int k;
        cin>>k;
        string s;
        cin>>s;
        int mx=0;
        for(int i=0;i<k;i++){
            alp[s[i]-'a']++;
            mx=max(mx,alp[s[i]-'a']);
        }
        for(int i=0;i<26;i++){
            if(alp[i]==mx){
                cout<<(char)(i+'a');
            }
        }
        cout<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1047 - C.邏輯計算機

http://tioj.infor.org/problems/1047

 照著優先順序做事就好 做完的就把運算元清掉
然後把運算子的地方換成答案

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin>>s && s[0]!='E'){
        bool nt=0;
        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='!'){
                nt=!nt;
                s[i]=' ';
            }
            if(s[i]=='0' && nt){
                s[i]='1';
                nt=0;
            }
            if(s[i]=='1' && nt){
                s[i]='0';
                nt=0;
            }
        }

        // cout<<"not processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='*'){
                int j,k;
                for(j=i;j>=0 && s[j]!='1' && s[j]!='0';j--){}
                for(k=i;k<(int)s.length() && s[k]!='1' && s[k]!='0';k++){}
                int jj=s[j]-'0';
                int kk=s[k]-'0';
                int res=jj&kk;
                // cout<<"process and with jj="<<jj<<" and kk="<<kk<<". res="<<res<<endl;
                s[i]=res+'0';
                s[j]=' ';
                s[k]=' ';
            }
        }

        // cout<<"and processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='+'){
                int j,k;
                for(j=i;j>=0 && s[j]!='1' && s[j]!='0';j--){}
                for(k=i;k<(int)s.length() && s[k]!='1' && s[k]!='0';k++){}
                int jj=s[j]-'0';
                int kk=s[k]-'0';
                int res=jj|kk;
                s[i]=res+'0';
                s[j]=' ';
                s[k]=' ';
            }
        }

        // cout<<"all processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='1' || s[i]=='0'){
                cout<<s[i]<<'\n';
            }
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1030 - Floor Machine

http://tioj.infor.org/problems/1030

 greedy做事就好
為了節省樓層 所以每個樓層如果能讓兩個胖虎的歌聲都存在就好(當然那層不能有人)
所以讓大的排在一起 空隙就會比較小

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int r[100005];

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    while(cin>>n && n){
        for(int i=0;i<n;i++){
            cin>>r[i];
        }
        sort(r,r+n);
        ll ans=1;
        for(int i=0;i<n;i++){
            ans+=r[i];
        }
        ans+=r[n-1];
        cout<<ans<<'\n';
    }
}
張貼者： 於 沒有留言:
訂閱： 意見 (Atom)