A. 井字棋##
记忆化搜索水过。当 (9) 个格子，每个有未讨论、黑、白三个状态时，一个较大的搜索总次数是两万左右。但实际由于双方轮流出牌，并且一旦获胜就终止游戏，实际上的状态数只有 (5000) 左右。 (f_S) 表示当前局面的白方胜利、失败、或者平局。考虑后面能到的状态 (S') 如果有一个是胜利，则当前状态胜利。否则如果有一个是平局，则当前状态平局。除此之外，就是失败了。
#include <cstdio>
#include <cstring>
using namespace std;
int f[50000], A[15], G[15];
char str[15];
inline int hs(int *arr)
{
int s = 0;
for (int i = 0; i < 9; ++i)
s = s * 3 + arr[i];
return s;
}
int ck(int *arr, int a, int b, int c, int &d)
{
if (arr[a]==0&&arr[b]==0&&arr[c]==0) return d = 2;
if (arr[a]==1&&arr[b]==1&&arr[c]==1) return d = 1;
return d = 0;
}
void dfs(int *A, int s, bool p)
{
int t;
if (f[s] != -1) return;
if (ck(A,0,1,2,t)||ck(A,3,4,5,t)||ck(A,6,7,8,t)||ck(A,0,3,6,t)||ck(A,1,4,7,t)||ck(A,2,5,8,t)||ck(A,0,4,8,t)||ck(A,2,4,6,t)) {
if (t == 1)
f[s] = 1;
else
f[s] = 0;
return;
}
bool ee = 0, possi = 0;
for (int i = 0; i < 9; ++i) {
if (A[i] == 2) {
A[i] = p;
int tmp = hs(A);
dfs(A, tmp, p ^ 1);
if (f[tmp] == p)
f[s] = p;
if (f[tmp] == 2)
ee = 1;
possi = 1;
A[i] = 2;
}
}
if (!possi)
f[s] = 2;
else if (f[s] == -1)
f[s] = ee ? 2 : p ^ 1;
return;
}
int main()
{
// freopen("well.in", "r", stdin);
// freopen("well.out", "w", stdout);
int T;
for (int i = 0; i < 9; ++i)
A[i] = 2;
memset(f, -1, sizeof f);
dfs(A, hs(A), 0);
scanf("%d", &T);
while (T--) {
scanf("%s%s%s", str, str + 3, str + 6);
for (int i = 0; i < 9; ++i) {
if (str[i] == 'O')
G[i] = 0;
else if (str[i] == 'X')
G[i] = 1;
else
G[i] = 2;
}
int tmphs = hs(G);
if (f[tmphs] == 0)
printf("O
");
else if (f[tmphs] == 1)
printf("X
");
else if (f[tmphs] == 2)
printf("E
");
else {
for (int hh = 0; hh <= -4; ++hh);
}
}
return 0;
}
B. 午餐##
状态 (f_{i,j}) 表示第 (i) 个面包处于 (j) 状态时，([1, i-1]) 这些人的选择是否合法。状态有 (4) 个：被 (i) 吃、被 (i-1) 吃、同时被两人吃、不被吃。然后讨论一下可以转移到 (f_{i+1, j'}) 。由于要记录答案，所以 (f_{i+1,j'} =j) ，这样最后可以倒着更新答案。说起来略复杂，具体见代码吧 Orz 。
#include <stdio.h>
#include <ctype.h>
#include <string.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<typename T>
void rd(T &num)
{
char tt;
bool flag = 0;
while (!isdigit((tt = GC)));
num = tt - '0';
while (isdigit(tt = GC))
num = num * 10 + tt - '0';
return;
}
template<typename T>
void pt(T num)
{
if (num < 0) putchar('-'), num = -num;
char sss[20];
int top = 0;
do sss[++top] = (num % 10 + '0');
while (num /= 10);
while (top)
putchar(sss[top--]);
putchar(' ');
return;
}
const int _N = 1200000;
int A[_N], f[_N][4], ans[_N], N;
bool test(int t)
{
memset(f, -1, sizeof f);
f[1][t] = 0;
for (int i = 1; i <= N; ++i) {
if (~f[i][0]) {
if (A[i] <= A[i + 1]) f[i + 1][1] = 0;
if (A[i] * 2 <= A[i + 1]) f[i + 1][3] = 0;
}
if (~f[i][1]) {
if (A[i] <= A[i + 1] * 2) f[i + 1][1] = 1;
if (A[i] <= A[i + 1]) f[i + 1][3] = 1;
}
if (~f[i][2]) {
if (A[i] >= A[i + 1]) f[i + 1][0] = 2;
if (A[i] * 2 >= A[i + 1]) f[i + 1][2] = 2;
}
if (~f[i][3]) {
if (A[i] >= A[i + 1] * 2) f[i + 1][0] = 3;
if (A[i] >= A[i+1])f[i + 1][2] = 3;
}
}
if (~f[N + 1][t]) {
for (int i = N + 1; i >= 1; --i) {
if (t == 1) ans[i - 1] = i;
else if (t == 2) ans[i] = i;
else if (t == 3) ans[i] = ans[i - 1] = i;
t = f[i][t];
}
for (int i = 1; i <= N; ++i)
pt(ans[i] > N ? ans[i] - N : ans[i]);
return 1;
}
return 0;
}
int main()
{
rd(N);
for (int i = 1; i <= N; ++i)
rd(A[i]);
A[N + 1] = A[1];
for (int i = 0; i < 4; ++i) {
if (test(i)) break;
}
return 0;
}
C. 泰拉瑞亚##
单调栈 (O(nm)) 水过 40 分。正解是分块 + 线段树维护。