# 某岛

… : "…アッカリ～ン . .. . " .. .
May 15, 2012

## PKU Campus 2012

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

## Problem C. Lausanne Capitale Olympique

### Analysis:

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

void bfs(){
RST(d), d[0] = 1, q[head = 0] = 0, tail = 1;

while (head < tail){

int u = q[head++];

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


。。重新整理。。

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:

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/