练习题 - 序列数(数理逻辑)

前言

算法拾遗继续。今天才发现,原来我高中时使用的训练题有很多都是来自于湖南雅礼中学的。

题目

问题描述

有一个非递减的整数序列S1,S2,S3,……,Sn+1(Si<=Si+1)。定义序列m1,m2,…,mn¬为S的“M序列”,其中mi=(Si+Si+1)/2。
例如,S=(1, 3, 3, 5),则m=(2, 3, 4)。
现在给你序列m,要你求有多少个S序列的“M序列”是序列m。

输入(sequence.in)

第一行一个整数n,
下接n行,每行一个整数mi

输出(sequence.out)

一个整数,表示有多少个S序列的“M序列”是序列m

样例 sequence.in

3
2
5
9

sequence.out

4

样例说明: 存在如下四个数列S满足要求:

2,2,8,10;
1,3,7,11;
0,4,6,12;
-1,5,5,13。

数据范围

50%的数据n<=1000,mi<=20000
100%的数据2<=n<=100000,mi<=109.

解答

本题出自IOI2005第一式,事实上是一道很简单的题目。

令S序列的第一项为k,那么后面几项就可以写成关于k的多项式: S1=k S2=2m1-k S3=2m2-2*m1+k ……

然后根据S序列的非递减性质,有S1<=S2<=S3<=…. 所以有 k<=2m1-k 2m1-k<=2m2-2m1+k ……

可以得到n个关于k的不等式,而且都是有规律的,可以在O(n)的时间内解出形如 a<=k<=b 的结果。

由于k的值和S序列是一一对应的,所以k的取值的个数(b-a)就是满足要求的S序列的个数。

#include <stdio.h>

FILE *in, *out;
int n, shu[100001];

int main() {
  int i;

  in = fopen("sequence.in", "r");
  fscanf(in, "%d", &n);
  for (i = 1; i <= n; i++)
    fscanf(in, "%d", &shu[i]);
  fclose(in);

  int max, min, last;
  last = shu[1];
  max = last;
  for (i = 3; i <= n; i += 2) {
    last = last + shu[i] - 2 * shu[i - 1] + shu[i - 2];
    if (last < max)
      max = last;
  }

  last = 2 * shu[1] - shu[2];
  min = last;
  for (i = 4; i <= n; i += 2) {
    last = last - shu[i] + 2 * shu[i - 1] - shu[i - 2];
    if (last > min)
      min = last;
  }

  out = fopen("sequence.out", "w");
  fprintf(out, "%d\n", (max - min + 1 > 0 ? max - min + 1 : 0));
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-13 05:43:14 UTC.

Subscribe by RSS