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