15011418730 LV 7 @ 2025-8-24 22:28:06

自动搬运

来自洛谷，原作者为

	serene_analysis 我所有的欲望和沉思，都是这个世界缓缓呼出的气流

搬运于2025-08-24 22:28:06，当前版本为作者最后更新于2021-10-16 20:28:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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;
	}
}

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

感谢您的阅读。

ID

6365

时间

1000ms

内存

128MiB

难度

(无)

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[BalticOI 2012] 旋律 (Day2)

信息

1 条题解

自动搬运

以下是正文

[BalticOI 2012] 旋律 (Day2)

信息

还没有账户？

登录