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
