| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1095 人关注过本帖
标题:求解这两题T_T
取消只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
结帖率:94.44%
收藏
已结贴  问题点数:100 回复次数:4 
求解这两题T_T
[Description]
E.T. Inc. employs Maryanna as alien signal researcher. To identify possible
alien signals and background noise, she develops a method to evaluate the signals
she has already received. The signal sent by E.T is more likely regularly
alternative.
Received signals can be presented by a string of small latin letters 'a' to 'z'
whose length is N. For each X between 1 and N inclusive, she wants you to find out
the maximum length of the substring which can be written as a concatenation of X
same strings. For clarification, a substring is a consecutive part of the original
string.
[Input]
The first line contains T, the number of test cases (T <= 200). Most of the test
cases are relatively small. T lines follow, each contains a string of only small
latin letters 'a' - 'z', whose length N is less than 1000, without any leading or
trailing whitespaces.
[Output]
For each test case, output a single line, which should begin with the case number
counting from 1, followed by N integers. The X-th (1-based) of them should be the
maximum length of the substring which can be written as a concatenation of X same
strings. If that substring doesn't exist, output 0 instead. See the sample for more
format details.

Sample Input  
2
arisetocrat
noonnoonnoon

Sample Output
Case #1: 11 0 0 0 0 0 0 0 0 0 0
Case #2: 12 8 12 0 0 0 0 0 0 0 0 0
[Hint]
For the second sample, the longest substring which can be written as a
concatenation of 2 same strings is "noonnoon", "oonnoonn", "onnoonno", "nnoonnoo",
any of those has length 8; the longest substring which can be written as a
concatenation of 3 same strings is the string itself. As a result, the second integer
in the answer is 8 and the third integer in the answer is 12.


(这题是区间DP,可是不会T_T)
[Description]
  Jerry loses himself in the interesting game: Fruit Ninja. Fruit Ninja is a game
of iPhone and iPad in which the players cut the fruits coming from the bottom of
the screen and gain the bonus from cutting more than two fruits with a single slice.
Once a fruit is cut, it breaks into small pieces and cannot be cut any more.
After months of training, he becomes pro of this game. Actually, he can cut all
the fruits on the screen at any time. Jerry also has a bad habit that he has no willing
to leave some fruits for the future cutting. In the other words, after Jerry cuts
the fruits, all the fruits on the screen breaks and no one left. That is why all
his friends call him “Juice Extractor”.
Now he only consider about the bonus, when he cuts more than two fruits, he can
gain some bonus scores as same as the number of fruits he slice at that time. For
example, if Jerry cuts 4 fruits with a single slice, he can get 4 scores from this
slice.
After Jerry gets the fruit schedule, he knows the appearing time and the
disappearing time for every single fruit. He can only cut a fruit into pieces between
its appearing time and disappearing time inclusive. He wants to know the maximum
possible bonus scores he can receive.
 
[Input]
  There are several test cases; the first line of the input contains a single
integer T, denoting the number of the test cases. (T <= 200)
For each test case, the first line contains an integer N, denoting the total
number of fruits. (1 <= N <= 1000)
The next N lines, each line describe a fruit. For each line, there are two
integers Xi and Yi, where Xi is the appearing time of the fruit and Yi is the
disappearing time of this fruit. (0 <= Xi <= Yi <= 1000000000)
 
[Output]
  For each test case, output a single integer denoting the maximum scores that
Jerry could possibly gain. See the sample for further details.
 
Sample Input
1
10
1 10
2 11
3 12
4 13
13 14

Sample Output
Case #1: 10

求思想,求高手指导,求交流,求各种求 emil:clddn3581927@
搜索更多相关主题的帖子: likely whose 
2011-05-17 21:43
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 2楼 waterstar
非常感谢
2011-05-17 22:30
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 5楼 waterstar
我们复旦邀请赛的题目
 第一题的意思大概是这样的 给你一串字符串 让你找出一个最长子串,能把他平分成一样的X份(X=1,2,3,.....字符串总长)
如第2个案例: noonnoonnoon 分成一份的最长子串是其本身所以最长12,
              分成2分的最长子串有 oonnoonn,(oonn,oonn)或noonnoon(noon,noon)......最长为8;
             分成3分的最长子串是noonnoonnoon(noon,noon,noon) 最长为12;
             分成4,5,....12份得最长子串不存在所以长度为0;

第2题的意思大概是这样的 给你一堆水果,告诉你每个水果出现在屏幕上的开始时间和消失时间
                        让你去切水果,切到2个或2个以上就得相应的分数,一个不得分,
                        其中切一刀以后屏幕上的水果会全部消失,问你最多能得几分
2011-05-18 15:44
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
终于把第一题做出来了,看到AC我泪流满面了
AC代码:

#include<iostream>
#include<cstring>
using namespace std;

int next[1009];
void getnext(char *str){
  int i=0;
  int j=-1;
  next[0]=-1;
  int len=strlen(str);
  while(i<len){
    if(j==-1|| str[i]==str[j] ){
      ++i;
      ++j;
      next[i]=j;
    }else j=next[j];
  }
}

int main(){
  int n;
  while(cin >> n){
    for(int cas=1; cas<=n; ++cas ){
      char str[1009];
      cin >> str;
      int sum[1009]={0};
      int len=strlen(str);
      for(int i=0; i<len; ++i ){
        getnext(str+i);
        int len1=strlen(str+i);
        for(int j=1; j<=len1; ++j){
          int ans=j-next[j];
          if(j%ans==0 && ans!=j){
            int tem=j/ans;
            int k=1;
            while(k<=tem){
              if(tem%k==0 && sum[k]<ans*tem) sum[k]=ans*tem;
              else if(sum[k]<ans*k) sum[k]=ans*k;
              ++k;
            }
          }
        }
      }
      sum[1]=len;
      cout << "Case #" << cas << ": ";
      for(int j=1; j<=len; ++j){
        cout << sum[j];
        if(j<len) cout << " ";
      }
      cout << endl;
    }
  }
  return 0;
}
2011-05-18 18:19
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 10楼 我菜119
是的
2011-05-18 19:06
快速回复:求解这两题T_T
数据加载中...
 
   



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

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