HDU 4678 Mine
对于每个空白区域，求SG值。
最后异或起来等于0，先手必败。
#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
#define MAXN 1010
#define oo 1234567890
int arr[MAXN][MAXN];
bool vis[MAXN][MAXN];
int n, m;
int dg, bk;
int sg[MAXN * MAXN][];
int go[][] = { { , }, { -, }, { , }, { , - }, { -, - },
{ -, }, { , - }, { , } };
bool isIn(int x, int y) {
return x >= && x < n && y >= && y < m;
}
int SG(int digit, int blank) {
if (sg[digit][blank] == -) {
int x, y;
x = y = -;
if (blank) {
x = SG(, );
}
if (digit) {
y = SG(digit - , blank);
}
for (int i = ;; i++) {
if (i != x && i != y) {
sg[digit][blank] = i;
break;
}
}
}
return sg[digit][blank];
}
void dfs(int x, int y) {
vis[x][y] = true;
if (arr[x][y] > ) {
dg++;
} else if (arr[x][y] == ) {
bk = ;
int nx, ny;
for (int i = ; i < ; i++) {
nx = x + go[i][];
ny = y + go[i][];
if (isIn(nx, ny) && !vis[nx][ny]) {
dfs(nx, ny);
}
}
}
}
int main() {
int T;
int ca = ;
int x, y;
int i, j, k;
int res;
memset(sg, -, sizeof(sg));
sg[][] = ;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &k);
memset(arr, , sizeof(arr));
while (k--) {
scanf("%d%d", &x, &y);
arr[x][y] = -oo;
}
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (arr[i][j] < ) {
for (k = ; k < ; k++) {
x = i + go[k][];
y = j + go[k][];
if (isIn(x, y)) {
arr[x][y]++;
}
}
}
}
}
res = ;
memset(vis, false, sizeof(vis));
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (!vis[i][j] && arr[i][j] == ) {
dg = bk = ;
dfs(i, j);
res ^= SG(dg, bk);
}
}
}
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
if (!vis[i][j]) {
dg = bk = ;
dfs(i, j);
res ^= SG(dg, bk);
}
}
}
if (res) {
printf("Case #%d: Xiemao\n", ca++);
} else {
printf("Case #%d: Fanglaoshi\n", ca++);
}
}
return ;
}
HDU 4679 Terrorist’s destroy
dp[i][0]表示i为根的最长链。
dp[i][1]表示i为根的次长链。
dp[i][2]表示i为根的第三长链。
#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
#define oo 0x7FFFFFFF
using namespace std;
int first[MAXN], next[MAXN], v[MAXN], cost[MAXN], id[MAXN], e;
int dp[MAXN][];
bool vis[MAXN];
int res, idx;
void addEdge(int x, int y, int val, int idx) {
cost[e] = val;
id[e] = idx;
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
void dfs(int x) {
vis[x] = true;
dp[x][] = dp[x][] = dp[x][] = ;
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
dfs(y);
if (dp[y][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[x][];
dp[x][] = dp[y][] + ;
} else if (dp[y][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[y][] + ;
} else if (dp[y][] + > dp[x][]) {
dp[x][] = dp[y][] + ;
}
}
}
}
void search(int x, int pre) {
int tmp;
vis[x] = true;
if (pre != -) {
if (dp[x][] + == dp[pre][]) {
if (dp[pre][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[x][];
dp[x][] = dp[pre][] + ;
} else if (dp[pre][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[pre][] + ;
} else if (dp[pre][] + > dp[x][]) {
dp[x][] = dp[pre][] + ;
}
} else {
if (dp[pre][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[x][];
dp[x][] = dp[pre][] + ;
} else if (dp[pre][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[pre][] + ;
} else if (dp[pre][] + > dp[x][]) {
dp[x][] = dp[pre][] + ;
}
}
}
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
if (dp[y][] + == dp[x][]) {
tmp = dp[x][] + dp[x][];
} else {
tmp = dp[x][];
if (dp[y][] + == dp[x][]) {
tmp += dp[x][];
} else {
tmp += dp[x][];
}
}
tmp = cost[i] * max(dp[y][] + dp[y][], tmp);
if (tmp < res) {
res = tmp;
idx = id[i];
} else if (tmp == res && idx > id[i]) {
idx = id[i];
}
search(y, x);
}
}
}
int main() {
int T;
int ca = ;
int n;
int i;
int x, y, val;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
e = ;
memset(first, -, sizeof(first));
for (i = ; i < n; i++) {
scanf("%d%d%d", &x, &y, &val);
addEdge(x, y, val, i);
addEdge(y, x, val, i);
}
res = oo;
memset(vis, false, sizeof(vis));
dfs();
memset(vis, false, sizeof(vis));
search(, -);
printf("Case #%d: %d\n", ca++, idx);
}
return ;
}
HDU 4681 String
分别枚举D在A和B中的起点，可以暴力得到最短终点。
枚举任意两个起点与终点，通过dp可以求得两端的LCS。
#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 1010
using namespace std;
char a[MAXN], b[MAXN], c[MAXN];
vector<pair<int, int> > p1, p2;
int f[MAXN][MAXN], g[MAXN][MAXN];
void cal(char a[], char c[], vector<pair<int, int> >&p) {
int i, j, k;
int la = strlen(a + );
int lc = strlen(c + );
p.clear();
for (i = ; i <= la; i++) {
k = ;
if (a[i] != c[k]) {
continue;
}
for (j = i; j <= la; j++) {
if (a[j] == c[k]) {
k++;
}
if (k > lc) {
break;
}
}
if (k > lc) {
p.push_back(make_pair(i, j));
}
}
}
int main() {
int T;
int ca = ;
int ans;
int i, j;
int la, lb, lc;
scanf("%d", &T);
while (T--) {
scanf(" %s %s %s", a + , b + , c + );
la = strlen(a + );
lb = strlen(b + );
lc = strlen(c + );
cal(a, c, p1);
cal(b, c, p2);
ans = ;
if (!(p1.empty() || p2.empty())) {
memset(f, , sizeof(f));
memset(g, , sizeof(g));
for (i = ; i <= la; i++) {
for (j = ; j <= lb; j++) {
if (a[i] == b[j]) {
f[i][j] = f[i - ][j - ] + ;
} else {
f[i][j] = max(f[i - ][j], f[i][j - ]);
}
}
}
for (i = la; i > ; i--) {
for (j = lb; j > ; j--) {
if (a[i] == b[j]) {
g[i][j] = g[i + ][j + ] + ;
} else {
g[i][j] = max(g[i + ][j], g[i][j + ]);
}
}
}
for (i = ; i < (int) p1.size(); i++) {
for (j = ; j < (int) p2.size(); j++) {
ans = max(ans,
lc + f[p1[i].first - ][p2[j].first - ]
+ g[p1[i].second + ][p2[j].second + ]);
}
}
}
printf("Case #%d: %d\n", ca++, ans);
}
return ;
}