刚学 WA 一个点求助
查看原帖
刚学 WA 一个点求助
239192
淸梣ling楼主2022/12/30 22:41

在第三个捆绑测试 WA 了一个点,对应代码里的 Sub1,请问有 dalao 帮一下萌新吗 qwq

#include<bits/stdc++.h>
using namespace std;

int a[20];
int b[1000100],s[1000100];
int f[1<<18];
int ans;
int n,v,x;

namespace Sub1 {
    int t[1<<18];
    set<int> st;
    void add(int cur)
    {
        for(int i=0; i<x; i++)
        if(!((cur>>i)&1))
        {
            int sta=cur|1<<i;
            ++t[sta];
            if(t[sta]==__builtin_popcount(sta))
            st.insert(sta);
        }
    }
    void work()
    {
        f[0]=1; add(0); st.insert(-1);
        for(int i=1; i<=n; i++)
        for(auto p=st.begin(); p!=st.end(); ++p)
        {
            int cur=*p;
            if(__builtin_popcount(cur^(cur&b[i]))+s[i]<=v)
            {
                f[cur]=1;
                add(cur); --p;
                st.erase(cur);
            }
        }
    }
}
namespace Sub2 {
    vector<int> t[19][1<<18]; // 桶
    void work()
    {
        f[0]=1;
        for(int i=0; i<1<<x; i++) t[0][i].push_back(0);
        for(int i=1; i<=n; i++)
        for(int j=0; j<=min(v-s[i], x); j++)
        {
            for(int cur : t[j][b[i]])
            if(!f[cur|b[i]])
            for(int k=cur|b[i]; k; k=(cur|b[i])&(k-1))
            if(!f[k])
            {
                f[k]=1;
                int ccur=((1<<x)-1)^k,num=__builtin_popcount(k);
                for(int sta=ccur; sta; sta=ccur&(sta-1))
                t[num][sta].push_back(k);
            }
            t[j][b[i]].clear();
        }
    }
}
int main()
{
    cin>>n>>v>>x;
    for(int i=0; i<x; i++)
    scanf("%d", &a[i]);
    for(int i=1; i<=n; i++)
    for(int j=0; j<x; j++)
    {
        int c;
        scanf("%d", &c);
        if(c) b[i]|=1<<j;
        s[i]+=c;
    }

    if(n<=2e3)
    Sub1::work();
    else
    Sub2::work();

    for(int i=0; i<1<<x; i++)
    if(f[i])
    {
        int sum=0;
        for(int j=0; j<x; j++)
        if((i>>j)&1)
        sum+=a[j];
        ans=max(ans, sum);
    }
    cout<<ans;
    return 0;
}
2022/12/30 22:41
加载中...