UVa 1339 Ancient Cipher

浏览: 146 发布日期: 2017-12-24 分类: c

Ancient Cipher

Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown



https://uva.onlinejudge.org/i...

Accepted Code

#include "stdio.h"
#include "string.h"

#define MAX 110

void count(char str[], int cnt[]);

int main()
{
    char str1[MAX], str2[MAX];

    while (scanf("%s%s", str1, str2) != EOF)
    {
        int cnt1[26] = { 0 }, cnt2[26] = { 0 };
        count(str1, cnt1); count(str2, cnt2);

        for (int i = 1; i < 26; i++) {
            for (int k = 0; k < 26 - 1; k++) {
                if (cnt1[k] > cnt1[k + 1]) {
                    int tmp = cnt1[k];
                    cnt1[k] = cnt1[k + 1];
                    cnt1[k + 1] = tmp;
                }
                if (cnt2[k] > cnt2[k + 1]) {
                    int tmp = cnt2[k];
                    cnt2[k] = cnt2[k + 1];
                    cnt2[k + 1] = tmp;
                }
            }
        }

        int flag = 1;
        for (int i = 1; i < 26; i++) {
            if (cnt1[i] != cnt2[i]) {
                flag = 0;
                break;
            }
        }

        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

void count(char str[], int cnt[])
{
    for (int i = 0; str[i] != '\0'; i++)
        cnt[str[i] - 'A']++;
}

Notes

题意:
给定两条字符串,可以对其中一条进行操作“重排字母顺序”和“一一映射”(当然也可以不操作),问操作后两串能否相同。

分析:
既然字母可以重排,则每个字母的位置并不重要,重要的是每个字母出现的次数。
这样可以先统计出两个字符串中各个字母的出现次数,得到两个数组cnt1[26]和cnt2[26]。
下一步需要一点想象力:只要两个数组排序之后的结果相同,输入的两个串就可以通过重排和一一映射变得相同。
这样,问题的核心就是排序。

//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//
// 作者:龙威昊
// 完成时间:2017/12/22
//
//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

返回顶部