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/

Posted by xiaodao
Category: 算法竞赛
Tags: 施工中