P3943 星空

2018-09-17 20:27:21


这道题是2017.11.02 luogu模拟赛的T3

当时大家都只得了 $8-12$ 分不等


部分分做法:

  • $4pts$ : $n=m=2,k<=2$ ,直接 $printf("\%d",1-(k==0))$

  • $24pts$ : $n,m<=16$ ,直接对原序列状压 $dp$

    复杂度 $O(m2^n)$

  • $m=1$ ,从前往后贪心消去第一个 $1$

  • 答案小于 $4$ ,特判答案为 $0$ 或 $1$ 的情况

    爆搜得到答案为 $2$ 的情况,没有就输出 $3$


发现 $k$ 很小,考虑以 $k$ 作为状态

因为涉及区间修改,可以将其转化到修改端点 $→$ 差分

做异或差分, $b[i]=a[i] xor a[i+1]$

如果在 $a$ 数组上反转 $[l,r]$ ,相当于在 $b$ 数组上对 $b[l-1]$ 和 $b[r]$ 取反


问题转化为:一个长度为 $n$ 的 $01$ 串,其中有不超过 $2k$ 个 $0$ ,每次从 $m$ 个长度中选择一个 $len$ ,将相距为 $len$ 的两点取反,问最少操作几次使得全部变为 $1$

举个栗子:

$011101$

$110101$

$111111$

可以发现,如果一个位置是 $0$ ,那么一定要进行操作来消去这个 $0$

如果选择一个 $1$ 和一个 $0$ ,可以看作把 $1$ 移动过来

如果选择两个 $0$ ,可以看作把一个 $0$ 移到另一个的位置并同时消去


那么问题进一步转化:

一个长度为 $n$ 的序列,有不超过 $2k$ 个位置有物品,每次可以从 $m$ 个距离中选择一个进行移动,两个物品放在一起会同时消去,最少操作几次可以消去所有物品

这样来看,最多有 $2k$ 个起点,每个点有 $m$ 条边,可以用 $O(nmk)$ 的 $bfs$ 预处理出两两之间的最短距离


问题再次转化:

有 $2k$ 个物品,两两可以消去,分别有不同的代价,求全部消去的最小代价

因为 $k<=8$ ,所以状压 $dp$ 即可

总复杂度 $O(nmk+k2^{2k})$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=4e4+5;
int n,k,m,a[N],len[65],pos[N],cnt;
int dis[N],d[17][17],r[1<<16],f[1<<16];
bool vis[N];
inline void Chkmin(int &a,int b){if (a>b) a=b;}
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void bfs(int s)
{
    queue<int>q;
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1;
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        for (reg int i=1;i<=m;i++)
        {
            int x=u+len[i],y=u-len[i];
            if (x<=n&&!vis[x]) dis[x]=dis[u]+1,q.push(x),vis[x]=1;
            if (y>=0&&!vis[y]) dis[y]=dis[u]+1,q.push(y),vis[y]=1;
        }
    }
}
int main()
{
    n=read(),k=read(),m=read();
    for (reg int i=1;i<=k;i++) a[read()]=1;
    for (reg int i=1;i<=m;len[i++]=read());
    for (reg int i=0;i<=n;i++)
      if (a[i]^a[i+1]) pos[++cnt]=i;
    for (reg int i=1;i<=cnt;i++)
    {
        bfs(pos[i]);
        for (reg int j=1;j<=cnt;j++) d[i][j]=dis[pos[j]];
    }
    for (reg int i=0;i<(1<<cnt);i++)
    {
        r[i]=cnt;
        for (reg int k=1;k<=cnt;k++)
          if (!((i>>k-1)&1)) {r[i]=k; break;}
    }
    memset(f,127/3,sizeof(f)); f[0]=0;
    for (reg int i=0;i<(1<<cnt);i++)
      for (reg int j=r[i]+1;j<=cnt;j++)
        if ((!((i>>j-1)&1))&&d[r[i]][j])
          Chkmin(f[i|(1<<r[i]-1)|(1<<j-1)],f[i]+d[r[i]][j]);
    printf("%d\n",f[(1<<cnt)-1]);
    return 0;
}