yp155136 coding area

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");
    }
}

訂閱：文章 (Atom)

2016年8月29日 星期一

2016年8月26日 星期五

2016年8月25日 星期四

2016年8月22日 星期一

2016年8月17日 星期三

2016年8月29日星期一

2016年8月26日星期五

2016年8月25日星期四

2016年8月22日星期一

2016年8月17日星期三