进行一个魔的除题解

· · 题解

为了与题面统一，称 a_i 状态 \tt 1 \to \tt 0 为消除，\tt 0 \to \tt 1 为点亮。

算法零

由于状态只有 2^n 种，因此记忆化所有状态，爆搜转移。

时间复杂度 \mathcal O(n^32^n + T)，可以通过 Subtask 0。

算法一

按算法四的思想模拟即可，不过多赘述。

时间复杂度 \mathcal O(\sum n^2)。

算法二

考虑初始灯全为 0。

这个时候，勇士可以直接贪心地先点亮所有编号为奇数的格子，这样魔王每次只能消除一个 \tt 1；直到勇士只能往 \tt 1 空隙中点亮为止。

可以选择任何计算方法，时间复杂度 \mathcal O(\sum n)，还可以通过推结论的方法做到更优。

算法三

考虑数据随机。

一些缺少一些细节的贪心以及乱搞做法应该都能通过。

算法四

考虑魔王的每次消除 \tt 1 的行动，按照时间推移，它形如：

由于 A 段和 C 段每一天都只比前一天增加一盏亮着的灯，所以只需求出在 B 段花费的时间即可计算总时间。

考虑 A 段：先贪心地模拟魔王，每次消掉两个连续的 \tt 1，并直接算出它的时间。

在 A 段魔王消除之时，我们可以假设勇士知道魔王会如此消除（事实上，根据魔王每一步的消除，针对性地再点亮一些灯也可行），那么他的最优策略肯定是：在保证任意两个 \tt 1 不连续的前提下，点亮尽可能多的 \tt 1，可以用 dp 求解。

考虑 B 段：由于魔王每次都会采取最优策略，那么勇士补上每次魔王消掉的那一盏灯，这同样也是最优的。可能有形如 \tt{010000001000} 的特殊情况，即魔王第一天无论怎么选择都比较劣，可以首先进行一轮模拟或者特判掉。剩下的时间，就相当于每天点亮两盏灯。

考虑 C 段：在 A / B 段都已经求出来的情况下，可以直接求解。

时间复杂度 \mathcal O(\sum n)。

代码如下：

#include<bits/stdc++.h>
#define pi pair<int,int> 
#define mid (l+r)/2
#define N 1000001
using namespace std;
int t,n,a[N],cnt,cnt1,dp[N],ans,cnt2,flag,flag1,pre[N],nxt[N];
int pan(){//单消段特判 
    int x=-1;
    for(int i=1;i<=n;i++){//计算每两个 1 之间的间隔 
        if(a[i]){
            pre[i]=i-x-1;
            nxt[i]=n+1-i;
            if(x>0)nxt[x]=pre[i];
            x=i;
        }
    }
    for(int i=1;i<=n;i++){//判断是否有较优的单消情况 
        if(a[i]==1&&((pre[i]%2==1||nxt[i]%2==1)||a[i-1]==1||a[i+1]==1)){
            return 0;
        }
    }
    if(a[n]==1)return 0;
    return 1;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<=n+2;i++){
            a[i]=pre[i]=nxt[i]=dp[i]=0;
        }
        cnt=cnt1=ans=cnt2=flag=flag1=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i])ans++,flag=1;
        }
        if(pan())flag1=1;
        for(int i=1;i<=n;i++){//判断初始双消段的长度 
            if(a[i]==a[i+1]&&a[i]==1){
                a[i]=a[i+1]=0;
                cnt++;
            }
        }
        for(int i=1;i<=n;i++){
            if(a[i]==1){
                dp[i]=max(dp[i-2],dp[i-3]);
            }else if(a[i+1]!=1&&a[i-1]!=1){
                dp[i]=max(dp[i-2],dp[i-3]);
                dp[i]++;
            }
            cnt1=max(cnt1,dp[i]);
        }
        if(n<=3){
            if(ans<n)cout<<1<<endl;
            else cout<<0<<endl;
            continue;
        }
        if(cnt1/3<cnt){//判断是否存在单消段 
            cout<<n-ans<<endl; 
            continue;
        }
        cnt1=cnt1-cnt*3;
        if(flag1&&flag)cnt1++;
        if(flag)cout<<n-ans-cnt1/2-1<<endl;
        else if(n<=5)cout<<2<<endl;
        else cout<<n-(cnt1-3)/2-3<<endl;    
    }   
    return 0;
}

PS：这题据说可能有神秘的 bitset 或者线段树等做法，大家可以试一试。