[ICM Technex 2018 and Codeforces Round #463][Codeforces 932E] Team Work
[Codeforces Round #466 (Div. 2)][Codeforces 940F] Machine Learning

[Codeforces Round #467 (Div. 1)][Codeforces 936C] Lock Puzzle

Zarxdy34 posted @ 2018年2月27日 23:28 in Codeforces with tags 构造 , 453 阅读

        题目大意:定义对字符串S的操作shift x为\[S'=B^RA\ (S=AB,length(B)=x),0 \leq x \leq length(S)\]

        例如字符串\(S=bcacab\)经过操作shift 4后变为\(S'=bacabc\)。给出两个长度为\(n\)的字符串\(S,T\),要求在6100步之内将\(S\)变成\(T\),求操作方案。\((n \leq 2000\)

        题解:可以从数据范围中看出来,如果能每次将一个字符在3步内移到正确的位置的话,就肯定能完成。

        如果我已经将最后m位字符放在了合适的位置,现在我要把本应在第m+1位的字符x移动进来,设它的位置为pos,则当前有\[S=AxBC,length(A)=pos-1,length(C)=m\]

        我可以进行三次操作:1.shift n-pos-1   2.shift 1   3.shift n

        三次操作后S分别变化为:\[S_1=C^R B^R A x\] \[S_2=x C^R B^R A\] \[S_3=A^R B C x\]

        三次操作之后,变到了最后,而\(C\)字符串保持不变。也就是说,只要我们每次将本应在第i位的字符(i从n到1)换到最后一位,我们就能够在\(3n\)次操作之后得到\(T^R\),最后再执行一次shift n即可得到\(T\)。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2010;

int cnt[26][2];
char s[maxn],t[maxn],tmp[maxn];
int ans[maxn<<2],ansn;
int n;

void Reverse(int N)
{
	for (int i=0;i<N;i++) tmp[i]=s[n-i-1];
	for (int i=N;i<n;i++) tmp[i]=s[i-N];
	for (int i=0;i<n;i++) s[i]=tmp[i];
}

int main()
{
	scanf("%d",&n);
	scanf("%s%s",s,t);
	for (int i=0;i<n;i++) cnt[s[i]-'a'][0]++;
	for (int i=0;i<n;i++) cnt[t[i]-'a'][1]++;
	for (int i=0;i<26;i++) if (cnt[i][0]!=cnt[i][1])
	{
		printf("-1\n");
		return 0;
	}
	for (int i=n-1;i>=0;i--)
	{
		int pos=0;
		while (s[pos]!=t[i]) pos++;
		if (i==n-1)
		{
			Reverse(n-1-pos);
			ans[++ansn]=n-1-pos;
			continue;
		}
		Reverse(n-pos-1);
		Reverse(1);
		Reverse(n);
		ans[++ansn]=n-pos-1;
		ans[++ansn]=1;
		ans[++ansn]=n;
	}
	Reverse(n);
	ans[++ansn]=n;
	printf("%d\n",ansn);
	for (int i=1;i<=ansn;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

 

        题解的做法为\(\frac{5}{2}n\)的,做法和一个操作次数为\(2n\)的做法差不多,就说一下\(2n\)的做法。\[S=AxByCD\] \[S_1=d^RC^RyB^RAx\] \[S_2=xD^RC^RyB^RA\] \[S_3=A^RByxD^RC^R\] \[S_4=CA^RByxD^R\]

Avatar_small
AHSEC Syllabus 说:
2022年9月30日 01:36

Department of Education & Government of Assam Higher Secondary Education Council is announced the state class 11th and 12th standard Arts, AHSEC Syllabus Science and Commerce course students for MIL and revised course with Curriculum government and private college students as AHSEC HS Syllabus 2023 Pdf to all Hindi and English Medium students.Department of Education & Government of Assam Higher Secondary Education Council is announced the state class 11th and 12th standard Arts .


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter