Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

两次快排可以了,详细说明+code

Posted by angrad at 2011-03-11 22:39:32 on Problem 2159
/*
举例说说这一题吧,比如下面
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator