题目链接
题意简述
给你一个被加密后的字符串.字符串加密的规则是,字母表中所有二十六个字母围成一个圈,字符串中每个字母都被这个圈逆时针方向的上一个字母替代(这意味着加密前后的字符不能相同).
现在请你根据被加密后的字符串,构造一个加密规则,以找出一个字典序最小的加密前的原串.
样例
点击查看样例
分析
比赛时没有做出来这道题.来补题的时候发现挺简单的,自己A掉了.
找一个字符加密前的结果,也就是根据加密规则,该字符在圈中的位置逆时针方向的上一个位置
对于当前的一个加密后字符 \(c_i\) ,如果他还没有匹配加密前的字符,我们可以从小到大找还没有在圈中的字母,这样保证字典序最小,同时也不会形成小环.找到后就加入到圈中.
同时对已经在圈中的字符个数进行计数,如果个数达到25个了,说明下一个只需要连接到圈的头部.
圈的头部是什么?就是逆时针方向上一个位置还没有字符的.
所以可以开辟两个数组,一个数组 \(nex\) ,记录当前位置顺时针的下一个位置,也就是该字符加密后的结果.一个数组 \(pre\) ,记录当前位置的上一个字符是什么.如果上一个字符为空,要么是没加入到圈中,要么就是圈的头部了.判断是否在圈中也很好判断,并查集就可以.
代码
点击查看代码
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
int pre[200];
int nex[200];
int n;
string s;
int cnt=0;
char f[200];
int find(char u)
{
if(u!=f[u])
{
f[u]=find(f[u]);
}
return f[u];
}
void add(int a,int b)
{
int fa=find(a),fb=find(b);
f[fb]=fa;
}
char find(char u,int now)
{
if(pre[u])return pre[u];
if(cnt==25)
{
for(int i='a';i<='z';i++)
{
if(!nex[i])return i;
}
}
for(int i='a';i<='z';i++)
{
if(i==u)continue;
if(!nex[i]&&(find(i)!=find(u)||cnt==25))
{
cnt++;
add(i,u);
pre[u]=i;
nex[i]=u;
return i;
}
}
return ' ';
}
int main()
{
//freopen("uva.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
cnt=0;
memset(pre,0,sizeof pre);
memset(nex,0,sizeof nex);
scanf("%d",&n);
for(int i='a';i<='z';i++)
{
f[i]=i;
}
cin>>s;
for(int i=0;s[i];i++)
{
printf("%c",find(s[i],i));
}
printf("\n");
}
return 0;
}