【codeforces 752B】Santa Claus and Keyboard Check
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other’s place! That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be.
In order to make sure that he’s right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard.
You are given the Santa’s favorite patter and the string he actually typed. Determine which pairs of keys could be mixed. Each key must occur in pairs at most once.
Input
The input consists of only two strings s and t denoting the favorite Santa’s patter and the resulting string. s and t are not empty and have the same length, which is at most 1000. Both strings consist only of lowercase English letters.
Output
If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «-1» (without quotes).
Otherwise, the first line of output should contain the only integer k (k ≥ 0) — the number of pairs of keys that should be swapped. The following k lines should contain two space-separated letters each, denoting the keys which should be swapped. All printed letters must be distinct.
If there are several possible answers, print any of them. You are free to choose the order of the pairs and the order of keys in a pair.
Each letter must occur at most once. Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes.
Examples
input
helloworld
ehoolwlroz
output
3
h e
l o
d z
input
hastalavistababy
hastalavistababy
output
0
input
merrychristmas
christmasmerry
output
-1
【题目链接】:http://codeforces.com/contest/752/problem/B
【题解】
开一个map,看看每个小写字母的对应关系是什么;
如果发现有不合法的地方就输出无解就好;
用map来判断的话很方便的。
也不用转换成int之类的。
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e3+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
map <char,int> b,b2;
map <char,char> dic;
char s1[MAXN],s2[MAXN],s3[MAXN];
int num = 0;
vector <pair<char,char> > ans;
void QAQ()
{
puts("-1");
exit(0);
}
int main()
{
// freopen("F:\\rush.txt","r",stdin);
scanf("%s",s1);
scanf("%s",s2);
int len = strlen(s1);
for (int i = 0;i <= len-1;i++)
{
if (!b[s1[i]])
{
b[s1[i]] = 1;
dic[s1[i]] = s2[i];
if (b[s2[i]]==1)
{
if (dic[s2[i]]!=s1[i])
QAQ();
}
else
{
b[s2[i]] = 1;
dic[s2[i]] = s1[i];
}
}
else
if (dic[s1[i]]!=s2[i] || dic[s2[i]]!=s1[i])
QAQ();
}
for (char i = 'a';i <= 'z';i++)
if (b[i]!=0)
{
if (dic[i]!=i && !b2[i] && !b2[dic[i]])
{
ans.pb({i,dic[i]});
b2[i] = b2[dic[i]] = 1;
}
}
len = ans.size();
cout << len << endl;
rep1(i,0,len-1)
printf("%c %c\n",ans[i].fi,ans[i].se);
return 0;
}
相关文章
- android studio报错Gradle project sync failed. Please fix your project and try again
- Sereja and Suffixes
- I bumped into a girl literally_back and forth
- MOB LEC3 Cameras and Images
- CodeForces 750A New Year and Hurry
- A. Vasya and Book ( Codeforces Educational Codeforces Round 55 )
- ORA-24042: no propagation schedule exists for QUEUE string and DESTINATION string ORACLE 报错 故障修复 远程处理
- ORA-00054: resource busy and acquire with NOWAIT specified or timeout expired ORACLE 报错 故障修复 远程处理
- ORA-01295: DB_ID mismatch between dictionary string and logfiles ORACLE 报错 故障修复 远程处理
- SQLServer 错误 41349 警告:为包含具有持续性 SCHEMA_AND_DATA 的一个或多个内存优化表的数据库启用了加密。 不会对这些内存优化表中的数据加密。 故障 处理 修复 支持远程
- Codeforces 842A Kirill And The Game暴力,水详解编程语言
- MySQL Error: Solutions and Best Practices(mysqlerror)
- Linux崩溃?如何应对与解决(Crash Linux: How to Handle and Fix)(crashlinux)
- 深入浅出:MySQL中AND和OR运算符使用方法(mysql中and和or)
- Exploring the Power of Linux Labeling: Enhancing Security and Organization(linuxlabel)
- Mysql中强大的AND运算符的使用方法探究(mysql中and的使用)
- Oracle中使用除了And的其他查询关键字(oracle中除了and)
- 实现支持逻辑搜索/单词搜索/词组搜索+支持OR/AND关键字的VBSCLASS!