杭电多校第一场第三题 Backpack(异或dp+bitset）

问题描述

爱丽丝有一个容量背包m她现在想用一些物品填充！
爱丽丝有n项目，每个项目都有一个卷v我和值w我.
是否可以从n个项目中选择多个项目，以使背包完全装满（即体积的总和等于背包容量）？如果是这样，当背包装满时，背包中物品值的最大异或总和是多少？

输入

第一行包含整数T(T≤10)- 测试用例的数量。
每个测试用例的第一行包含 2 个整数n，m（1≤n，m<2^10)— 物品数量，背包容量。
下一个n行，每行包含 2 个整数v我,w我(1≤v我,w我<2^10)— 项目的数量和价值。 

输出

对于每个测试用例，输出一行，如果背包无法填充，只需输出一行“-1”，否则输出最大的XOR总和。

示例输入

1 5 4 2 4 1 6 2 2 2 12 1 14

示例输出

14

思路（照搬标程思路） ：用bitset建立dp数组(f)在每一个bitset元素（f[j])中存储一个01串，某一位为1表示这个位置对应的容量m的异或和可以为j,用g数组拷贝f，然后每次加入一个容量v相当于把g左移v（相当于体积增加v时异或和为j的情况）状态转移为f[j]|=g[j^m1]  （感谢多校教我做人，孩子再也不敢了）

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
const int N=1050;
int n,m;
bitset<N> f[N],g[N];

void init(){
		for(int i=0;i<=1024;i++){
			f[i].reset();
		}
		f[0][0]=1;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		init();
		for(int i=0;i<n;i++){
			int v,m1;
			cin>>v>>m1;
			for(int j=0;j<1024;j++){
				g[j]=f[j]; 
				g[j]<<=v;//此时g为初状态
			}
			for(int j=0;j<1024;j++){
				f[j]|=g[j^m1];//此时f为末状态也就是(j^m1)^m1==j 注：“（）”内为初状态 
			}
		}
		int ans=-1;
		for(int i=0;i<1024;i++){
			if(f[i][m]) ans=i;
		}
		cout<<ans<<endl;
	}
	return 0;
}