题解 | #Forsaken喜欢玩自走棋#

经典SOS dp问题。考虑到本题源自小白月赛，可能出题人本意也是给大伙介绍介绍科技，那我就简单来讲下什么是SOS dp。
如果觉得自己的英文还过的去的话强烈推荐阅读SOSdp出处的这篇博客
SOS指的是the Sum over Subsets，即子集的求和，该算法就是用动态规划的方法来快速求解如下问题

我们定义状态$dp[mask][i]dp[mask][i]$为mask的二进制子集中，前i个数字与mask不同，并且满足 的值。那么我们能得出状态转移方程式

当然，第一次看见这个的你应该会挺懵的，不知道是怎么推出来的,我简单的解释下，当子集的第i位与mask的第i位相同时，$F(mask,i)\mathrm{自}\mathrm{动}\mathrm{退}\mathrm{化}\mathrm{为}F(mask,i-1)F(mask,i)自动退化为F(mask,i-1)$所以两个式子里都含有一个$F(mask,i-1)F(mask,i-1)$，这个相信大家都没问题，当mask的第i位为1且和x的第i位不同的时候，此时的值是不是就可以理解为$F(mask\oplus 2^i,i-1)F(mask\backslash oplus2^i,i-1)$,完全符合定义是不是，那么状态转移方程式就解决了。 还是不懂的话我还有一计，请诸君看图 假设我们有i个元素，那么请问我们有多少个子集呢？答案是显然的$2^{i}2^i$个，那么，我们去掉其中一个元素，我们的子集个数是不是就变成了$2^{i-1}2^\{i-1\}$个，假如我们以此为依据进行dp，设$F(mask)F(mask)$是所有子集的和,那么不就是$F(mask)=F(mask)+F(mask\oplus 2^i)F(mask)=F(mask)+F(mask\backslash oplus2^i)$,其中i是最高位1的位置。那是不是就可以解释我们的状态转移方程式了。 好了，解释完毕，上代码！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int n;
ll dp[1 << 21];
int main() 
{
	scanf("%d",&n);
	int tot = 1 << 20;
	for(int i = 1; i <= n; i++) 
    {
		int s,v;scanf("%d%d",&s,&v);
		s ^= (tot - 1);
		dp[s] += v;
	}
	for(int i = 0; i < 20; i++)
		for(int j = 0; j < tot; j++)
			if(j >> i & 1) dp[j] += dp[j ^ (1 << i)];
	ll mx = -1e18;
	int res = -1;
	for(int i = 0; i < tot; i++) 
    {
		if(dp[i] > mx) 
        {
			mx = dp[i];
			res = i;
		} 
        else if(dp[i] == mx) 
			res = max(res,i);
	}
	printf("%d %lld\n",(tot - 1) ^ res,mx);
	return 0;
}
/*需要注意的是，我们要对限制取反，因为没有限制的我们可以随便变，有限制的不能随意变，有
限制的地方应该是0，没限制的地方应该是1*/