| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3959 人关注过本帖
标题:求解oj寄居蟹与海葵问题
只看楼主 加入收藏
rainnese
Rank: 1
来 自:广州
等 级:新手上路
帖 子:51
专家分:0
注 册:2016-1-15
结帖率:56.25%
收藏
已结贴  问题点数:10 回复次数:3 
求解oj寄居蟹与海葵问题
题目是:
Description
寄居蟹与海葵是一对合作互助的共栖伙伴。海葵是寄居蟹最称职的门卫。它用有毒的触角去蜇那些敢来靠近它们的所有动物,保护寄居蟹。而寄居蟹则背着行动困难的海葵,四出觅食,有福同享。
但并不是所有寄居蟹和海葵都可以做搭档的。那就要看海葵的身体是不是符合寄居蟹的螺壳。
海葵的身体是有褶皱的,而寄居蟹的螺壳同样凹凸不平,我们可以用一个大写字母组成的字符串来表示它们的高低程度,其中A代表0,B代表1,依次类推。我们称两者相加等于25的就算是吻合,比如A和Z相吻合,B与Y吻合,依次类推。
只要海葵身体的部分序列与寄居蟹外壳的序列相吻合,就称他们可以一起生活。
比如:
1.海葵的褶皱是"ABCDEFG",寄居蟹是"ZYXWVUT"。这样,它们就可以完全吻合了。
2.海葵的褶皱是"AHBICJDKELFMGN",寄居蟹是"ZYXWVUT"。这样,寄居蟹可以和海葵的部分序列"ABCDEFG"相吻合 (注意:部分序列不改变字符原来的先后顺序,比如"ACB"就不是它的部分序列)。
3.海葵的褶皱是"ABCD",寄居蟹是"ZYXWVUT"。这样,虽然海葵可以和寄居蟹前面一段完全吻合,但它比寄居蟹要小,不能完全保护寄居蟹的安全,所有它们是不适合的。
4.海葵的褶皱是"HIJKLMNOPQ",寄居蟹是"ZYXWVUT"。这样,它们就可以完全不吻合了。
现给你两段字符串S1、S2,分别代表海葵和寄居蟹的外壳,为了它们以后各都能快乐地生活,请你帮忙计算一下它们是不是吻合的。


Input
输入包括多组测试数据。
每组测试数据包括两个字符串H、J,分别代表海葵的外壳和寄居蟹的外壳。可以保证它们的长度都小于100000。
输入以0 0结束。


Output
如果寄居蟹和海葵的外壳能吻合,就输出"Yes",否则输出"No"。


Sample Input
Original Transformed

ABCDEFG ZYXWVUT
AHBICJDKELFMGN ZYXWVUT
ABCD ZYXWVUT
HIJKLMNOPQ ZYXWVUT
0 0

Sample Output
Original Transformed

Yes
Yes
No
No
我的代码是:
程序代码:
#include<stdio.h>
#include<string.h>
char s1[100000], s2[100000];
int main()
{
    char a[26];
    for (int i = 0;i < 26;i++)
        a[i] = 'A' + i;
    while (scanf("%s%s", s1, s2) == 2&&s1[0]!='0'&&s2[0]!='0')
    {
        int flag = 1;
        for (int i = 0,j=0;i < strlen(s2);i++)
        {
            s2[i] = a[25 - s2[i] + 'A'];
            for (;j < strlen(s1);j++)
            {
                if (s2[i] == s1[j])break;
            }
            if ((j > strlen(s1) - 1) && i < strlen(s2))flag = 0;
        }
        if (flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

提交时是time limit exceeded,怎么修改?要用strchr函数之类的吗?
我用strchr函数也是同样的问题
程序代码:
#include<stdio.h>
#include<string.h>
char s1[100000], s2[100000];
int main()
{
    char a[26];
    for (int i = 0;i < 26;i++)
        a[i] = 'A' + i;
    while (scanf("%s%s", s1, s2) == 2 && s1[0] != '0'&&s2[0] != '0')
    {
        int flag = 1;
        char *p = s1;
        for (int i = 0, j = 0;i < strlen(s2);i++)
        {
            s2[i] = a[25 - s2[i] + 'A'];
            p = strchr(p, s2[i]);
            if (p == NULL || *p == '\0')
            {
                flag = 0;break;
            }    
        }
        if (flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

怎么做?

[此贴子已经被作者于2016-1-30 13:48编辑过]

搜索更多相关主题的帖子: 寄居蟹 字符串 动物 互助 门卫 
2016-01-30 13:35
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:5 
因为你的算法复杂度太高,换成strchr也不过是把内层循环换成了一个等价的函数而已,复杂度不变。

很报歉没时间分析,送段代码给你
程序代码:
#include<stdio.h>

int main()
{
    char a[100000], b[100000];
    int i, j;

    for(; scanf("%s%s", a, b), a[0] - '0'; puts(b[j] ? "No" : "Yes"))
        for(i = j = 0; a[i] && b[j]; i++)
            if(a[i] + b[j]- 2 * 'A' == 25) j++;
    return 0;
}

重剑无锋,大巧不工
2016-01-30 16:28
拉链
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:107
专家分:534
注 册:2016-1-22
收藏
得分:5 
回复 2楼 beyondyf
精炼强大!
2016-01-31 01:26
abec
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2017-3-9
收藏
得分:0 
回复 2楼 beyondyf
能解释下代码吗,看不懂QAQ
2017-03-09 17:37
快速回复:求解oj寄居蟹与海葵问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021623 second(s), 11 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved