题解 P3943 星空

题解

一道思维量巨大的题，很烧脑

考虑异或差分，设 \(d_i=a_i\;\;xor\;\;a_{i-1}\)，那么对于翻转 \(a_i\sim a_j\) 就相当于 \(b_i\) 和 \(b_{j+1}\) 异或 \(1\)

那么我们最后要求的异或序列就全是 \(0\)，那么想办法消去 \(1\)，考虑状压

因为我们只想消去 \(1\)，所以我们只需考虑异或为 \(1\) 的位置，而这最多有 \(2k\) 位，所以我们对这状压。

那么我们考虑由 \(i\) 位异或到 \(j\) 位需要多少步，这个通过 \(bfs\) 来解决。

技巧：我们可以在枚举状态时，对每个状态只转移最低位，因为每个状态都会被转移到。

这样复杂度为 \(\mathcal O(2knm+2k×2^{2k})\)

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define lowbit(x) ((x)&-(x))

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    static const int N=4e4+7,K=18;

    int dis[K][K],tdis[N],vis[N],b[K<<2],a[K],que[N],lg[1<<K],f[1<<K],tot,n,k,m;

    void bfs(int x,int id) {

        memset(tdis,0x3f,sizeof(tdis));

        ri hd=1,tl=0;

        tdis[que[p(tl)]=x]=0;

        while(hd<=tl) {

            x=que[hd++];

            for (ri i(1);i<=m;p(i)) {

                if (x-b[i]>0&&tdis[x-b[i]]>tdis[x]+1) tdis[x-b[i]]=tdis[x]+1,que[p(tl)]=x-b[i];

                if (x+b[i]<=n+1&&tdis[x+b[i]]>tdis[x]+1) tdis[x+b[i]]=tdis[x]+1,que[p(tl)]=x+b[i];

            }

        }

        for (ri i(1);i<=tot;p(i)) dis[id][i]=tdis[a[i]];

    }

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(n),read(k),read(m);

        for (ri i(1),x;i<=k;p(i)) read(x),vis[x]^=1,vis[x+1]^=1;

        for (ri i(1);i<=m;p(i)) read(b[i]);

        for (ri i(1);i<=n+1;p(i)) if (vis[i]) a[p(tot)]=i;

        for (ri i(1);i<=tot;p(i)) bfs(a[i],i);

        int S=(1<<tot)-1;

        for (ri i(2);i<=S;p(i)) lg[i]=lg[i>>1]+1;

        memset(f,0x3f,sizeof(f));

        f[S]=0;

        for (ri i(S);i;--i) {

            int low=lg[lowbit(i)],bs=i^(1<<low);

            for (ri j(low+1);j<tot;p(j)) {

                if (!(i&(1<<j))) continue;

                int aim=bs^(1<<j);

                f[aim]=cmin(f[aim],f[i]+dis[low+1][j+1]);

            }

        }

        printf("%d\n",f[0]);

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

题解 P3943 星空

题解

最新文章

热门文章