| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
两次快排可以了,详细说明+code/*
举例说说这一题吧,比如下面
ABBCFEA(假设为dst)
CCGGHJB(假设为src)
不关心怎么从src变到dst,我先qsort一遍,两者就变成:
AABBCEF
BCCGGHJ
不深度题目,人工的都以为这个是NO.
但非也,我们再找一下两个串的相同字母数字序列.两者分别是:
22111
12211
这个你应该了解吧,就是AA为2,BB为2,C为1,E为1,F为1.
然后再把两串数字qsort就是
11122
11122
再比较一下,一样就YES了,否则NO.
总结个人WA原因:
1.第一次WA:小瞧水题、人太单纯被题目举例骗。
2.粗细复制,忘记修改src为dst导致总输出YES.
*/
人水代码也比较水,仅供大家新手交流参考。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void *a, const void *b)
{
return *(char*)a - *(char*)b;
}
int cmpint(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int i, a[101], b[101], count=0, j, k, q;
char dst[101], src[101], ch;
scanf("%s%s", dst, src);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
qsort(src, strlen(src), sizeof(char), cmp);
qsort(dst, strlen(dst), sizeof(char), cmp);
for (i=0, k=0; src[i]!='\0';)
{
j = i;
ch = src[i];
count++;
while(src[++i] == ch)
{
count++;
}
a[k++] = count;
count = 0;
}
//WA了好几次在于下面for循环里dst一直是复制上面的src没改过来,copy是双刃剑啊.
for (i=0, q=0, count = 0; dst[i]!='\0';)
{
j = i;
ch = dst[i];
count++;
while(dst[++i] == ch)
{
count++;
}
b[q++] = count;
count = 0;
}
qsort(a, k, sizeof(int), cmpint);
qsort(b, q, sizeof(int), cmpint);
for (i=0; i<k; i++)
{
if (a[i] != b[i])
{
printf("NO\n");
break;
}
}
if (i==k)
{
printf("YES\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator