PKU Campus 2012

http://poj.openjudge.cn/campus2012/

Problem A. Hand Evaluation

Brief description:

略。)

Analysis:

簽到。)

Problem C. Lausanne Capitale Olympique

Brief description:

給定一個圖,問是否從源點出發,到任意點的最短路徑和次短路徑的長度相差不超過 1 。。。

Analysis:

做一次 bfs() 對所有不在最短路徑樹中的邊,如果連接兩點的層次一樣則同時標記這兩個頂點。。如果一高一低則標記高點。。
返回標記的頂點數是否 == n。

const int N = 10009;

VI adj[N]; MIB used[N]; int q[N], d[N], head, tail;
bool bj[N]; int cnt;
int n, m;


void init(){
    REP(i, n) CLR(adj[i]), CLR(used[i]);
    int x, y; REP(i, m){
        RD(x, y); --x, --y;
        adj[x].PB(y), adj[y].PB(x);
    }
}



void bfs(){
    RST(d), d[0] = 1, q[head = 0] = 0, tail = 1;
    
    while (head < tail){
        
        int u = q[head++];
        
#define v adj[u][i]
        
        REP(i, SZ(adj[u])) if (!d[v]){
            d[v] = d[u] + 1, used[u][v] = used[v][u] = true;
            q[tail++] = v;
        }
    }
}

void tick(int x){
    if (!bj[x]) bj[x] = true, ++cnt;
}

int check(){
    RST(bj); bj[0] = true, cnt = 1;
    
    REP(u, n) REP(i, SZ(adj[u])) if (!used[u][v]){
        if (d[u] == d[v]) tick(u), tick(v);
        else tick(d[u] > d[v] ? u : v);
    }
    
    
    return cnt == n;
}

int main(){
    while (scanf("%d %d", &n, &m) != EOF){
        init(); bfs();
        cout << check() << endl;
    }
}

Problem F. Game

。。先寫個程序暴力一下 SG 。。。

const int N = 1024;
int SG[N], n;
VI tmp;

int mex(VI& tmp){
    if (tmp[0] != 0) return 0;
    FOR(i, 1, SZ(tmp)) if (tmp[i] - tmp[i-1] != 1){
        return tmp[i-1] + 1;
    }
    return tmp[SZ(tmp) - 1] + 1;
}

int main(){
    
    freopen("out.txt", "w", stdout);
    
    n = 1024;
   
    SG[0] = 1, SG[1] = 0;

    FOR(i, 2, n){
        CLR(tmp); REP_1(j, i/2) tmp.PB(SG[i - j] ^ SG[i - 2 * j]);
        SRT(tmp); tmp.resize(unique(ALL(tmp)) - tmp.begin()); SG[i] = mex(tmp);
    }
    
    REP(i, n){
        if (!SG[i] && !SG[i+1]) cout << endl;
        cout << SG[i];
    }
}

稍微整理下得到以下數據。。

1
0
010
012210
010
012214414412210
010
012210
01
001221441441221771771221771771221441441221
001
001221
001
001221441441221
001
001221
001
001221441441221771771221771771221441441221881881221881881221441441221881881221881881221441441221771771221771771221441441221
001
001221
001
001221441441221
001
001221
001
001221441441221771771221771771221441441221
001
001221
001
001221441441221
001
001221
001
00122144144122177177122177177122144144122188188122188188122144144122188188122188188122144144122177177122177177122144144122111111111112211111111111221441441221111111111122111111111112214414412217717712217717712214414412211111111111221111111111122144144122111111111112211111111111221441441221771771221771771221441441221881881221881881221441441221881881221881881221441441221771771221771771221441441221

這樣規律性就已經顯現了。。中間的 Pattern 類似某種樹狀數組的東西。。
中間又出現了 1, 2, 5, 14, 51, 152 這樣的數列。。(差分一下是 a[n] = 3n – 1)。。。
。。重新整理。。

const int N = 1<<10;
int SG[N], n;
VI tmp;

int mex(VI& tmp){
    if (tmp[0] != 0) return 0;
    FOR(i, 1, SZ(tmp)) if (tmp[i] - tmp[i-1] != 1){
        return tmp[i-1] + 1;
    }
    return tmp[SZ(tmp) - 1] + 1;
}

int main(){
    
    freopen("out.txt", "w", stdout);
    
    n = N;
    
    
    SG[0] = 1, SG[1] = 0;

    FOR(i, 2, n){
        CLR(tmp); REP_1(j, i/2) tmp.PB(SG[i - j] ^ SG[i - 2 * j]);
        SRT(tmp); tmp.resize(unique(ALL(tmp)) - tmp.begin()); SG[i] = mex(tmp);
    } 
    
    
    int cnt = 0; REP(i, n){
        printf("%c", (SG[i] <= 10 ? '0' : ('A' - 10)) + SG[i]);
        if (!SG[i]){
            if (++cnt&1) cout << endl;
        }
    }
}

Problem H. Gugle Seating

Brief description:

給一個N*M的矩陣,每個位置上可以有電腦(2)或者椅子(1)或者空(0)。如下面的矩陣

3 4
2 2 1 2
0 1 2 2
2 2 2 1

每個工程師需要佔用一個椅子 + 兩個和椅子相鄰且成直角關係的電腦。如:

1 2
2

問最多能安排多少個工程師進來。電腦只能同時給一個人,椅子也是。

Analysis:

S -> (奇數列) 電腦-> 人 -> (偶數列) 電腦 -> T
中間椅子拆點以保證每個椅子只會被計數一次。

https://gist.github.com/lychees/7306034

References:

http://roosephu.github.io/2013/04/07/TC-575/