九省联考2018 D1T1 一双木棋chess 题解

题目链接

当时现场A了这道题,成功以非正式的身份吓到了正式选手。后来听讲解发现好像和我的思路不太一样,所以发一下我的做法

思考方向

考试的时候我就想,这可能是个博弈论,也可能是个DP

博弈论的话由于不是标准的求先手必胜还是必败,所以应该不是了。

那么就是DP了。而且是10*10的,应该是个状压DP。所以先确定了总体思路:状压DP

关于A和B的处理

居然一个格子有两个参数,这样一下就复杂了,要是能变成一个就好了。

所以我试了各种方法(太过复杂不予描述),成功找到了正解:

ans最开始不设为0,设为所有B的和的相反数,然后把格子里A和B加起来就可以正常玩了。

Player1和Player2轮流落子,P1想让结果尽量大,P2落子不计算得分,想让结果尽量小。

如何状压

题目明显是在和我们说每一行棋子一定是左边的一串,并且这一串长度不会超过上面一串。10的二进制位为1010,4位。那么10个10放在一起就是40位,没有超过long long,状压成功。

二进制1010 1001 1000 0111 0110 0101 0100 0011 0010 0001的意思就是第一行10子,二行9子,3行8子,4行7子……10行1子

DP状态的设定

我们肯定不能开1 << 40这么大的DP数组,所以需要离散化。那就DFS一遍枚举所有状态并且用map水一下就好了,反正开O2

我们知道如果一个状态确定了,那轮到谁就也确定了。所以dp[i]就索性设定为状态i下按最优策略博弈还能拿到的分数好了。

但是我比较懒,即使想到了也不想这么写,还不如干脆dp[i][1]为“下一步轮到第1个人走,那么最优策略下还能得到的分数是多少”,dp[i][0]为“下一步轮到第2个人走,那么最优策略下还能得到的分数是多少”

DP的转移方程

dp[now][0] = min(dp[下一个状态][1]);

dp[now][1] = max(dp[下一个状态][0] + 到达状态能得到的分数);

OK,那到达状态能得到的分数怎么办?

到达状态能得到的分数

肯定就是现在的比后来的多出来的那一格的得分了,这个大家看我代码就能明白了,不用多说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//b before
//a after
inline int getX(long long b, long long a) {
a -= b;
for(int i = 1; i <= xlen; ++i) {
if((15ll << ((xlen - i) << 2)) & a) {
return i;
}
}
}
inline int getY(long long b, long long a) {
int x = getX(b, a);
return (a >> ((xlen - x) << 2)) & 15;
}
//unmap是一个逆向离散化的数组
inline int getArr(int b, int a) {
return arr[getX(unmap[b], unmap[a])][getY(unmap[b], unmap[a])];
}

具体实现

由于我这么设的状态,所以逆向连边是肯定的了。

正常来说肯定是要拓扑排序了,但是我弱,考场上并没想到

所以我写了个SPFA。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// luogu-judger-enable-o2 O2不开会80分
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>

template<typename T>
inline void input(T &var) {
char ch = ' ';
T ope = 1;
while((ch < '0' || '9' < ch) && ch != '-') {
ch = getchar();
}
if(ch == '-') {
ope = -1;
ch = getchar();
}
var = 0;
while('0' <= ch && ch <= '9') {
var = var * 10 + ch - '0';
ch = getchar();
}
var *= ope;
}
template<typename T>
inline void output(T var) {
if(var < 0) {
putchar('-');
var = -var;
} else if(var == 0) {
putchar('0');
return;
}
if(var >= 10) {
output(var / 10);
}
putchar(var % 10 + '0');
return;
}

struct Edge {
Edge(int to, Edge *next) : to(to), next(next) { }
Edge *next;
int to;
} *first[300000];

std::map<long long, int> map;
long long unmap[300000];
long long memery[300000][2];
int cnt = 0;
int xlen;
int ylen;
long long ans = 0;
int arr[15][15];

void init();
void build();
long long solve();

int main() {
init();
build();
output(solve() + ans);
return 0;
}

void getMap(int x, int last_y, long long res) {
--x;
map[res << ((xlen - x) << 2)] = ++cnt;
unmap[cnt] = res << ((xlen - x) << 2);
++x;
if(x > xlen) return;
for(int y = 1; y <= last_y; ++y) {
getMap(x + 1, y, (res << 4) | y);
}
return;
}

inline int getYByX(long long res, int x) {
res >>= ((xlen - x) << 2);
res &= 15;
return res;
}

void init() {
input(xlen);
input(ylen);
getMap(1, ylen, 0);
for(int i = 1; i <= xlen; ++i) {
for(int j = 1; j <= ylen; ++j) {
input(arr[i][j]);
}
}
int key;
for(int i = 1; i <= xlen; ++i) {
for(int j = 1; j <= ylen; ++j) {
input(key);
arr[i][j] += key;
ans -= key;
}
}
return;
}

inline void addEdge(int from, int to) {
first[from] = new Edge(to, first[from]);
return;
}

void build() {
std::queue<long long> que;
que.push(1ll << ((xlen - 1) << 2));
static bool vis[300000];
memset(vis, 0, sizeof(vis));
vis[map[1ll << ((xlen - 1) << 2)]] = true;
while(!que.empty()) {
long long now = que.front();
que.pop();
if(getYByX(now, 1) < ylen) {
long long next = now + (1ll << ((xlen - 1) << 2));
//addEdge(map[now], map[next]);
addEdge(map[next], map[now]);
if(!vis[map[next]]) {
que.push(next);
vis[map[next]] = true;
}
}
for(int i = 2; i <= xlen; ++i) {
if(getYByX(now, i - 1) <= getYByX(now, i)) continue;//no <
long long next = now + (1ll << ((xlen - i) << 2));
//addEdge(map[now], map[next]);
addEdge(map[next], map[now]);
if(!vis[map[next]]) {
que.push(next);
vis[map[next]] = true;
}
}
}
return;
}

inline int getX(long long b, long long a) {
a -= b;
for(int i = 1; i <= xlen; ++i) {
if((15ll << ((xlen - i) << 2)) & a) {
return i;
}
}
}
inline int getY(long long b, long long a) {
int x = getX(b, a);
return (a >> ((xlen - x) << 2)) & 15;
}

inline int getArr(int b, int a) {
return arr[getX(unmap[b], unmap[a])][getY(unmap[b], unmap[a])];
}

long long solve() {
memset(memery, -1, sizeof(memery));
addEdge(2, 1);
long long fin = 0;
for(int i = 1; i <= xlen; ++i) {
fin <<= 4;
fin |= ylen;
}
fin = map[fin];
for(int i = 1; i <= cnt; ++i) {
memery[i][0] = 0x7fffffffffffffff;
memery[i][1] = 0x8000000000000000;
}
memery[fin][0] = memery[fin][1] = 0;

std::queue<int> que;
que.push((int)fin);
static bool in_que[300000];
memset(in_que, 0, sizeof(in_que));
while(!que.empty()) {
int now = que.front();
que.pop();
in_que[now] = false;
for(Edge *edg = first[now]; edg != NULL; edg = edg->next) {
bool flag = false;
if(memery[now][1] < memery[edg->to][0]) {
memery[edg->to][0] = memery[now][1];
flag = true;
}
if(memery[edg->to][1] < memery[now][0] + getArr(edg->to, now)) {
memery[edg->to][1] = memery[now][0] + getArr(edg->to, now);
flag = true;
}
if(flag) {
if(in_que[edg->to]) continue;
in_que[edg->to] = true;
que.push(edg->to);
}
}
}
return memery[1][1];
}