yp155136 coding area: 8月 2016

2016年8月29日星期一

(Codeforces) 623B. Array GCD

http://codeforces.com/problemset/problem/623/B

solution : http://codeforces.com/contest/623/submission/20172218

題目大意：給你一個長度n的序列(1<=n<=10^6)，裡面的每個值ai的範圍在[2,10^9]。現在，你可以做兩件事情：(1)刪除掉這個序列的某個子序列(長度<=n-1) 這會花費a * m元，其中m是子序列的長度 (2)把序列的任意值 +1 or -1，把做一次這個動作，會花費b元。在你經過這兩件事情後，你會得到一個新的序列。題目的要求是：使得這個新序列的gcd值 >= 2。

可以注意到的一件事情是說：這個序列一定會包含 a1-1,a1,a1+1, an-1,an,an+1 的其中一個值(也就是說，開頭or尾巴一定有一個可以留下來！)。因此，我們可以dp。一旦上面那六個值中的其中一個選定了，所擁有的質數有確定了！

假設我們擁有的質數是p，我們開三條dp陣列(dp[3][n])，其中dp[0][i]是指一路來在只有做 操作2 的情況下，前i個的最小cost，若無此case，則為INF。dp[1][i]是指在第i個把挖掉的情況下，前i個的最小cost。dp[2]則為在i之前已經刪除一段序列的情況下，前i個的最小值，若無此case，則為INF。

我們先定義 "合法" ：在經過操作後，得到的數字 % p == 0，其中p是上述中，選定的質數。

那麼，我們可以得到以下結論：

dp[0][i] = (如果合法)dp[0][i-1]+費用(沒有做操作2，就是0，其他情況就是b)
dp[1][i] = min( dp[0][i-1] + a, dp[1][i-1] + a)
dp[2][i] = min( (如果合法)dp[0][i-1] + 費用, dp[2][i-1] + 費用 )

如果有看不懂的話，歡迎在下面留言喔~

2016年8月26日星期五

(Codeforces) 623A. Graph and String

http://codeforces.com/problemset/problem/623/A

solution : http://codeforces.com/contest/623/submission/20080880

題目大意：有一個人，他先寫下一個長度n(1<=n<=500)的字串，裡面只包含'a' , 'b' , 'c'。接下來，他把字串中的每個字元視為一個節點，字元符合下面的情況時，會建邊：'a' - 'a' , 'b' - 'b' , 'c' - 'c' , 'a' - 'b' , 'b' - 'c' (也就是說，只要兩個點相等時 or 字母表的相鄰兩個點) 。畫完圖後，他就把字串給擦掉了。隔天，他的朋友看到這張圖，他的朋友希望她能看到原本的字串。請你給出任意一組合法解。

可以先注意到的兩個特性：(1) 'b'可以與任意相接 (2) 'a' - 'c'不相連。

接下來，我們就尋找每個不相連的邊，一個設定成'a'，另外一個設定成'c'，其他如果不相關的通通設定成'b'。如果在過程中，發現有矛盾的情況，那就是不可能發生。

2016年8月25日星期四

Educational Codeforces Round 16

http://codeforces.com/contest/710

想說剛進div.1 ，先打場Educational Round試試手感。結果16min之後就沒再傳code了...

Problems :
pA : http://codeforces.com/contest/710/problem/A
pB : http://codeforces.com/contest/710/problem/B
pC : http://codeforces.com/contest/710/problem/C
pD : http://codeforces.com/contest/710/problem/D
pE : http://codeforces.com/contest/710/problem/E
pF : http://codeforces.com/contest/710/problem/F

My solutions :
pA : http://codeforces.com/contest/710/submission/20047572
pB : http://codeforces.com/contest/710/submission/20048663
pC : http://codeforces.com/contest/710/submission/20051573
pE : http://codeforces.com/contest/710/submission/20142269

題解：

pA :
題目大意：給你一個在西洋棋盤上面的格子，請輸出如果那個格子擺的是King(國王)，他可以走幾步。

基本上可以分三種case : 四個角，邊，中間。判斷方法可以用第一個是'a', 'h'或第二個是 '1','8'等判斷，詳細可以參考我的code。

pB :
題目大意：一個長度n的a序列(1<=n<=3*10^5)，請找出最小的點x，使得|a1-x|+|a2-x| + ... + |an-x|有最小值，如果x有很多解，請輸出最左邊的。

這個比較算是數學解：把a排序，然後輸出中間的點即可。這個算是絕對值圖形的特性。

pC :
題目大意：給你一個奇數n(1<=n<=49)，請製造出一個n*n的矩陣，使得每一行、列、斜邊的和都是奇數。

Jury的解法大概是圖片(一)的樣子，我的解法是：讓每個行、列、斜邊的和都一樣。

圖一：

pE :
題目大意：現在你需要作出n個'a' (1<=n<=10^7)，其中你可以使用三種操作：再任意處插入、刪除一個'a'，這花費了a元、複製貼上目前的字串，這花費'b'元。請求出最小的花費。

這是一題dp題：令dp[i]代表說：有i個'a'的最佳解。則初始化條件為dp[1] = a，遞迴式為：若i%2==0，則dp[i] = max(dp[i-1] + a, dp[i/2] + b) else : dp[i] = max(dp[i-1]+a,max(dp[i/2]+b+a,dp[i/2+1] + b+a)。看code應該會比較清楚XD。

2016年8月22日星期一

Codeforces Round #368 (Div. 2)

經過了好久，終於晉級Div. 1了~~ Candidate Master

希望之後能夠維持穩定再Div.1 ~~

http://www.codeforces.com/contest/707

題目：
pA : http://www.codeforces.com/contest/707/problem/A
pB : http://www.codeforces.com/contest/707/problem/B
pC : http://www.codeforces.com/contest/707/problem/C
pD : http://www.codeforces.com/contest/707/problem/D
pE : http://www.codeforces.com/contest/707/problem/E

My solutions :
pA : http://www.codeforces.com/contest/707/submission/19982541
pB : http://www.codeforces.com/contest/707/submission/19986266
pC : http://www.codeforces.com/contest/707/submission/19987375
pD : http://www.codeforces.com/contest/707/submission/20037472

題解：

pA :
題目大意：給你一個有n*m個像素的圖片(1<=n,m<=100)，每個像素有六種顏色。只要一張圖片中，沒有C , M , Y，就是黑白照片，其他就是彩色照片。

這題主要要小心的部分是字元處理(很多hack神人都利用了這一點)，用scanf的要特別特別特別注意！很容易因為字元就雷掉了。所以我用string XD。

pB :
題目大意：現在有n個城市，m條有權重的邊(1<=n,m<=10^5)，這其中有k個城市(0<=k<=n)是補給站。現在，你必須要選擇一個不是補給站的城市i，以及一個補給站城市j，這兩座城市必須要有路徑相連。現在，你要想辦法使得權重和變成最小，請問有沒有辦法？

仔細想想後會發現：要使得權重和最小，那勢必說要使得經過的城市越少。那倒不如說，直接一個i(上述的i)跟j(上述的j)之間用一條邊連接就好------這就是重點。所以，我們只要拜訪所有的邊，就okay囉~~。複雜度：O(E)。

pC :
題目大意：給你一個直角三角形的任意一個邊，請給出另外兩個邊。

那我假設題目給我的是n好了，若n=1,2，那一定不行(最小的直角三邊行三個邊長是 3,4,5)，最簡單的方法是說：a^2 + n^2 = b^2 ==> n^2 = b^2 - a^2 ==> n^2 = (a-b)(a+b)。那這個時候，我們就可以解聯立解說：a-b=1, a+b=n*n。若這個時候n是偶數，一直除以二，變成奇數即可。(可是我已經忘記我的code到底是如何神奇的運作了，因為這個在我小學六年級的時候就無意間不小心推出來了，所以就直接用，忘記如何解釋了。對於讀者，感到抱歉。)

pD :
題目大意：維護一個n*m書架(1<=n,m<=1000)，q比詢問(1<=q<=10^5)，這q比詢問中，有四種動作：1.把書放到(i,j) 2.把書從(i,j)移掉 3. 把橫列i中，有書的變沒書，沒書的變有書 4. 變成操作k的模樣。

這題解題其實可以用DFS實作：可以想像成這個狀態要前往那些狀態，這樣就可以用DFS了。詳細的話，可以參考我的code。

後記：
我發現，我擁有access to tags了 XD。

2016年8月17日星期三

(UVA) 10731 - Test

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1672

SCC喔！

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

const int MAX_N = 30;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
bool visit[MAX_N];
bool used[MAX_N];
int stamp[MAX_N];
string scc[MAX_N];

inline int f(char c) {
    return c-'A'+1;
}

inline char ff(int x) {
    return x-1+'A';
}

void dfs_for_stamp(int id,int &cur_stamp) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_stamp(tmp,cur_stamp);
    }
    stamp[cur_stamp++]=id;
}

void dfs_for_scc(int id,int num) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if(visit[tmp]==false) dfs_for_scc(tmp,num);
    }
    int len=scc[num].size();
    scc[num] += " ";
    scc[num][len] = ff(id);
}

int main (){
//    freopen("output.txt","w",stdout);
    int n;
    int cases=1;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        if (cases!=1) puts("");
        cases++;
        for (int x=0;MAX_N>x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            visit[x]=false;
            used[x]=false;
            scc[x]="";
        }
        for (int x=0;n>x;x++) {
            string i[6];
            for(int y=0;6>y;y++) cin>>i[y];
            int id=0;
            for (id=0;5>id;id++) {
                used[f(i[id][0])]=true;
                if (i[id]==i[5]) break;
            }
            for (int y=0;5>y;y++) {
                used[f(i[y][0])]=true;
                if (y==id) continue;
                edg[f(i[id][0])].push_back(f(i[y][0]));
                rev_edg[f(i[y][0])].push_back(f(i[id][0]));
            }
        }
        int cur_stamp=1;
        for (int x=1;MAX_N>x;x++) {
            if (visit[x]==false &&used[x]==true) dfs_for_stamp(x,cur_stamp);
        }
        for (int x=0;MAX_N>x;x++) {
            visit[x]=false;
        }
        int num=1;
        for (int x=cur_stamp-1;x>=1;x--) {
//            cout<<"x="<<x<<endl;
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],num++);
            }
        }
//        for (int x=1;num>x;x++) cout<<scc[x]<<endl;
//        cout<<"num="<<num<<endl;
        for (int x=1;num>x;x++) {
            string tmp[MAX_N];
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                tmp[y]=" ";
                tmp[y][0]=scc[x][y];
            }
            sort(tmp,tmp+len);
            scc[x]="";
            for (int y=0;len>y;y++) {
                scc[x] += tmp[y];
            }
        }
        sort(scc+1,scc+num);
        for (int x=1;num>x;x++) {
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                if (y!=0) printf(" ");
                char t=scc[x][y];
                printf("%c",t);
            }
            puts("");
        }
    }
}

(UVA) 247 - Calling Circles

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=183

SCC進化版XD

處理字串那裏比較難啦XD

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

const int MAX_N = 30;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
vector<int> scc[MAX_N];
bool visit[MAX_N];
int stamp[MAX_N];
map<string,int> mp;
string rev_mp[MAX_N];

void dfs_for_stamp(int id,int &cur_stamp) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if(visit[tmp]==false) dfs_for_stamp(tmp,cur_stamp);
    }
    stamp[cur_stamp++]=id;
}

void dfs_for_scc(int id,int num) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_scc(tmp,num);
    }
    scc[num].push_back(id);
}

int main () {
    int n,m;
    int cases=1;
    while (cin >> n >> m) {
        if (!n && !m) break;
        mp.clear();
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            scc[x].clear();
            visit[x]=false;
        }
        int id=1;
        for (int x=0;m>x;x++) {
            string i,j;
            cin >> i >>j;
            if(mp.find(i) == mp.end()) {
                mp[i]=id;
                rev_mp[id++]=i;
            }
            if (mp.find(j) == mp.end()) {
                mp[j]=id;
                rev_mp[id++]=j;
            }
            edg[mp[i]].push_back(mp[j]);
            rev_edg[mp[j]].push_back(mp[i]);
        }
        int cur_stamp=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) {
                dfs_for_stamp(x,cur_stamp);
            }
        }
        for(int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int num=1;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],num++);
            }
        }
        if (cases!=1) cout<<endl;
        cout<<"Calling circles for data set "<<cases++<<":\n";
        for(int x=1;num>x;x++) {
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                if (y!=0) cout<<", ";
                cout<<rev_mp[scc[x][y]];
            }
            cout<<endl;
        }
    }
}

(UVA) 11838 - Come and Go

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2938

也是SCC的應用喔，這題也可以當模板題。

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

const int MAX_N = 2004;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
int stamp[MAX_N];
bool visit[MAX_N];

void dfs_for_stamp(int id,int &cur_depth) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_stamp(tmp,cur_depth);
    }
    stamp[cur_depth++]=id;
}

void dfs_for_scc(int id,int scc) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_scc(tmp,scc);
    }
}

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        if (!n && !m) break;
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            if (k==1) {
                edg[i].push_back(j);
                rev_edg[j].push_back(i);
            }
            else {
                edg[i].push_back(j);
                edg[j].push_back(i);
                rev_edg[i].push_back(j);
                rev_edg[j].push_back(i);
            }
        }
        int cur_depth=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) dfs_for_stamp(x,cur_depth);
        }
        for (int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int scc=0;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) dfs_for_scc(stamp[x],scc++);
        }
        if(scc==1) puts("1");
        else puts("0");
    }
}

(UVA) 11504 - Dominos [SCC]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2499

SCC 模板！

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

typedef pair<int,int> pii;
const int MAX_N = 1e5 + 6;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
int stamp[MAX_N];
int in_scc[MAX_N];
int rudu[MAX_N];
bool visit[MAX_N];

void dfs_for_stamp(int id,int &cur_depth) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_stamp(tmp,cur_depth);
    }
    stamp[cur_depth++]=id;
}

void dfs_for_scc(int id,int scc) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) {
            dfs_for_scc(tmp,scc);
        }
    }
    in_scc[id]=scc;
}

int main () {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            stamp[x]=in_scc[x]=rudu[x]=0;
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[i].push_back(j);
            rev_edg[j].push_back(i);
        }
        int cur_depth=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) dfs_for_stamp(x,cur_depth);
        }
        for (int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int scc=1;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],scc++);
            }
        }
        for (int x=1;n>=x;x++) {
            for (auto i=edg[x].begin();i!=edg[x].end();i++) {
                int tmp=*i;
                if (in_scc[x]!=in_scc[tmp]) rudu[in_scc[tmp]]++;
            }
        }
        int ans=0;
        for(int x=1;scc>x;x++) {
            if (rudu[x]==0) ans++;
        }
        printf("%d\n",ans);
    }
}

2016年8月16日星期二

(UVA) 10765 - Doves and bombs

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1706

割點的強化XD

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 10004;

int low[MAX_N];
int depth[MAX_N];
vector<int> edg[MAX_N];
bool visit[MAX_N];
int cut_vertex[MAX_N];
int son[MAX_N];
pii ans[MAX_N];

void dfs(int id,int cur_depth,int parent) {
low[id]=cur_depth;
visit[id]=true;
depth[id]=cur_depth;
for (auto i=edg[id].begin();i!=edg[id].end();i++) {
int tmp=*i;
if (visit[tmp] ==true) {
if (low[id] > depth[tmp]) {
low[id] = depth[tmp];
}
}
else {
son[id]++;
dfs(tmp,cur_depth+1,id);
if (low[tmp] < low[id]) low[id]=low[tmp];
else if (low[tmp] >= cur_depth && id!=parent){
cut_vertex[id]++;
}
}
}
if (id==parent) cut_vertex[id]=son[id];
}

int main () {
int n,m;
while (scanf("%d %d",&n,&m) != EOF) {
if (!n && !m) break;
for (int x=0;n>x;x++) {
edg[x].clear();
visit[x]=false;
cut_vertex[x] = 1;
son[x]=0;
}
int i,j;
while (scanf("%d %d",&i,&j)) {
if (i==-1&&j==-1) break;
edg[i].push_back(j);
edg[j].push_back(i);
}
dfs(0,1,0);
for (int x=0;n>x;x++) {
ans[x]=make_pair(cut_vertex[x],-x);
}
sort(ans,ans+n);
for (int x=n-1;x>=n-m;x--) {
printf("%d %d\n",-ans[x].second,ans[x].first);
}
puts("");
}
}

(UVA) 796 - Critical Links [割邊 bridge]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=737

裸割邊題，也是一樣用tarjan的low函數，不過這次需要考慮重邊 & 從父親來的節點XD。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e5+6; //assume, not given in the input

int low[MAX_N];
int depth[MAX_N];
bool visit[MAX_N];
vector<int> edg[MAX_N];
pii ans[MAX_N];
int ans_no;
set<pii> path;
set<pii> repeat;

void dfs(int id,int cur_depth,int parent) {
    visit[id]=true;
    low[id]=cur_depth;
    depth[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==true) {
            if (depth[tmp] < low[id] && tmp!=parent) {
                low[id] = depth[tmp];
            }
            else if (depth[tmp]<low[id] && repeat.find(make_pair(tmp,id))!=repeat.end()) {
                low[id] = depth[tmp];
            }
        }
        else {
            dfs(tmp,cur_depth+1,id);
            if (low[tmp] < low[id]) low[id]=low[tmp];
        }
    }
    if (id!=parent && low[id]>=cur_depth) {
        ans[ans_no++]=make_pair(min(parent,id),max(parent,id));
    }
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            edg[x].clear();
            visit[x]=false;
            ans_no=0;
        }
        ans_no=0;
        for (int x=0;n>x;x++) {
            int i,j;
            scanf("%d (%d)",&i,&j);
            for (int y=0;j>y;y++) {
                int k;
                scanf("%d",&k);
                edg[i].push_back(k);
                edg[k].push_back(i);
            }
        }
        for (int x=0;n>x;x++) {
            if (visit[x]==false) dfs(x,1,x);
        }
        sort(ans,ans+ans_no);
        printf("%d critical links\n",ans_no);
        for (int x=0;ans_no>x;x++) {
            printf("%d - %d\n",ans[x].first,ans[x].second);
        }
        puts("");
    }
}

(UVA) 315 - Network [割點 cut vertex]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=251

裸割點題：用Tarjan算法的 low 函數：不經過父節點所能到達的最上面深度！實作就看code吧！這裡不需要考慮重邊的部分，因為是cut vertex，重邊的話回到父節點，其實沒差。

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

const int MAX_N = 103;

int low[MAX_N];
int depth[MAX_N];
vector<int> edg[MAX_N];
bool visit[MAX_N];
int cut_vertex[MAX_N];
int son[MAX_N];

void dfs(int id,int cur_depth,int parent) {
    visit[id]=true;
    depth[id]=cur_depth;
    low[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==true) {
            if (depth[tmp]<low[id] && tmp!=parent) low[id]=depth[tmp];
        }
        else {
            son[id]++;
            dfs(tmp,cur_depth+1,id);
            if (low[tmp] < low[id]) low[id]=low[tmp];
            else if (low[tmp] >= cur_depth && id!=1) cut_vertex[id]=1;
        }
    }
    if (id==1 && son[1]>1) cut_vertex[1]=1;
}

int main (){
//    freopen("output.txt","w",stdout);
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        for (int x=0;n>=x;x++) {
            visit[x]=false;
            edg[x].clear();
            cut_vertex[x]=0;
            son[x]=0;
        }
        int p;
        while (scanf("%d",&p)) {
            if (p==0) break;
            int t;
            char c;
            while (scanf("%d%c",&t,&c)) {
                edg[t].push_back(p);
                edg[p].push_back(t);
                if (c=='\n') break;
            }
        }
        dfs(1,1,1);
        int sum=0;
        for (int x=1;n>=x;x++) {
            sum += cut_vertex[x];
        }
        printf("%d\n",sum);
    }
}

(UVA) 11686 - Pick up sticks

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2733

主要是topological sort啦。比較需要注意的是N比較大(10^6)，要小心不要co爛掉。

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

const int MAX_N = 1e6 + 3;

int rudu[MAX_N];
vector<int> edg[MAX_N];
queue<int> que;
bool visit[MAX_N];
int ans[MAX_N];

int main (){
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        if (!n && !m) break;
        for(int x=0;n>=x;x++) {
            edg[x].clear();
            rudu[x]=0;
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[i].push_back(j);
            rudu[j]++;
        }
        int id=0;
        for (int x=1;n>=x;x++) {
            if (rudu[x]==0 && visit[x]==false) {
                que.push(x);
                while (!que.empty()) {
                    int t=que.front();
                    ans[id++]=t;
                    visit[t]=true;
                    que.pop();
                    for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                        int tmp=*i;
                        rudu[tmp]--;
                        if (rudu[tmp]==0) que.push(tmp);
                    }
                }
            }
        }
        if (id!=n) puts("IMPOSSIBLE");
        else {
            for(int x=0;id>x;x++) {
                printf("%d\n",ans[x]);
            }
        }
    }
}

(UVA) 11080 - Place the Guards

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2021

用 "二分染色法" ，用BFS實作(DFS也可XD)

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

const int MAX_N = 203;
const int MAX_M = 10004;

int visit[MAX_N];
vector<int> edg[MAX_N];
queue<int> que;

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            visit[x]=-1;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[j].push_back(i);
            edg[i].push_back(j);
        }
        int ans=0;
        for (int x=0;n>x;x++) {
            if (visit[x]==-1) {
                que.push(x);
                int _[2]={1,0};
                visit[x]=0;
                while (!que.empty()) {
                    int t=que.front();
                    que.pop();
                    for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                        int tmp=*i;
                        if (visit[tmp]==-1) {
                            visit[tmp] = 1-visit[t];
                            _[visit[tmp]]++;
                            que.push(tmp);
                        }
                        else if (visit[tmp]==visit[t]) {
                            ans=-1;
                        }
                    }
                }
                if (ans==-1) continue;
                else if (_[1]==0) ans+=_[0];
                else ans+= min(_[0],_[1]);
            }
        }
        printf("%d\n",ans);
    }
}

Codeforces Round #364 (Div. 2)

http://codeforces.com/contest/701

題目：
pA : http://codeforces.com/contest/701/problem/A
pB : http://codeforces.com/contest/701/problem/B
pC : http://codeforces.com/contest/701/problem/C
pD : http://codeforces.com/contest/701/problem/D
pE : http://codeforces.com/contest/701/problem/E
pF : http://codeforces.com/contest/701/problem/F

My solutinos :
pA : http://codeforces.com/contest/701/submission/19329561
pB : http://codeforces.com/contest/701/submission/19331053
pC : http://codeforces.com/contest/701/submission/19333717
pE : http://codeforces.com/contest/701/submission/19878556
pF : http://codeforces.com/contest/701/submission/19885355

題解：

pA :
題目大意：給你n個數字(2<=n<=100，n是偶數)，請你找出n/2個配對(兩個數字為一個配對)，使得這n/2個配對總和一樣(題目保證有解！)。

那就隨便唬爛一下就好啦XD。看你要開陣列存 or 開set or O(N^2)解，都可以。

pB :
題目大意：現在有一個n*n (1<=n<=10^5)的棋盤，以及m (1<=m<=min(n^2,10^5) 個城堡(相當於中國象棋的車(ㄐㄩ))。每當下一個城堡時，問說有多少個格子不會被攻擊到。

這題有很多解法。我的作法是：紀錄現在有多少個row和col是有被城堡佔領的。之後再用數學解即可。

pC :
題目大意：給你一個序列(只包含大寫字母、小寫字母)，請求出最短的長度，使得這個長度包含所有出現的字元。

使用爬行法(two pointers)！就okay囉！

pD :
聽說有數學解，可是我看不太懂。有好心人士願意告訴我的話，歡迎在下面留言 ^_^。

pE :
題目大意：給你一棵大小n(2<=n<=10^5)的樹。這其中有2*k個點是大學。你現在要把這些點連接起來，使得經過的路線總和最大！

有一個很神奇的想法是說：有一條邊，把樹分成兩半：一半有s個大學，另外一半就有2*k-s個大學，其中，這一條邊一定會經過min(s,2*k-s)次(有點greedy的想法，大概就是走越多越好的概念)。基於這個想法，我可以DFS整棵樹，在過程中，我就維護子樹有大學的數量，在求出答案，就okay了~~。

pF :
題目大意：給你一張有權重的無向圖(不保證強連通，可能有重邊、自環)，v個節點(1<=v<=1000)，e條邊(1<=e<=30000)，以及兩個點s,t (s!=t)。現在你可以清掉c個邊(0<=c<=2)，使得s不能走到t且清除的邊中，權重和最小。

分成三種case討論吧！

case 1 : c=0 --- 直接輸出答案即可！代表在圖中s走不到t。

case 2 : c=1 ：那你先找出任一一條s到t的路徑(看是要BFS or DFS皆可，總之想辦法用到O(E) )，接下來，找出圖中的割邊( 使用 low 函數)，如果割邊是在那條路徑上的話，那就有可能是答案。

case 3 : c=2 ：先試著移除掉你找過那條路徑上的任意一個邊，然後再從新的圖中，再找出一條s到t 的路徑，然後再找一次割邊，跟case 1一樣。

期望複雜度：O(n * m)，我寫的複雜度：O(n*m*lgn)

Codeforces Round #365 (Div. 2)

http://codeforces.com/contest/703

題目：
pA : http://codeforces.com/contest/703/problem/A
pB : http://codeforces.com/contest/703/problem/B
pC : http://codeforces.com/contest/703/problem/C
pD : http://codeforces.com/contest/703/problem/D
pE : http://codeforces.com/contest/703/problem/E

My solutions :
pA : http://codeforces.com/contest/703/submission/19618133
pB : http://codeforces.com/contest/703/submission/19622667
pD : http://codeforces.com/contest/703/submission/19768229

題解：

pA :
題目大意：判斷比賽的輸贏！

認真判斷即可！

pB :
題目大意：有n個城市(3<=n<=10^5)，每個城市都有各自的ci值(1<=ci<=10000)。如果兩個城市i,j中間有連接，那連接的weight就是ci * cj。一開始，會形成一個環：城市 1 連接城市 2 ，城市 2 連接城市 3 ， ...... 城市 n 連接城市 1。而這其中，會有k個首都(1<=k<=n)，首都城市會與所有其他城市相連。問你說：整張圖的權重和。

先開一個sum值：記錄所有城市的ci和。接下來，對於每個首都j，ans += cj * (sum - cj)，接下來再把環補起來。最後，我們要想辦法處理首都相乘的問題：可以利用數學公式(a1 + a2 + ..... + an) ^ 2 = (a1^2 + a2^2 + ..... + an^2) + 2 * (兩兩相乘) 解決。

pD :
題目大意：給你一個長度n(1<=n<=10^6)的序列，你只需要支援區間查詢[l,r]：區間中，出現偶數個數的數字的XOR和。

先把查詢按照右界排序。然後需要維護一個東西：前綴XOR和。之後答案就是前綴XOR和 ^ (區間distinct的數字XOR和)。至於如何維護後面的東西：線段樹啦！

2016年8月15日星期一

(UVA) 10004 - Bicoloring

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=945

BFS一番即可XD

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

const int MAX_N = 203;

int w[MAX_N][MAX_N];
int col[MAX_N];

int main () {
int n;
while (scanf("%d",&n) != EOF) {
if (!n) break;
int m;
scanf("%d",&m);
memset(w,0,sizeof(w));
for (int x=0;m>x;x++) {
int i,j;
scanf("%d %d",&i,&j);
w[i][j] = w[j][i] = 1;
}
queue<int> que;
que.push(0);
memset(col,-1,sizeof(col));
bool ans=true;
while (!que.empty()) {
int t=que.front();
que.pop();
for (int x=0;n>x;x++) {
if (w[t][x]==1 && col[x]==-1) {
col[x] = 1-col[t];
que.push(x);
}
else if (w[t][x]==1 && col[x]==col[t]) ans=false;
}
}
printf("%s\n",ans?"BICOLORABLE.":"NOT BICOLORABLE.");
}
}

Codeforces Round #367 (Div. 2)

http://codeforces.com/contest/706

題目；
pA : http://codeforces.com/contest/706/problem/A
pB : http://codeforces.com/contest/706/problem/B
pC : http://codeforces.com/contest/706/problem/C
pD : http://codeforces.com/contest/706/problem/D
pE : http://codeforces.com/contest/706/problem/E

My Solutions :
pA : http://codeforces.com/contest/706/submission/19788234
pB : http://codeforces.com/contest/706/submission/19790222
pC : http://codeforces.com/contest/706/submission/19797359
pD(1) : http://codeforces.com/contest/706/submission/19806189
pD(2) : http://codeforces.com/contest/706/submission/19823423

題解：
pA :
題目大意：給你一個固定點(a,b)以及n個(1<=n<=100)其他的點(xi,yi)。請求出其他點到固定點的最小距離。

那你就開一個計算距離的函式，認真維護距離一番。記得輸出答案的時候，要指定輸出的位數：(1) #include <iomanip>中，cout << fixed<<setprecision(位數) << num<<endl; (2) printf("%.位數f", num);

pB :
題目大意：給你n個數字(1<=n<=10^5)，q比詢問(1<=q<=10^5)，求有多少個數字小於等於mi。

求upper_bound或lower_bound即可XD。用法可以參考我的code

pC :
題目大意：現在有n個字串(1<=n<=10^5)，你可以對字串i做出反轉這個動作，可是每當你反轉，就要花費ci。現在你需要把這n個字串按照字典序排好(C++ string中的大於&小於)，請求出最少的花費。

那你就開一個兩條dp陣列(dp[2][MAX_N])，初始值是INF(無限大)，dp[0][i]的意思是說以沒有反轉的i為結尾的最小cost，dp[1][i]是有反轉的。

遞迴的方式：dp[0][i] = min(dp[0][i] , dp[1][i-1] if valid , dp[0][i-1] if valid) , dp[1][i] = min(dp[0][i-1] + c[i] if valid, dp[1][i-1] + c[i] if valid)。

pD :
題目大意：維護一個很像multiset的資料結構：支援(1)插入 (2)刪除 (3)查詢，查詢是指給你一個數字i，求出max(i ^ j) ，其中j是在mutliset裡面，^是XOR運算。一開始multiset就有0

第一份solution的解法：用treap維護multiset。接下來，對於"查詢"，先有一個greedy的概念：如果可以在越高的位元XOR成1，那就在越高的位元XOR成1。又因為數字範圍在1~10^9之間，所以位元最多只有lg 10^9 = 32次，對於每個位元，我把它分成0和1的部分，進行query，有比較高的XOR值，就先往那裏走，走到最後，就是答案了。複雜度 O(q lg q lg 10^9)

第二份：用trie存multiset，然後按照trie認真走即可 <(_ _)>

2016年8月10日星期三

(UVA) 11060 - Beverages

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2001

題目大意：給你n個東西及m個限制。要求輸出符合m個限制的排列。如果兩兩間沒有特別的限制(在m裡面的限制)，用輸入的順序判斷。

sol : 把寫topological 的 queue 改成 priority_queue 即可！！！

因為，用min heap的話，就變成可以維護相對關係了！

複雜度：O(n lg n) //map + heap

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

const int MAX_N = 103;

string s[MAX_N];
int rudu[MAX_N];
map<string,int> mp;
vector<int> edg[MAX_N];

int main () {
// freopen("output.txt","w",stdout);
//好久沒用cin XD ;
int n;
int cases=1;
while (scanf("%d",&n) != EOF) {
mp.clear();
for (int x=0;n>x;x++) {
rudu[x]=0;
edg[x].clear();
}
for (int x=0;n>x;x++) {
cin >> s[x];
mp[s[x]] = x;
}
int m;
scanf("%d",&m);
for (int x=0;m>x;x++) {
string a,b;
cin >> a >> b;
rudu[mp[b]] ++;
edg[mp[a]].push_back(mp[b]);
}
printf("Case #%d: Dilbert should drink beverages in this order:",cases++);
priority_queue<int,vector<int> , greater<int> > que;
for (int x=0;n>x;x++) {
if (rudu[x] == 0) que.push(x);
}
while (!que.empty()) {
int t=que.top();
que.pop();
cout<<' '<<s[t];
for (vector<int>::iterator i=edg[t].begin();i!=edg[t].end();i++) {
int tmp=*i;
rudu[tmp]--;
if (rudu[tmp] == 0) que.push(tmp);
}
}
puts(".\n");
}
}

(UVA) 11094 - Continents

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=203

注意事項：國王代表的點是陸地，其他都是水！！！

我是用DFS，其實也可以用BFS

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

const int MAX_N = 23;

char s[MAX_N][MAX_N];
int mp[MAX_N][MAX_N];

int dfs(int x,int y,int n,int m) {
mp[x][y] = 0;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
int ret=1;
for (int i=0;4>i;i++) {
int tx=(x + dx[i]), ty=(m+y+dy[i]) % m;
if (0<=tx && tx<n && mp[tx][ty] == 1) {
mp[tx][ty] = 0;
ret += dfs(tx,ty,n,m);
}
}
return ret;
}

int main () {
int n,m;
while (scanf("%d %d",&n,&m) != EOF) {
memset(mp,0,sizeof(mp));
getchar();
for (int x=0;n>x;x++) {
scanf("%s",s[x]);
}
int sx,sy;
scanf("%d %d",&sx,&sy);
for (int x=0;n>x;x++) {
for (int y=0;m>y;y++) {
mp[x][y] = (s[x][y] == s[sx][sy] ? 1 : 0);
}
}
dfs(sx,sy,n,m);
int ans=0;
for (int x=0;n>x;x++) {
for (int y=0;m>y;y++) {
if (mp[x][y] == 1) ans = max(ans,dfs(x,y,n,m));
}
}
printf("%d\n",ans);
}
}

(UVA) 11906 - Knight in a War Grid

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3057

注意事項：
騎士從(0,0)開始走。 每到他可以走到的點 ，他會計算說，有多少個點可以走到這裡。記得，他可以走到(0,0) 。輸出有多少偶數 & 奇數。

於是乎，debug好久，終於AC了

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

#define S second
#define F first
#define MP make_pair
typedef pair<int,int> pii;
const int MAX_N = 203;

int mp[MAX_N][MAX_N];
int can[MAX_N][MAX_N];

int f(int x,int y,int n,int m) {
if (mp[x][y] == 0) return 0;
int dx[8] = {n,n,-n,-n,m,m,-m,-m},dy[8] = {m,-m,m,-m,n,-n,n,-n};
int ret=0;
for (int i=0;8>i;i++) {
//1-->okay
int tx=x + dx[i],ty=y+dy[i];
if (0<=tx && 0<=ty && mp[tx][ty] == 1) ret++;
}
return (n==m || n==0 || m==0 ? ret/2 : ret);
}

int main () {
// freopen("output.txt","w",stdout);
int T;
scanf("%d",&T);
for (int qq=1;T>=qq;qq++) {
printf("Case %d: ",qq);
int a,b,n,m;
scanf("%d %d %d %d",&a,&b,&n,&m);
memset(mp,0,sizeof(mp));
memset(can,0,sizeof(can));
can[0][0] = 1;
for (int x=0;a>x;x++) {
for (int y=0;b>y;y++) {
mp[x][y]= 1;
}
}
int q;
scanf("%d",&q);
while (q--) {
int x,y;
scanf("%d %d",&x,&y);
mp[x][y] = 0;
}
int even=0,odd=0;
queue<pii> que;
que.push(MP(0,0));
while (!que.empty()) {
pii tmp = que.front();
que.pop();
int t=f(tmp.F,tmp.S,n,m);
if (t!=0 && t%2==0 || t==0 && tmp == MP(0,0)) even++;
else if (t%2==1) odd++;
int dx[8] = {n,n,-n,-n,m,m,-m,-m},dy[8] = {m,-m,m,-m,n,-n,n,-n};
int x=tmp.F, y=tmp.S;
// cout<<endl<<x<<" "<<y<<endl;
for (int i=0;8>i;i++) {
int tx=x + dx[i],ty=y+dy[i];
if (0<=tx && 0<=ty && mp[tx][ty] == 1 && can[tx][ty] == 0) {
que.push(MP(tx,ty));
can[tx][ty] = 1;
}
}
}
printf("%d %d\n",even,odd);
}
}
/*
1
11 53 0 7
4
4 12
0 18
7 46
1 46
*/

訂閱：文章 (Atom)

2016年8月29日 星期一

2016年8月26日 星期五

2016年8月25日 星期四

2016年8月22日 星期一

2016年8月17日 星期三

2016年8月16日 星期二

2016年8月15日 星期一

2016年8月10日 星期三