题解 P6612 【[POI2012]LIC-Bidding】
Werner_Yin
·
·
题解
这是一道博弈论DP 的交互题。
暴力
我们可以设状态为
f[i][j]
表示当 x 为 i 时，y 为 j 时的走法，当
于是：
$f[i][j] =
-
0 (i + j >= n )
-
1 (f [1][i+j] = 0)
-
2 (f[i*2][j] = 0)
-
3 (f[i*3][j] = 0)
但是,这肯定MLE了。
优化
注意到，x 可以表示为 2^i*3^j ,于是我们可以这样表示状态：
当 $y = i,x = 2^j*3^k$ 时 的方案。
预处理一下$2$，$3$ 的幂就行。
改造一下方程即可。
# 代码
蒟蒻第一次写非IO的交互题，长见识了。
```cpp
int f[30010][16][11] = {0},k = 0;
int p2[16],p3[11];
extern "C" {
extern int _opt(int n, int x, int y) {
if(k == 0){
p2[0] = 1,p3[0] = 1;
for(int i = 1;i <= 15;i++) p2[i] = p2[i-1]*2;
for(int i = 1;i <= 10;i++) p3[i] = p3[i-1]*3;
for(int i = n;i >= 0;i--){
for(int j = 15;j >= 0;j--){
for(int k = 10;k >= 0;k--){
if(p2[j] * p3[k] + i >= n) f[i][j][k] = 0;
else{
if(!f[i][j + 1][k]) f[i][j][k] = 2;
if(!f[i][j][k+1]) f[i][j][k] = 3;
if(!f[ i+p2[j]*p3[k] ][0][0]) f[i][j][k] = 1;
}
}
}
}
k = 1;
}
int xx2 = 0,xx3 = 0;
while(x%2 == 0 && x > 0){x /= 2;xx2++;}
while(x%3 == 0 && x > 0){x /= 3;xx3++;}
return f[y][xx2][xx3];
}
}
```