题解 P7254 [BalticOI 2012 Day2]旋律

· · 题解

看着自己一年半前写的题解十分感慨。当年还只会暴力，现在却成了一看就会的题。真怀念那个时候啊。

2021.10.16：第一版题解，暴力过的题。

2023.7.4：第二版题解，增加了两种复杂度正确的解法，对原内容进行了修正。为了行文方便，这版增加的内容放在原内容之后，如果你只想看正解，则不需要阅读原内容。

2021.10.16 第一版

可能是非正解，但因网上似乎找不到题解且 Loj 的 special judge 似乎有问题，于是写一篇题解，供对拍或参考。顺便补充一下数据范围： 1 \le G \le S \le 100,1 \le L \le 10^5。

看到最小值和这样的数据范围，应该会去想 DP。

那么来分析一下怎么设状态。首先一维 i 要给现在正要弹第几个音符。然后发现为了明确表示状态，还需要一维 j 记录第 i 个选择弹第 j 个音符。

这样表示状态，那么转移就是从正要弹第 i-1 音符转移而来。如果暴力比较复杂度又多出一个 n，发现 \mathcal{O}(n^2S) 复杂度可以接受，考虑预处理两个音符能否互相紧邻着弹奏。那么转移就从所有可以紧邻着 j 弹奏的音符转移而来，取最小值即可。

想到这里，你的图论思维应该已经提醒你了。这相当于在所有可以紧邻着的音符间建边，每次可以从一条边走到另一条边，每走一步可以 \mathcal{O}(1) 算代价。那么设 mi_{i,j} 表示前 i 个乐符，第 i 个乐符弹的是第 j 个音符，最小的弹错的数量。按照上述方法转移。

如果直接枚举每个点看其与当前点是否有连边，时间复杂度是 \mathcal{O}(n^2L) 的，稳过 \text{65pts}。

考虑优化，上前向星，减少无用枚举，开 \text{O2} 能有 \text{93pts}。

观察到有 TLE \text{1.16s}，猜测没有超时限太多。将前向星换为 \texttt{std::vector}，配合 \text{O2} 就可以过了，最大点大约 \text{800ms}。

理论时间复杂度仍然是 \mathcal{O}(n^2L) 的，能卡过纯属数据水。这个做法没有用到每个孔只有 10 种可能，即便出到 10^9 也一样能做，因此我猜测正解依赖于这个性质，不知道有没有人会，如果您做出来了请务必即刻私信我，我洗耳恭听！

#include<algorithm>
#include<cstdio>
#include<vector>
const int maxn=1e2+5;
const int maxm=1e2+5;
const int maxq=1e5+5;
const int inf=1073741823;
std::vector<int>apr[maxn];
int n,m,k;
int q;
int want[maxq];
int dig[maxn][maxm];
int mi[maxn][maxq];
int stk[maxq],scnt;
void out(int x,int wz){
//  printf("x=%d,wz=%d\n",x,wz);
    stk[++scnt]=x;
    if(wz==1){
        for(int i=scnt;i;i--)printf("%d ",stk[i]);
        return;
    }
    int nmi=inf;
    for(int v:apr[x])nmi=std::min(nmi,mi[v][wz-1]);
    for(int v:apr[x]){
        if(mi[v][wz-1]==nmi){
            out(v,wz-1);
            return;
        }
    }   
    return;
}
signed main(){
//  freopen("melody.i18a","r",stdin);
//  freopen("out.txt","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%1d",dig[i]+j);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int cou=0;
            for(int l=1;l<=m;l++)cou+=(int)(dig[i][l]!=dig[j][l]);
            if(cou<=k){
                apr[i].push_back(j);
                apr[j].push_back(i);
            }
        }
    }
    for(int i=1;i<=n;i++)apr[i].push_back(i);
    scanf("%d",&q);
//  printf("q=%d\n",q);
    for(int i=1;i<=q;i++)scanf("%d",want+i);
    for(int i=1;i<=n;i++)mi[i][1]=(i==want[1]?0:1);
    for(int i=2;i<=q;i++){
        for(int j=1;j<=n;j++){
            mi[j][i]=inf;
            for(int v:apr[j])mi[j][i]=mi[j][i]>mi[v][i-1]?mi[v][i-1]:mi[j][i];
            mi[j][i]+=(int)(j!=want[i]);
        }
    }
    int res=inf;
    for(int i=1;i<=n;i++)res=std::min(res,mi[i][q]);
    printf("%d\n",res);
    for(int i=1;i<=n;i++){
        if(mi[i][q]==res){
            out(i,q);
            return 0;
        }
    }
    return 0;
}

感谢您的阅读！

2023.7.4 第一次补充

上面的做法看起来没有什么优化空间，我们尝试换个思路。这次我们尝试设 mx_i 表示强制 i 这个位置弹对的前提下最多弹对的个数，并设 p 表示 i 这个位置具体是哪个音符。这样我们就知道当前弹的是什么了。直接暴力枚举上一个弹对的位置肯定是不可取的，但是注意到上一个弹对的位置的音符只有 n 种可能，如果音符相同肯定是取个数最多的，那么可以考虑枚举上个弹对的位置的音符 q。考虑相邻两个音符的限制，如果我们把可以连续弹奏的两个音符的距离设成 1，那么跑个 floyd 就可以得到任意两个音符最近要隔多远。也就是说，合法的 q 是所有可能的 q 的一个前缀，这个位置可以直接二分出来。再注意到对于音符相同的位置其 mx 一定单调递增（因为你可以直接全填这一个音符），那么二分出来离 i 最近的位置就是最优决策，直接转移即可。时间复杂度 \mathcal{O}(nL \log L)，那我们已经获得了复杂度正确的算法。

#include<algorithm>
#include<cstdio>
#include<vector>
const int maxn=1e2+5;
const int maxl=1e5+5;
int n,s,g,l;
char tp[maxn][maxn];
int dis[maxn][maxn];
bool link[maxn][maxn];
int id[maxl];
int mx[maxl];
struct state{
    int stk[maxl],scnt;
    void push(int x){
//      printf("push:%d\n",x);
        stk[++scnt]=x;
        return;
    }
    int query(int x,int &gid){
        if(id[x]==id[stk[scnt]]){
            gid=stk[scnt];
            return mx[stk[scnt]];
        }
        int ef_lef=1,ef_rig=scnt,ef_ans=-1,ndis=dis[id[x]][id[stk[scnt]]];
        while(ef_lef<=ef_rig){
            int ef_mid=(ef_lef+ef_rig)>>1;
            if(x-stk[ef_mid]>=ndis)ef_ans=ef_mid,ef_lef=ef_mid+1;
            else ef_rig=ef_mid-1;
        }
//      printf("ef_ans=%d,id[stk[scnt]]=%d\n",ef_ans,id[stk[scnt]]);
        if(ef_ans==-1)return 0;
//      printf("stk[ef_ans]=%d\n",stk[ef_ans]);
        gid=stk[ef_ans];
        return mx[stk[ef_ans]];
    }
}stk[maxn];
int from[maxl],out[maxl];
void go(int x,int y,int len,int wz){
    if(len==0)return;
//  printf("go:%d,%d,%d,%d\n",x,y,len,wz);
    out[wz]=x;
    for(int i=1;i<=n;i++)if((link[x][i]||x==i)&&dis[i][y]<=len-2){
        go(i,y,len-1,wz+1);
        return;
    }
    return;
}
void tian(int x){
    if(!x)return;
    tian(from[x]),out[x]=id[x];
    if(from[x])/*printf("go:%d,%d,%d,%d\n",id[from[x]],id[x],x-from[x]+1,from[x]),*/
        go(id[from[x]],id[x],x-from[x]+1,from[x]);
    return;
}
signed main(){
    scanf("%d%d%d",&n,&s,&g);
    for(int i=1;i<=n;i++)scanf("%s",tp[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)dis[i][j]=0,link[i][j]=true;
            else{
                int cou=0;
                for(int k=1;k<=s;k++)cou+=(tp[i][k]!=tp[j][k]);
                dis[i][j]=(cou<=g?1:maxl),link[i][j]=(cou<=g);
            }
//          printf("%d ",link[i][j]);
        }
//      printf("\n");
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=n;j++)printf("%d ",dis[i][j]);
//      printf("\n");
//  }
    scanf("%d",&l);
    for(int i=1;i<=l;i++)scanf("%d",id+i);
    stk[id[1]].push(1),mx[1]=1;
    for(int i=2;i<=l;i++){
        for(int j=1;j<=n;j++)if(stk[j].scnt){
            int nid=-1,nv=stk[j].query(i,nid);
//          printf("i=%d,j=%d,nv=%d\n",i,j,nv);
            if(nv>mx[i])mx[i]=nv,from[i]=nid;
        }
        mx[i]++,stk[id[i]].push(i);
//      printf("mx[%d]=%d,from[%d]=%d\n",i,mx[i],i,from[i]);
    }
    int pos=std::max_element(mx+1,mx+l+1)-mx;
    printf("%d\n",l-mx[pos]),tian(pos);
    int fpos=-1,spos=-1;
    for(int i=1;i<=l;i++)fpos=(fpos==-1&&out[i]?i:fpos),spos=(out[i]?i:spos);
//  printf("fpos=%d,spos=%d\n",fpos,spos);
    for(int i=1;i<=fpos;i++)out[i]=out[fpos];
    for(int i=spos;i<=l;i++)out[i]=out[spos];
    for(int i=1;i<=l;i++)printf("%d ",out[i]);
    return 0;
}
/*
4 2 1
00
11
10
21
4
1 1 2 4
*/
/*
10 7 3
4030342
4330332
2043120
4043312
0043022
0043122
4332332
4043122
4332331
4000312
5
5 10 3 1 5
*/
//namespace burningContract

反过来思考，对于一个位置，其能贡献到的位置其实也就是对于每种颜色的一个后缀，这个后缀的位置可以直接算出来，那么取个前缀 \max 即可。时间复杂度降至 \mathcal{O}(nL)。下面给出核心代码，方案构造和上一个算法一致。

for(int i=1;i<=l;i++){
    for(int j=1;j<=n;j++)if(cmx[j][i-1]>cmx[j][i])
        cmx[j][i]=cmx[j][i-1],cid[j][i]=cid[j][i-1];
    mx[i]=cmx[id[i]][i]+1,from[i]=cid[id[i]][i];
    for(int j=1;j<=n;j++){
        int arr=std::min(l+1,i+dis[id[i]][j]);
        if(mx[i]>cmx[j][arr])cmx[j][arr]=mx[i],cid[j][arr]=i;
    }
}

后话：一年半前的猜测果然不靠谱，快过来洗耳恭听！（

感谢您的阅读。