自动搬运

查看原文

来自洛谷，原作者为

	Werner_Yin For the things that make you sad, one day, you will laugh out and say it.

搬运于2025-08-24 22:22:25，当前版本为作者最后更新于2020-07-26 16:06:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道博弈论DP 的交互题。

暴力

我们可以设状态为

$f[i][j]$

表示当 x 为 $i$ 时，y 为 $j$ 时的走法，当

$f[i][j] = 0$时为必输。

于是：

$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$ ,于是我们可以这样表示状态：

$f[i][j][k]$ :

当 $y = i,x = 2^j*3^k$ 时 的方案。

预处理一下$2$，$3$ 的幂就行。

改造一下方程即可。

代码

蒟蒻第一次写非IO的交互题，长见识了。

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];
	}
}