《国家集训队论文集李天翼ppt课件》由会员分享，可在线阅读，更多相关《国家集训队论文集李天翼ppt课件（29页珍藏版）》请在装配图网上搜索。
1、 特殊情况主要分为两种：极端情况和简单情况特殊情况主要分为两种：极端情况和简单情况 极端情况：例极端情况：例1 Bra 1 Bra 简单情况：例简单情况：例2 Sko 2 Sko 2022-8-15问题描画如图，给定n个门,分别编号为0至n-1。每个门能够有多个输入端，但只需一个输出端。电路的信号电路的信号 有三种能够性：有三种能够性：0 0、1/21/2和和1 1。2022-8-15 编号为编号为0 0和和1 1的门没有输入端，的门没有输入端，0 0号门一直输出号门一直输出0 0，1 1号门一直输出号门一直输出1 1。对于其它的门，它的输。对于其它的门，它的输入信号中入信号中 0 0的个数比
2、的个数比1 1的个数多时，它输出的个数多时，它输出0 0；1 1的个数比的个数比0 0的个数多时，它输出的个数多时，它输出1 1；0 0的个数和的个数和1 1的个数一样多时，它输出的个数一样多时，它输出1/21/2；保证存在符合要求的输出形状。保证存在符合要求的输出形状。给定一个电路，要求尽能够多地确定每个门给定一个电路，要求尽能够多地确定每个门的输出结果。的输出结果。2022-8-15 令令Cj,iCj,i表示表示i i号门的一切输入端中，来自号门的一切输入端中，来自j j号门输出端的数量。设号门输出端的数量。设P(i)P(i)为为i i号门的输出号门的输出形状。形状。C2,0=1,C2,1
3、=1,C3,2=1,C3,4=1,C4,2=1,C4,C2,0=1,C2,1=1,C3,2=1,C3,4=1,C4,2=1,C4,4=14=1 其它均为其它均为0 02022-8-15 令令 ，即相当于即相当于i(i1)i(i1)号门一切输入信号的平均值。号门一切输入信号的平均值。U(i)1/2 U(i)1/2 U(i)1/2，那么，那么P(i)=1P(i)=1 1,01,0nj ijnj ijC P jU iC2022-8-15 令令Pmin(i)Pmin(i)和和Pmax(i)Pmax(i)分别为分别为P(i)P(i)在一切能在一切能够的电路中能取到的最小值和最大值，它们够的电路中能取到的
4、最小值和最大值，它们是是P(i)P(i)的极端情况。的极端情况。显然，假设显然，假设Pmin(i)=Pmax(i)(0in-1)Pmin(i)=Pmax(i)(0in-1)，那么那么i i号门的输出形状是固定的，否那么就号门的输出形状是固定的，否那么就不是固定的。不是固定的。因此，我们只需求求出因此，我们只需求求出Pmin(i)Pmin(i)和和Pmax(i)Pmax(i)。2022-8-15 假设假设P(k)P(k)变大，那么一切的变大，那么一切的U(i)(0in-1)U(i)(0in-1)也只能变大，而不能也只能变大，而不能够变小，而对应的够变小，而对应的P(i)P(i)也是如此。也是如此
5、。令令P(i)=Pmin(i)(0in-1)P(i)=Pmin(i)(0in-1)，可以，可以得到，此时的输出形状是符合要求的。得到，此时的输出形状是符合要求的。2022-8-15 无妨先将一切的门的输出形状都标为无妨先将一切的门的输出形状都标为0 0，此，此时只需时只需1 1号门不正确。从号门不正确。从1 1号门开场，将它的号门开场，将它的输出形状改为输出形状改为1 1。然后不断找到矛盾所在，。然后不断找到矛盾所在，进展迭代。由于每个门的形状最多变两次进展迭代。由于每个门的形状最多变两次0 0变变1/21/2，1/21/2变变1 1，每个门的输入的总数，每个门的输入的总数不超越不超越2000
6、00200000，因此在不超越，因此在不超越2 2*200000 200000=400000=400000次迭代后，迭代就会中止。迭代终次迭代后，迭代就会中止。迭代终止时，有止时，有P(i)=Pmin(i)(0in-1)P(i)=Pmin(i)(0in-1)。类似的，也可以求得类似的，也可以求得Pmax(i)(0in-1)Pmax(i)(0in-1)。2022-8-15 极端情况是特殊情况的一种表现方式。标题极端情况是特殊情况的一种表现方式。标题中的许多性质，往往会经过一些具有极端性中的许多性质，往往会经过一些具有极端性质的对象比如此题中的极值表现出来。质的对象比如此题中的极值表现出来。这就使
7、得我们可以以它们为重点调查对象，这就使得我们可以以它们为重点调查对象，来寻觅突破口和答案。来寻觅突破口和答案。假设一个骑士有挪动假设一个骑士有挪动(2,1)(2,1)，那么他在，那么他在A(4,3)A(4,3)点就可以挪动点就可以挪动到到B(6,4)B(6,4)或或C(2,2)C(2,2)C(2,2)B(6,4)A(4,3)111 12 2111 112 212 221 2221 22 12(1)()paqbbsb saba sbb s aa s ba s bs aba bs r 221paqbs r 121211222121()()pXqYp cadaq cbdbc paqbd paqbcs rds rr csdsr pXqY11221212111222121212121122112211121221212121210()()XXXa sa ska aka aXa ska aXa ska aXskaaXskaaYpXYpXXpkrXb sb sbka ba bXb ska bXb ska bXskabXskab
国家集训队论文集李天翼ppt课件
