| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1289 人关注过本帖
标题:字符串题目求解大牛请进
只看楼主 加入收藏
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
结帖率:40%
收藏
已结贴  问题点数:20 回复次数:16 
字符串题目求解大牛请进
竞赛题
C  Problem C

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制
描述

    我们都知道,学习英语单词最好的方法就是在相应的句子和语言环境中学习。小W最近定下了一个学习单词的计划,他要背n个单词,但他想通过背一篇文章中的一段来记住这些单词。

假定现在小W手中有一篇包含m个单词的文章,他想在文章中找出连续的一段,其中包含最多的他所要背的单词(重复的只算一个),并且使这段连续的单词长度最短。这样他就可以用尽量短的时间学习尽可能多的单词了。

 

输入格式

    第1行一个数n (1≤n≤1000)

    接下来n行每行是一个长度不超过10的字符串,表示一个要背的单词。

    接着是一个数m (1≤m≤100000 )

然后是m行长度不超过10的字符串,每个表示文章中的一个单词。
输出格式

    输出文件共2行。第1行为文章中最多包含的要背的单词数,第2行表示在文章中包含最多要背单词的最短的连续段的长度。
输入样例

3
hot
dog
milk
5
hot
dog
dog
milk
hot

输出样例

3
3

Provider
200831000423
搜索更多相关主题的帖子: 单词 Memory 字符串 竞赛题 
2013-04-06 18:19
embed_xuel
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:58
帖 子:3845
专家分:11385
注 册:2011-9-13
收藏
得分:4 
哥屋恩

总有那身价贱的人给作业贴回复完整的代码
2013-04-06 18:20
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
不要求代码   只要求给出思路  或者用到什么算法即可
2013-04-06 18:33
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:4 
又是你们学校的题?也不能去测试,有些乏味了。 这个算法时间复杂度不超过O(m)。

重剑无锋,大巧不工
2013-04-06 18:51
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
回复 4楼 beyondyf
要测试么,我给你账号就行啦
不过这个题没,老师没把他上去。我问问怎么办吧
2013-04-06 19:42
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
回复 4楼 beyondyf
要不你加我QQ吧  1004573547
2013-04-06 19:45
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
你们学校的OJ外网能访问得到?如果能,那不妨帮我申请一个帐号。QQ我几乎不用,所以意义不大。

题目要求的串的找法可以这么做,设f(i,j)包含了最多的待记单词,i、j分别表示它在原串中的左右边界

如果f(i, j - 1)中包含f(j, j),那么f(i, j - 1)中也包含了最多的待记单词

同理,如果f(i + 1, j)中包含f(i, i),那么f(i + 1, j)中也包含最多的待记单词

简单的动态规划应用。

重剑无锋,大巧不工
2013-04-06 20:28
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
回复 7楼 beyondyf
目前不能够申请账号。。。只有本校学生才可以用学号注册
上面那个题目http://www.soj.me/submit.php?problem_id=1222

2013-04-06 20:31
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
回复 7楼 beyondyf
我用最笨的方法做出来测试没错 提交不是超时 是错误
#include <iostream>
#include<cstring>
using namespace std;
  int c[100020],visit[100020];
void EN(char *a,char *b,int n,int k)
{

    if(strcmp(a,b)==0)   c[k]=n;

}

void dfs(int n,int i,int m)
{

}
int main()
{
  char a[1002][12],b[100002][12];

  int n,m;
  cin>>n;
  memset(c,0,sizeof(c));
  for(int i=0;i<n;i++)
    cin>>a[i];
  cin>>m;
 for(int i=0;i<m;i++)
    cin>>b[i];
for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
       EN(a[i],b[j],i+1,j+1);

int sum=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
{
   if(c[j]==i) {sum++;//  cout<<c[j]<<endl;
   break;  }
}
//cout<<sum<<"ijuio"<<endl;
int max=0,maxstr=2*m;
int flag;
for(int i=1;i<=m;i++){
      memset(visit,0,sizeof(visit));
      int  maxnum=0;max=0;
       flag=0;
    for(int j=i;j<=m;j++)
    {
        if(c[j]>0&&!visit[c[j]])
        {  visit[c[j]]=1;
            max++;   //cout<<"sss"<<max<<' '<<i<<endl;
        }
//cout<<"sss"<<max<<' '<<i<<endl;
        maxnum++;
    if(max==sum) {flag=1; break;}
    }
    if(flag&&maxnum<maxstr) maxstr=maxnum;
}
cout<<sum<<'\n'<<maxstr<<endl;


    return 0;
}

2013-04-06 20:38
a1004573547
Rank: 2
等 级:论坛游民
帖 子:78
专家分:25
注 册:2013-3-11
收藏
得分:0 
DFS那个是没用的
2013-04-06 20:39
快速回复:字符串题目求解大牛请进
数据加载中...
 
   



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

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