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

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

\begin{aligned} &给定集合mask,求解 F(mask)= \sum_{x\subseteq mask}^{}x \end{aligned}

我们定义状态 $d p [m a s k] [i]$ 为mask的二进制子集中，前i个数字与mask不同，并且满足 $x\&mask==x$ 的值。那么我们能得出状态转移方程式
$F(mask,i)=\begin{cases}F(mask,i-1)&mask\oplus2^i==0\\F(mask,i-1)+F(mask\oplus2^i,i-1)&mask\oplus2^i==2^i\end{cases}$

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