交换

NC232383. 交换

描述

小沙是一个机器人，虽然小沙有很多设计不完善的地方，但是小沙立志要成为一个聪明的机器人。

小沙经常遇见这样的一个问题，管理员大大要小沙将上传的指定数列进行排序。

小沙的程序指令集中每个指令会交换两个位置上的数字，哪怕那两个位置上没有数也会进行交换。

完成任务后会直接返回与给定数列长度相同的数列。

小沙的设计缺陷就在于对于每次管理员大大给定的任务，他并不能随心所欲的挑选指令集中的指令来进行交换，但他可以选择指令操作集中的一段子串从前往后按顺序执行指令来完成任务。

现在管理员大大又给了小沙许多任务，希望你可以帮小沙完成管理员大大给的任务，对于每个任务，输出最短可完成任务指令数长度。

如果小沙无法完成任务，那么他只好输出-1了QAQ。

输入描述

第一行输入两个数字 分别代表小沙的指令集长度，以及管理员大大下发的任务数
随后行 每行两个数字，代表交换位置的数字 
随后行 每行第一个数代表这段数列有个数,保证给定 数是一段排列。

输出描述

对于每个任务输出一行整数代表答案
如果没法完成任务输出-1

示例1

输入:

输出:

1
1
2

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 1827ms, 内存消耗: 103420K, 提交时间: 2022-03-05 15:57:58

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int n,m,k;
int x[N],y[N];
unordered_map<string,int>mp;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i],x[i]--,y[i]--;
	string s="0123456789";
	string t="";
	for(int i=0;i<10;i++)
		t+=s[i],mp[t]=0;
	for(int i=1;i<=n;i++)
	{
		s="0123456789";
		for(int j=i;j>=1;j--)
		{
			swap(s[x[j]],s[y[j]]);
			t="";
			int maxn=-1;
			for(int l=0;l<10;l++)
			{
				t+=s[l];
				maxn=max(maxn,s[l]-'0');
				if(maxn>l) continue;
				if(!mp.count(t)) mp[t]=i-j+1;
				else mp[t]=min(mp[t],i-j+1);
			}
		}
	}
	while(m--)
	{
		cin>>k;
		s="";
		for(int i=1,a;i<=k;i++)
		{
			cin>>a; a--;
			s+=(char)(a+'0');
		}
		if(!mp.count(s)) cout<<"-1\n";
		else cout<<mp[s]<<"\n";
	}
	return 0;
}

上一题

下一题

详情