回 帖 发 新 帖 刷新版面

主题:[原创]TJU1096 & TJU1173 kitty 猫的基因编码 - 版本1/2

// 这次介绍一道 TJU 上的题: Kitty 猫的基因编码版本 1/2
// http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1096
// http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1173

// 这道题是 NOIP2004 普及组中 FBI 树的相似题, 算法基本上是没有区别
// 由于基因的长度是 2^k, 这就给了我们一个 dfs 算法的提示.

// 算法的描述基本这样:
// 构造一个二元树, 根就是原基因
// 然后左儿子就是基因的左边一半, 右儿子就是基因的右边,
// 最后直到某个儿子的内容都相同 (都是 0 或者都是 1) 就返回
// 否则继续 dfs 分析

Run ID User      Problem Result   Memory Time   Language Date  
243738 davidw017 1096    Accepted 44k    1 ms   C++      2005-05-15 17:13:39
243747 davidw017 1173    Accepted 188k   156 ms C++      2005-05-15 17:15:54

#include <stdio.h>
#include <string.h>

#define MAXN 256
/* 这里控制基因串的长度, 对于 1096 长度只有 2^8 = 256 个字节这里就定义为 256,
   对于 1173 长度有 2^17 = 131072 就要改成 131072, 即
   #define MAXN 131072
*/
char dnacode[MAXN];

bool enable[2];
/* enable[0] 的取值代表基因中 0 是否出现, enable[1] 即表示 1. */

/* 深度优先搜索过程
   char *code 表示要分析的基因, int length 表示基因的长度.
*/
void dfs(char *code, int length)
{
  if (length == 0) return;
  /* 如果基因长度等于 0 就返回 */

  memset (enable, false, sizeof(enable));
  for (int index = 0; index < length; index++)
    enable[code[index] - 48] = true;
  /* 清空 enable 数组, 然后分析基因, 若出现过 0 就把 enable[0] 置为 true,
     出现过 1 就把 enable[1] 置成 true. */

  if (enable[0] == true && enable[1] == true)
  /* 如果 0 和 1 都出现过, 那么相应的情况就应该是 C */
    printf("C");
  else if (enable[0] == true)
  /* 如果只是 0 出现过就是 A */
    printf("A");
  else if (enable[1] == true)
  /* 如果只是 1 出现过就是 B */
    printf("B");

  if (enable[0] == enable[1])
  {
    dfs (code, length/2);
    dfs (code + length/2, length/2);
  }
  /* 如果 enable[0] = enable[1] = true, 都出现过, 就说明需要继续分析
     按题目描述把基因段 code 等分为两个串, 继续搜索 */
}

int main()
{
  while (scanf("%s", dnacode) != EOF)
  {
    dfs (dnacode, strlen(dnacode));
    memset (dnacode, 0, sizeof(dnacode));
    printf ("\n");
  }
  /* 读入数据 - dfs - 清空数组 - 回车
  */
}

回复列表 (共12个回复)

沙发

用得着吗???
就是一道递归而已

板凳

悲哀……不ac的感觉就是不爽。。。
楼主竟然是这里的斑竹啊……我也要。。

3 楼

我想这里肯定有参加 NOIP2004 的人,就肯定有普及组的做过那个 FBI 树的人,最近好不容易找到这个题过了,就当给同学们说下吧……我错了:)

4 楼

悲哀...
初中组的题我40分钟400分
高中组……我没拿一等。。难得题目简单啊

5 楼

2004年noip的高中题目bt简单,没上300分真是对不起自己。(估计有道题整个错了)

6 楼

你们都好
我就后悔当时没去考
等我意识到
不能报名鸟

7 楼

我刚注册,问个菜鸟问题:
TJU的输入和输出是键盘输入,屏幕输出还是文件输入输出?
如果是文件,那么文件名是什么??????????

8 楼

不是文件。

9 楼

照上面几个楼主所说,那么信息学奥赛很简单咯?我也在学这个,但是我怎么觉得难呀,你们能否说说你们的学习经验呀给我借鉴一下呀~~!

10 楼

多谢多谢:
    很有意思
    对了,我有一个算“C”型的新方法:
            先两个一组转换,成ABC形式,存入数组
                 再按照:
                     A+A=A;
                     B+B=B;
                     A+B=CAB;
                     CN1+CN2=CCN1CN2;
的原则进行合并相临的就行了

我来回复

您尚未登录,请登录后再回复。点此登录或注册