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';
    }
}
張貼者： 於 沒有留言:

TIOJ 1833 - Problem B 陽炎眩亂

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

 還是很普通的disjoint-set

 

 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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int djs[100005];

int F(int a){
    if(djs[a]==a)return a;
    else return djs[a] = F(djs[a]);
}
void U(int a,int b){
    a=F(a);
    b=F(b);
    djs[b]=a;
}
void P(){
    cout<<"djs:";for(int i=1;i<=n;i++)cout<<djs[i]<<" ";cout<<endl;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)djs[i]=i;
    while(m--){
        string s;
        cin>>s;
        if(s[0]=='M'){
            int a,b;
            cin>>a>>b;
            U(a,b);
            // P();
        }
        else{
            int k;
            cin>>k;
            cout<<F(k)<<'\n';
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1312 - 家族

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

 很普通的disjoint-set

 

 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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int djs[10005];

int F(int a){
    if(djs[a]==a)return a;
    else return djs[a] = F(djs[a]);
}
void U(int a,int b){
    a=F(a);
    b=F(b);
    if(b>a)swap(a,b);
    djs[a]=b;
}
void P(){
    cout<<"djs:";for(int i=1;i<=n;i++)cout<<djs[i]<<" ";cout<<endl;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>n>>m){
        memset(djs,0,sizeof(djs));
        for(int i=1;i<=n;i++)djs[i]=i;
        while(m--){
            int a,b;
            cin>>a>>b;
            U(a,b);
            // P();
        }
        int k;
        cin>>k;
        cout<<F(k)<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1013 - Fire in the forest

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

 就火跟人一起BFS就好了
然後人不能走的地方火也不能走
我當初卡這個卡好久 不知道在幹嘛((

 

  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
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

struct pnt{
    int x,y,len;
    pnt():x(0),y(0),len(0){};
    pnt(int xx,int yy,int lll):x(xx),y(yy),len(lll){};
};

string mp[10]={
    "*****************",
    "*...*.......**..*",
    "**..*....*.*.*..*",
    "*......*.**.**.**",
    "*..**...**..**.**",
    "**.....**..*.*..*",
    "*....*..........*",
    "*.....****.*...**",
    "****.*.*........*",
    "*****************"
};
int n,m,t;
int fx,fy,sx,sy,ex,ey;
bool gone[20][20],fgone[20][20];

queue<pnt> fq,mq;

void fWalk(){
    if(fq.empty())return;
    int time = fq.front().len;
    while(fq.size() && fq.front().len==time){
        pnt tmp = fq.front();fq.pop();
        int x = tmp.x,y = tmp.y,len = tmp.len;
        if(!fgone[x+1][y] && (mp[x+1][y]=='.' || mp[x+1][y]=='w') && x+1 <n){fgone[x+1][y]=1;mp[x+1][y]='*';fq.push({x+1,y,len+1});};
        if(!fgone[x-1][y] && (mp[x-1][y]=='.' || mp[x-1][y]=='w') && x-1>=0){fgone[x-1][y]=1;mp[x-1][y]='*';fq.push({x-1,y,len+1});};
        if(!fgone[x][y+1] && (mp[x][y+1]=='.' || mp[x][y+1]=='w') && y+1 <m){fgone[x][y+1]=1;mp[x][y+1]='*';fq.push({x,y+1,len+1});};
        if(!fgone[x][y-1] && (mp[x][y-1]=='.' || mp[x][y-1]=='w') && y-1>=0){fgone[x][y-1]=1;mp[x][y-1]='*';fq.push({x,y-1,len+1});};
    }
}

int meGo(){
    if(mq.empty())return -1;
    int time = mq.front().len;
    while(mq.size() && mq.front().len==time){
        pnt tmp = mq.front();mq.pop();
        int x=tmp.x, y=tmp.y, len=tmp.len; if(mp[x][y]=='*') continue;
        if(mp[x][y]=='!' || (x==ex && y==ey))return len;
        if(!gone[x+1][y] && mp[x+1][y]!='*'){if(mp[x+1][y]!='!'){mp[x+1][y]='w';}if(mp[x+1][y]=='!'){return len+1;}gone[x+1][y]=1;mq.push({x+1,y,len+1});};
        if(!gone[x-1][y] && mp[x-1][y]!='*'){if(mp[x-1][y]!='!'){mp[x-1][y]='w';}if(mp[x-1][y]=='!'){return len+1;}gone[x-1][y]=1;mq.push({x-1,y,len+1});};
        if(!gone[x][y+1] && mp[x][y+1]!='*'){if(mp[x][y+1]!='!'){mp[x][y+1]='w';}if(mp[x][y+1]=='!'){return len+1;}gone[x][y+1]=1;mq.push({x,y+1,len+1});};
        if(!gone[x][y-1] && mp[x][y-1]!='*'){if(mp[x][y-1]!='!'){mp[x][y-1]='w';}if(mp[x][y-1]=='!'){return len+1;}gone[x][y-1]=1;mq.push({x,y-1,len+1});};
    }
    return -1;
}

void P(){
    cout<<"now map:\n";
    for(int i=0;i<n;i++){
        cout<<mp[i]<<endl;
    }
    cout<<endl;
}

void S(){
    fq.push({fx,fy,0});
    mp[fx][fy]='*';
    fgone[fx][fy]=1;
    // cout<<"Init map: ";
    // P();
    for(int time=1;time<t;time++){
        fWalk();
        // P();
    }
    // P();
    // cout<<"pre gone.\n\n";

    mq.push({sx,sy,0});
    gone[sx][sy]=1;
    int cnt=1200;
    while(mq.size()){
        int res = meGo();
        if(res!=-1){
            cout<<res<<endl;
            return;
        }
        fWalk();
        // P();
    }
    cout<<"Help!\n";
}

int main(){
    n=10,m=17;
    fx=rit(),fy=rit(),t=rit(),sx=rit(),sy=rit(),ex=rit(),ey=rit();

    mp[ex][ey]='!';

    S();
}
張貼者： 於 沒有留言:

TIOJ 1355 - 河內之塔-蘿莉塔

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

 普通到不能再普通的河內塔(?

 

 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
#include<bits/stdc++.h>
using namespace std;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
}

int n;
int cnt;

void o(int a,int b){
    printf("#%d : move the dish from #%d to #%d\n",cnt++,a,b);
}

void Hn(int from,int dist,int step,int tmp){
    if(step==1){
        o(from,dist);
        return;
    }
    Hn(from,tmp,step-1,dist);
    o(from,dist);
    Hn(tmp,dist,step-1,from);
    return;
}

int main(){
    cin>>n;
    cnt=1;
    Hn(1,3,n,2);
}
張貼者： 於 沒有留言:

TIOJ 1026 - 惡猿果實

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

 反過來想 一開始先從最大步的開始走 然後每次/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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

string ans;
ll d,mxi;

void walk(){
    if(d>0){
        ans='+'+ans;
        d-=mxi;
    }
    else{
        ans='-'+ans;
        d+=mxi;
    }
    mxi>>=1;
}

int main(){
    cin>>d;
    {
        mxi=1;
        for(;mxi<=d;mxi<<=1){}
        mxi>>=1;
    }
    while(d){
        walk();
    }
    cout<<ans.length()<<'\n'<<ans<<'\n';
}
張貼者： 於 沒有留言:
訂閱： 文章 (Atom)