国家集训队2006论文集_李天翼

论文

从特殊情况考虑

复旦附中 李天翼

[关键字] 特殊情况 信息学竞赛 [摘要]

从特殊情况考虑是一种重要的数学思想。而特殊情况主要分为简单情况和极端情况。

本文通过几道例题，来说明从特殊情况考虑这一思想在信息学竞赛中的应用，并提炼出它们的共同点，揭示这一思想的重要内涵。

论文

例1 Bra

§1问题描述 §2 解决方案 §3小结 例2 Sko

§1 问题的提出 §1.1 问题描述 §1.2 最初的想法 §2 两个预备算法

§2.1 Euclid算法 §2.2 模线性方程的解法 §3问题的解决

§3.1 猜想的证明 §3.2 算法的实现 §4 小结 例3 Polygon

§1 问题描述 §2 问题的解决

§2.1 一个朴素的想法 §2.2 考虑特殊情况

总结

论文

例1

1.问题描述（由POI 2003-2004 Bra改编）

考虑一个有n个门组成的电路。这些门被标号为0、1、2、……、n-1。每个门有固定数目的输入和一个输出。输入和输出可以是0、1、1/2三种状态中的任意一个。每个输入连接某个门的一个输出。输入的状态与它所连接的输出状态相同。每个输出可以与数个输入相连。标号为0和1的门很特殊，它们没有输入，标号为0的门总输出0，标号为1的门总输出1。我们说，一个门的输出状态是“有效”的，当且仅当满足下列条件之一。

a)它等于0并且这个门的输入中0比1多。

b)它等于1/2并且这个门的输入中0和1一样多。 c)它等于1并且这个门的输入中1比0多。

d)它等于这个门的编号，且这个门的编号是0或1。

如果所有的门的输出状态是“有效”的，那么我们说这个电路是“有效”的。如果一个门的输出状态在所有“有效”的电路中都是一样的，那么它的输出状态是固定的。保证存在“有效”的电路。 任务：

写一个程序

从标准输入中读取电路的描述

对每一个门，检查它的输出状态是否是固定的，如果是固定的，确定它的状态。

向标准输出中写入输出状态固定的门的状态 输入：

标准输入包含一个整数n，2≤n≤10000。接下来的n-2行包括每个门的连接的描述。第i行描述第i个门的输入：第一个整数k_i(k_i≥1)，表示这个门有

k_i个输入，接下来的k_i个数表示这k_i个门的编号。行内整数之间用空格分隔。每个门的输入的总数不超过200000。 输出：

你的程序应该输出n行到标准输出中。第i行包括的内容，取决于编号为i-1的门的输出状态。

0---如果它总是0 1/2---如果它总是1/2 1---如果它总是

1 ?---如果它不确定 样例： 输入数据： 5 2 0 1 2 4 2 2 2 4

论文

输出数据： 0 1 1/2 ? ?

2.解决方案

由于图中有环，对于每个门，我们难以直接判断它的输出状态是否是固定的，这给解题带来了困难。

设P(i)为i号门的输出状态(0≤i≤n 1)。

令Pmin(i)和Pmax(i)分别为P(i)在所有“有效”的电路中能取到的最小值和最大值，它们是P(i)的极端情况。

显然，若Pmin(i)=Pmax(i) (0≤i≤n 1)，则i号门的输出状态是固定的，否则就不是固定的。

因此，我们只需要求出Pmin(i)和Pmax(i)。

令Cj,i表示i号门的所有输入端中，连接j号门输出端的数量。 考虑 n 1 Cj,iP(j)∑j=0

n 1

Cj,i∑j=0

即相当于i号门(2≤i≤n 1)所有输入状态的平均值。

根据题目中“有效”的定义，在所有“有效”的电路中： 若该值小于1/2，则P(i)=0 若该值等于1/2，则P(i)=1/2 若该值大于1/2，则P(i)=1

我们进行这样的操作。先将所有的门的输出状态都标为0，此时只有1号门不是“有效”的。从1号门开始，将它的输出状态改为1。然后不断找到矛盾所在，进行迭代。

下面证明，如此迭代必然能够终止，并且迭代终止时，

P(i)=Pmin(i)(0≤i≤n 1)。

证明：假设命题不成立。

由于操作开始时，对 i(0≤i≤n 1)，满足P(i)≤Pmin(i)。

因为命题不成立，所以必然在某个时刻开始出现P(k)>Pmin(k)。而在此之前的那个时刻，对 i(0≤i≤n 1)，仍然满足P(i)≤Pmin(i)。 ．．

论文

n 1

∑C

考虑

j=0

j,k

P(j)

，即k号门所有输入状态的平均值。这个值已经相

j,k

∑C

j=0

n 1

n 1

当大，使得P(k)取Pmin(k)不符合要求。

∑C

注意到，

j=0

j,k

P(j)

≤

j,k

∑C

j=0

n 1

j,k

Pmin(j)

，这意味着不存在一个“有效”

j,k

∑C

j=0

n 1

∑C

j=0

n 1

的电路，满足P(k)=Pmin(k)。而这一点与Pmin(k)的定义矛盾。

证毕。

由于每个门的状态最多变两次（0变1/2，1/2变1），每个门的输入的总数不超过200000，因此在不超过2*200000=400000次迭代后，迭代终止。此时有P(i)=

Pmin(i) ((0≤i≤n 1)。

类似的，我们可以求得Pmax(i)(0≤i≤n 1)。至此，整个问题获得解决。

3.小结

极端情况是特殊情况的一种表现形式。题目中的许多性质，往往会通过一些具有极端性质的对象（比如本题中的取极值）表现出来。这就是使得我们可以以它们为重点考察对象，来寻找突破口和答案。

例2

1.问题的提出

1.1问题描述

Sko（POI 2004-2005）

骑士在一个无限大的棋盘上移动。他能够执行的每种移动可以表示为一对整数。一对整数(a,b)表示骑士可以从坐标为(x,y)的点移动到(x+a,y+b)的点或

(x a,y b)的点。每一个骑士有一个由若干对整数所组成的集合，这若干对整

数表示了所有这个骑士可以进行的移动。对于每一个骑士，可以假定它从原点

(0,0)出发，所能够到达的点，不全在一条直线上。

我们说两个骑士是“相同”的，那意味着两个骑士从(0,0)出发，所能够到达

论文

的点（可以走任意步，且两个骑士所走的步数不一定要一样），是完全一样的。可以知道，对于每一个骑士，都有一个与他“相同”，且能被两对整数所表示的骑士。 任务：

写一个程序，进行以下操作：

从标准输入中读入表示这个骑士的移动的若干对整数。

确定两对整数，两对整数表示了一个“相同”的骑士的移动。 输出这两对整数到标准输出。 输入：

在标准输入的第一行中有一个整数n，表示整数对的数目(3≤n≤100)。在接下来的n行中，每行一对整数表示骑士的一种移动。在这n行中，两个整数ai和bi被一个空格隔开。( 100≤ai,bi≤100)。我们假设(ai,bi)不为(0,0)。

输出：

在标准输出的第一行，输出两个用空格隔开的整数a和b。第二行输出两个用空格隔开的整数c和d。( 10000≤a,b,c,d≤10000) 这四个整数应该满足一个。 移动被(a,b)和(c,d)所描述的骑士与输入数据里描述的骑士“相同”

样例：

输入数据： 3 24 28 15 50 12 21

输出数据： 468 1561 2805 9356 或 3 0 0 1

1.2最初的想法

要考虑给定的骑士与什么样的骑士“相同”，首先要知道给定的骑士能到达哪些点。不妨将一个骑士从(0,0)点出发，能够到达的点称为该骑士的可行点。一个骑士的可行点的集合称为该骑士的可行点集。

棋盘 …… 此处隐藏：8425字，全部文档内容请下载后查看。喜欢就下载吧 ……