当前位置：首页 > news >正文

打卡信奥刷题（2554）用C++实现信奥 P2133 天作之合

news 2026/5/11 23:41:42

P2133 天作之合

题目背景

生活就是一次 A*，你是我的第一个目标状态。——小明

题目描述

在小明的学校中，有若干个女生。小明认为每个女生的特征可以抽象为一个666位的数字串，其中不重复地包含1∼61\sim61∼6这666个数码。

在小明心中，有一个理想的女生，她的特征数字串为AAA。如果串YYY是串XXX交换两个连续的数码所得，那么我们认为特征数字串XXX和YYY相似。首先，小明找到了他的同桌，她的特征数字串为SSS。每次，小明会寻找一个特征数字串和当前串相似的女生，直到寻找到适合他的（即特征数字串和AAA相同或相似的）。定义每个女生的合适程度为找到此人至少需要找女生的数量（包括他的同桌和此人自己）。显然，合适程度数值越小的女生越适合小明。

然而，小明觉得老天不会轻易地让他找到，所以他认为合适程度第二小的才是他最合适的伴侣（也就是小红）。那么，请你帮他写一个程序，求出对于小明，小红的合适程度是多少。

输入格式

第111行，一个特征数字串AAA。

第222行，一个特征数字串SSS。

输出格式

一行，一个非负整数表示小红的合适程度。

输入输出样例 #1

输入 #1

123654 123456

输出 #1

说明/提示

样例解释：

最短的两个「合适的数字串」分别是454\tt 454454和545\tt 545545，故答案为333。

对于全部数据，保证串AAA和SSS合法，且保证能找到。

C++实现

#include<bits/stdc++.h>usingnamespacestd;string a,b;intdata[10];map<char,int>m;intmain(){cin>>a>>b;a=' '+a;//加上空格，个人习惯使用s[1]~s[6]b=' '+b;intans=0,cnt=0;for(inti=1;i<=6;i++)m[a[i]]=i;//map标记每个数字正确的位置for(inti=1;i<=6;i++)data[i]=m[b[i]];//同上，data[i]为b[i]应该在的位置for(inti=1;i<=6;i++)for(intj=i+1;j<=6;j++)if(data[j]<data[i])ans++;//求逆序对个数if(ans<2)ans+=2;//特判，如果没交换或者只交换了一次，必定属于最优解加2的情况else{for(inti=1;i<=6;i++)if(abs(data[i]-m[a[i]])==ans)cnt++;//特殊情况出现if(cnt==1)ans+=2;//只有一个数在移动}cout<<ans;return0;}