有一题　大家讨论一下啊！！（注意范围的处理） [复制链接]

我发一题　大家　讨论一下！　注意数据的范围哦！



奶牛们开始对用电波望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波被从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星的心跳。

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（含）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。

符合的序列可能会重叠，并且至少重复一次的序列会被计数。

PROGRAM NAME: contact
INPUT FORMAT
第一行：
三个用空格分隔的整数: A, B, N; (1 <= N < 50)

第二行及以后:
一个最多200，000字符的序列，全是0或1; 每行有80个字符，除了可能的最后一行。


SAMPLE INPUT (file contact.in)
2 4 10
01010010010001000111101100001010011001111000010010011110010000000
在样例里，序列100出现了12次，而序列1000出现了5次。次数最多的序列是00，出现了23次。

OUTPUT FORMAT
输出N个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于N，输出存在的序列。

对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些频率。每行六个（除非少于六个剩下）。

SAMPLE OUTPUT (file contact.out)
23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100

大家最好可以把　算法　　和　程序（pascal)　都贴近来

不是非常理解，什么叫做：“对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些频率。每行六个（除非少于六个剩下）。”
还有楼主能不能给个简单一点的测试数据？

题目好长啊??

ioi 试题， 在usaco上出现，去找找吧。
我记得我做的时候为了他的输出格式搞了半天

大家 发点有用的题目来研究一下啊

usaco的...

我发一下,英文的

Contact
Russ Cox
For this problem, we keep track of every bit sequence we see. We could use the bit sequence itself as an index into a table of frequencies, but that would not distinguish between the 2-bit sequence "10" and the 4-bit sequence "0010". To solve this, we always add a 1 to the beginning of the number, so "10" becomes "110" and "0010" becomes "10010".

After reading the entire bit string, we sort the frequency table and walk through it to print out the top sequences.

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

#define MAXBITS 12
#define MAXSEQ (1<<(MAXBITS+1))

typedef struct Seq Seq;
struct Seq {
  unsigned bits;
  int count;
};

Seq seq[MAXSEQ];

/* increment the count for the n-bit sequence "bits" */
void
addseq(unsigned bits, int n)
{
  bits &= (1<<n)-1;
  bits |= 1<<n;
  assert(seq[bits].bits == bits);
  seq[bits].count++;
}

/* print the bit sequence, decoding the 1<<n stuff */
/* recurse to print the bits most significant bit first */
void
printbits(FILE *fout, unsigned bits)
{
  assert(bits >= 1);
  if(bits == 1)    /* zero-bit sequence */
   return;

  printbits(fout, bits>>1);
  fprintf(fout, "%d", bits&1);
}

int
seqcmp(const void *va, const void *vb)
{
  Seq *a, *b;

  a = (Seq*)va;
  b = (Seq*)vb;

  /* big counts first */
  if(a->count < b->count)
   return 1;
  if(a->count > b->count)
   return -1;

  /* same count: small numbers first */
  if(a->bits < b->bits)
   return -1;
  if(a->bits > b->bits)
   return 1;

  return 0;
}

void
main(void)
{
  FILE *fin, *fout;
  int i, a, b, n, nbit, c, j, k;
  unsigned bit;
  char *sep;

  fin = fopen("contact.in", "r");
  fout = fopen("contact.out", "w");
  assert(fin != NULL && fout != NULL);

  nbit = 0;
  bit = 0;

  for(i=0; i<=MAXBITS; i++)
   for(j=0; j<(1<<i); j++)
      seq[(1<<i) | j].bits = (1<<i) | j;

  fscanf(fin, "%d %d %d", &a, &b, &n);

  while((c = getc(fin)) != EOF) {
   if(c != '0' && c != '1')
      continue;

   bit <<= 1;
   if(c == '1')
      bit |= 1;

   if(nbit < b)
      nbit++;

   for(i=a; i<=nbit; i++)
      addseq(bit, i);
  }

  qsort(seq, MAXSEQ, sizeof(Seq), seqcmp);

  /* print top n frequencies for number of bits between a and b */
  j = 0;
  for(i=0; i<n && j < MAXSEQ; i++) {
   if(seq[j].count == 0)
      break;

   c = seq[j].count;
   fprintf(fout, "%d\n", c);

   /* print all entries with frequency c */
   sep = "";
   for(k=0; seq[j].count == c; j++, k++) {
      fprintf(fout, sep);
      printbits(fout, seq[j].bits);
      if(k%6 == 5)
       sep = "\n";
      else
       sep = " ";
   }
   fprintf(fout, "\n");
  }

  exit(0);
}