`
从此醉
  • 浏览: 1034643 次
  • 性别: Icon_minigender_1
  • 来自: US
社区版块
存档分类
最新评论

uva 1339 Ancient Cipher

 
阅读更多

点击打开链接uva 1399

题意:给定两个长度分别为n的字符串,判断他们能否一一对应
思路:暴力
分析:
1 首先我们知道这两个字符串的长度最大为100并且相等
2 刚开始我的想法是对两个字符串排序,然后从头开始枚举判断。这个想法妥妥的过了样例,然而等到的确实一顿怒wa。下面举例证明我的思路是错误的
3 假设有两个字符串为ABBCFEA 和 CCGGHJB。排序后为AABBCEF和 BCCGGHJ如果按照我的思路那么我们从头开始枚举得到的是NO,但是实际上这个例子是YES。我们写出两个字符串中字母出现的次数的序列分别为22111和12211,那么我们对这个数字序列进行排序分别为11122和11122可以知道这个比较就可以得到YES

代码:

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 110;

bool ok(char *s1 , char *s2){
    int len = strlen(s1);
    int num1[maxn] , num2[maxn];
    memset(num1 , 0 , sizeof(num1));
    memset(num2 , 0 , sizeof(num2));
    for(int i = 0 ; i < len ; i++){
       num1[s1[i]-'A']++;
       num2[s2[i]-'A']++;
    }
    sort(num1 , num1+maxn);
    sort(num2 , num2+maxn);
    return !memcmp(num1 , num2 , sizeof(num1)) ? true : false;
}

int main(){
    char s1[maxn] , s2[maxn];
    while(scanf("%s" , s1) != EOF){
        scanf("%s" , s2);
        printf("%s\n" , ok(s1 , s2) ? "YES" : "NO");
    }
    return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics