自动搬运

查看原文

来自洛谷，原作者为

	shadow__ **

搬运于2025-08-24 21:54:25，当前版本为作者最后更新于2017-11-05 20:02:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题思维难度真的好大啊。。。写了两天，第二天看了好久才懂了我第一天的思路。。

#主体思路

首先我们发现对于连续的一段灯泡去按它的开关极其费时，因此我们需要一种O（1）复杂度的方法进行开关的操作。

想想看，对于区间的连续操作转为O（1）复杂度常用的方法是什么。

###差分！

其实具体把它想通是比较复杂的，而且乍一看感觉与差分没有任何关系。

但是根据亦或的性质，确实可以把对连续区间的0 1数列取反转化为对左端点与右端点取反。

n++
for(int i=1;i<=n;i++)G2[i]=G1[i]^G1[i-1];

这么做的可行性在于对于区间内我们提前进行了类似取反的操作。

差分的思想是在修改的区间左端点+1，右端点的右边-1，同样的，取反差分也是左闭右开。

例如某段区间全是1；

1 1 1 1 1 1

这么操作之后变为 1 0 0 0 0 0 1

如果我们要对1~6进行取反操作，在差分数组中对1,7取反，数列最终变为了全0。

那么这么做是不是偶然呢。

我们再对于原数列试着把3~4进行取反，于是差分数组变为

1 0 1 0 1 0 1

乍一看貌似与本该存在的数列110011没有什么半毛钱关系（滑稽）

但是要知道差分是左闭右开的。

此数组的意思为

在[1,3)中有(2-1)个1；

把结论一般化

从左到右每次取两个1，记第一个1位置为l，第二个1位置为r

对于原数组的意义为

在[l,r)间有(r-1-l)个1；

（貌似是这样的吧。。如果有问题可以在讨论里指出，本人仅是一名蒟蒻）

道理之前说过了，我们在建G2时对于新数列进行了类似于提前取反的操作。

既然可行性被证明。。那么我们便完成了对该问题的。。

#第一步转化。

那么原问题被我们巧妙（巧妙？玄学！）的转化为了对于给定的0 1数列，每次对于按要求的某两个数进行取反，问最少次可以使数列全部变为1.

接下来大家可以参考出题人给出的题解。

（当然我还是会说一下的）

显然，我们每次的L，R必然包括0.

假如每次是对两个0取反，那么他们都变成了1。

假如是对一个1一个0进行取反，则可以看成把0和1换位，即：

###0走到了1的位置。

这里有必要提一下原问题麻烦的地方，即对于答案无用的灯泡（亮着的）太多，这样会导致进行大量的无效操作。

如果想进行状压复杂度则高到了恐怖的O（2^40000）。

然而最终有用的转化仅在对未亮灯泡进行操作。

那么此时则体现了刚刚那句话的重要性。

既然可以看成1走到了0的位置，那么我们完全可以不考虑1的存在嘛。

于是乎我们对于问题进行了

#第二次转化

给你几个点，每次将其中一个点移动特定的距离，如果两个点碰到了一起，则两个点一起消失。

问如何移动使得消去所有的点的步数最少。

我们再对这个问题进行小贪心。

消去同一对点，那么一定是取他们走到一起的最短步数最优（废话）

那么找最短路的方法可以用spfa进行（这里吐槽一下出题人给的题解啊，误导了我好久，发现根本不是bfs好伐，也可能是我蒟蒻的问题？）

没错，我们把问题进行了

#第三次转化

我保证这是最后一次了。（滑稽）

给你一堆物品，一次只能取出给定的一对物品，取出不同对的物品有不同的代价，问如何取出物品使得代价最小。

由于题目中的不亮灯泡极少，我们完全可以通过状压完成最后的操作。

然而我这个蒟蒻不会状压动规，这里我把状压转为SPFA。

每一种状态看作一个点，每次取出物品的代价可以看作给一种状态和另一种状态连一条权值为其代价的边。

问始态到终态的最短路。

（不是第四次转换！不是第四次转换！不是第四次转换！（滑稽））

#代码

#include<bits/stdc++.h>
const int INF =2147483647;
using namespace std;
struct node{
    int v,w,next;
}cost[210];
int head[41000],e;
inline void insert(int u,int v,int w){
    cost[++e].next=head[u];
    cost[e].v=v;
    cost[e].w=w;
    head[u]=e;
}
int n,m,k;
int hash[41000],id[41000],Index;
bool G1[41000],G2[41000];
vector<int>stone;
queue<int>q;
bool vis[41000],inq[70000];
int dist[20][41000];
int step[65];
int f[70000];
inline void bfs(){//其实是SPFA 
    for(int i=0;i<stone.size();i++){
        memset(vis,0,sizeof(vis));
        int v=stone[i];
        dist[i+1][v]=0;
        q.push(v);
        inq[v] = true;
        while(!q.empty()){
            int x=q.front();q.pop();
            inq[x]=false;
            for(int j=1;j<=m;j++){
                int z=x+step[j];
                int y=x-step[j];
                if(z<=n){
                    if(dist[i+1][z]>dist[i+1][x]+1){
                        dist[i+1][z]=dist[i+1][x]+1;
                        if(!inq[z]){
                            q.push(z);
                            inq[z]=true;
                        }
                    }
                }
                if(y>=1){
                    if(dist[i+1][y]>dist[i+1][x]+1){
                        dist[i+1][y]=dist[i+1][x]+1;
                        if(!inq[y]){
                            inq[y]=true;
                            q.push(y);
                        }
                    }
                }
            }
        }
    }
}
inline void spfa(){
    int N=(1<<(Index))-1;
    f[N]=0;
    inq[N]=true;
    q.push(N);
    while(!q.empty()){
        int v=q.front();q.pop();
        inq[v]=false;
        for(int i=1;i<=Index;i++){
            int x=1<<(Index-i);
            for(int j=head[i];j;j=cost[j].next){
                int z=1<<(Index-cost[j].v);
                int w=cost[j].w;
                int u=(v^x)^z;
                if((v&x)&&(v&z)){
                    if(f[v]+w<f[u]){
                        f[u]=f[v]+w;
                        if(!inq[u]){
                            q.push(u);
                            inq[u]=true;
                        }
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&k,&m);
    int a;
    n++;
    for(int i=1;i<=k;i++){
        scanf("%d",&a);
        G1[a]=1;
    }
    for(int i=1;i<=n;i++)G2[i]=G1[i]^G1[i-1];
    for(int i=1;i<=n;i++)if(G2[i]){
        ++Index;
        stone.push_back(i);
    }
    for(int i=1;i<=m;i++)scanf("%d",&step[i]);
    for(int i=1;i<=Index;i++)
    for(int j=1;j<=n;j++)dist[i][j]=INF;
    bfs();
    for(int i=1;i<=Index;i++)
    for(int j=i+1;j<=Index;j++){
        int minn = INF;
        for(int o=1;o<=n;o++)if(dist[i][o]!=INF&&dist[j][o]!=INF)minn=min(dist[i][o]+dist[j][o],minn);
        if(minn!=INF){
            insert(i,j,minn);
            insert(j,i,minn);
        }
    }
    memset(f,0x3f,sizeof(f));
    spfa();
    printf("%d\n",f[0]);
    return 0;
}

最后在这里给出让我DE出BUG的数据，比较小却也比较有代表性

6 4 2 1 3 4 5

3 1

9 4 4 4 7 8 9

5 4 3 2