[diary of supplementary questions] [2022 Hangdian summer school 1] c-backpack

Pro

https://acm.hdu.edu.cn/showproblem.php?pid=7140

Sol

$f_{i,j,k}$ Before presentation i Items , XOR sum j, The volume is k Whether there is a plan for

Then the state transfer equation is $f_{i,j,k}=f_{i-1,j,k}|f_{i-1,j\oplus v,k-w}$

Use the scrolling array to roll out the first dimension , use bitset Optimize the last dimension

About g[j]=f[j]<<x explain ： The use of shift left here can be understood as , When the first $i$ Secondary mobility $v_i$ when , The final total movement is ${\sum }_{i=1}^n{v}_i{x}_i,x_i=0/1$. If the total number of moves is $m$, That is to say bitset Of the $m$ Position as 1, It means that it can just fill the whole backpack .

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

const LL maxn = 1030;
bitset<maxn> f[maxn], g[maxn];

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    LL t; cin>>t;
    while(t--) {
    
        LL n, m; cin>>n>>m;
        Fo(i,0,1023) f[i].reset();
        f[0][0] = 1;
        Fo(i,1,n) {
    
            LL x, y; cin>>x>>y;
            Fo(j,0,1023) g[j]=f[j]<<x;
            Fo(j,0,1023) f[j]|=g[j^y];
        }
        LL ans = -1;
        Ro(i,1023,0) {
    
            if(f[i][m]) {
    
                ans = i;
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}