tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

刘汝佳老师:形形色色的数学(非传统)题


2014全国青少年信息学奥林匹克 冬令营讲课

形形色色的“数学题”
(版本20140212c)

刘汝佳 rujia.liu@gmail.com

目录
? ? ? ? ? ? 开胃菜 各种计算 各种奇怪的策略题 几何题和“假几何题” 神题? Bonus: 其他讨论题

题目

来源们…
? ? ? ? IPSC Project Euler ACM/ICPC UVa Online Judge

随便说点…
? 先学数学知识、技巧还是直接做题? ? 数学思维、计算思维... ? 工具软件?

开胃菜

1. Quite the cheater! (IPSC 2013)
? 输入两个整数a, b,构造一个序列,使得它 的平均值为a,方差为b。限制:
– 序列长度n要满足10<=n<=1000 – 每个元素ai要满足-109<=ai<=109

? 在本题中,方差为

2. Rotate to divide (IPSC 2011)
? 输入正整数b, k,找出最小的b进制整数n, 使得n左移一位(即把n的最右数字移到最 前面)之后缩小为原来的1/k。n的b进制中 至少要有两个数字 ? 比如b=5, k=2的解为(31)5,因为(31)5=2*(13)5。 ? b>=2, k>=1, b,k<=2,000,000

3. Broadway (IPSC 2010)
? 有一个无限大网格(对于任意整数Z,有直 线x=Z和y=Z),另外有一条Broadway,即直 线Px+Qy=R。 ? 输入整点A, B, P, Q, R, 求A到B的最短路。只 能沿着网格或者Broadway走,只能在交点 处换路。

? 结论1:Broadway只会进入一次。因此可以 用 dijkstra 算法,结点是 A 、 B 以及 Broadway 上的整点 ? 结论 2 : A 一定是“直达” Broadway ,并且 离开Broadway之后一定是直达B。所以进入 和离开Broadway的位置各最多两个

4. Fair coin toss (IPSC 2012)
? 有n枚硬币,第i枚有Pi的概率正面朝上。每 个硬币各抛一次,正面朝上看做1,背面朝 上看做0,把所有硬币得到的数异或起来决 定最后得到的数 ? Easy:是否存在一个子集合使得0和1的概率 相等? n<=10 ? Hard:有多少个子集合使得0和1的概率相 等? n<=60

? 只要有一枚fair coin,把它放到最后抛,就 可以得到公平的结果 ? 如果所有硬币都不是fair的,无论怎么抛, 都不会得到公平的结果

5. Piece of cake! (IPSC 2010)
? 有一个A*B*C的长方体,切D次,每次沿着 某个平行于坐标平面的方向切下来一个厚 度为1的长方体。要求最后剩下的长方体的 体积最大 ? 0<A,B,C<=1018, 0<=D<=A+B+C-3

6. Rebel Alliance attack (IPSC 2012)
? 输入r<=44444,统计有多少个整数四元组 (x,y,z,w)满足x2+y2+z2=w2, w<r。

各种计算: 代数、数论、计数、概率…

行列式(determinant)
? Leibniz公式:

? 这里的求和符号取遍1~n的所有排列σ,比 如σ=[2,3,1]时σ1=2, σ2=3, σ3=1。1~n的所有排 列(称为n个元素的对称群)记为Sn。 ? sgn(σ)是signature,当逆序对数为偶数时为 +1,否则为-1

3*3行列式的展开

行列式的性质与计算
? 用高斯消元法可以在O(n3)时间内计算出一 个n*n矩阵的行列式。

积和式(permanent)
? 和行列式很接近,但是去掉符号项,全部 为正,即

? 组合意义:
– 二分图完美匹配的个数 – 任意图的圈覆盖的个数

? 计算perm(A)是#P-完全的

关于圈覆盖(cycle cover)
? 圈覆盖:从n个结点的有向图(可以有自环) 中选出n条边,每个结点恰好属于一个圈, 即每个结点恰好有一条入边和一条出边 ? 一个结点排列对应一个圈覆盖,而且排列 的循环分解中的每个循环对应图上的一个 圈。

Lucas定理
? 对于非负整数m, n和素数p:

? 其中m和n的p进制展开式如下:

? 当m<n时规定C(m,n)=0

7. A huge binomial coefficient (PE 365)
? 令M(n,k,m)表示C(n,k) mod m,求满足 1000<p<q<r<5000且p,q,r均为素数的所有 M(1018,109,p*q*r)之和。

? 对于范围内的所有p,用Lucas定理计算 M(1018, 109, p) ? 然后枚举三元组(p,q,r),用中国剩余定理计 算M(1018,109,pqr)。 ? …然后就没 了

8. Idempotents (PE 407)
? 记M(n)为满足a<n且a2=a(mod n)的最大a, 比如M(6)=4。求M(1)+M(2)+…+M(107)

? a2=a(mod n)等价于n是a2-a=a(a-1)的约数。 因为a和a-1互素,所以n可以写成m1*m2, 其中m1是a的因子,m2是a-1的因子,且m1 和m2互素。 ? 枚举a,然后枚举a和a-1的所有因子,组合 得到一个n,更新M(n)。

9. One-child Numbers (PE 413)
? 如果一个d位正整数(没有前导0)恰好有一个 连续子串是d的倍数,我们说它是一个onechild number。比如5671只有子串56是4的倍 数, 104和1132451也是one-child number ? 设F(n)为小于n的one-child number的个数, 比如F(10)=9, F(103)=389, F(107)=277674 ? 求F(1019)

10. Nontransitive sets of dice (PE 376)
? 考虑如下三个非标准筛子:
A: 1 4 4 4 4 4 B: 2 2 2 5 5 5 C: 3 3 3 3 3 6

? 可以验证
– 游戏者1拿筛子A,拿B的胜率为7/12>1/2。 – 游戏者1拿筛子B,拿C的胜率为7/12>1/2; – 游戏者1拿筛子C,拿A的胜率为25/36>1/2

? 这里的“胜”不含平局的情况。 ? 考虑六个面的筛子,每个数字为1~30,有 多少个筛子集{A,B,C}满足这个条件? ? 数字集相同的筛子被看做相同的筛子

? 其实…答案是一个多项式!

? 可是,如果得到这个多项式呢?

11. Going to the movies (IPSC 2009)
? 有n个人去电影院看电影。给她们预留了最 后一行座位,共k个。但是打票机器出了故 障,每个人拿到的座位编号都是1~k的均匀 随机整数。 ? 每个人拿到票之后从1号座开始往k号座走。 先走到自己的座位旁。如果没人,就直接 坐下去;如果有人,就继续走,走到第一 个没人的座位坐下去。如果走到最后都没 座,她就不看电影了。

? 输入n, k,求至少一个人不看电影的概率, 用分数表示 ? 例如n=k=3,概率为11/27 ? 票有33=27种可能,有人不看电影的情况有 以下11种:133, 222, 223, 232, 233, 313, 322, ? 323, 331, 332, 333。 ? 比如,若票为322,前2个女孩分别坐在位 置3和2,第3个女孩找不到座位。

? 经典思路:线转化为圈,利用对称性 ? 假设有k+1个椅子围成一圈,每张票上写着 1~k+1(而不是1~k),因为概率均等,我们 统计有多少种方案导致椅子k+1上坐着人 ? 一共有(k+1)n种可能的情况。为了方便叙述, 我们假定每种情况模拟一遍,每次在没人 坐的椅子上放一枚硬币(每次恰好有k+1-n 把椅子没人坐),则所有情况都模拟完之 后每把椅子上都有(k+1-n)(k+1)n-1枚硬币,也 就是说,有(k+1-n)(k+1)n-1种情况下,椅子 k+1上没人坐。 ? 改回每张票写1~k之后,这个结论不变。

12. Do the grading (IPSC 2013)
? 输入由小写字母组成的字符串S,判断是否 a~z的所有26!个排列都作为子序列(不一定 连续)出现。比如若只考虑前3个字母, abcabac满足条件,但abccba不满足(不包 含bac和cab) ? Easy: 判断是否满足条件。T<=150, |S|<=2500 ? Hard: 统计有多少个排列不存在。T<=20, 所 有|S|之和不超过1000

? Easy: f(S)表示包含集合S所有全排列的最短 前缀长度,可以递推:枚举字符a,检查f(S{a})的大小,然后找到最近的a。 ? 时间复杂度为O(s2s),这里s=26。需要预处 理:next(p,a)表示位置p之后字符a第一次出 现位置 ? Hard: g(S,L)表示集合S有多少个全排列不包 含在前L个字母组成的前缀中。递推方式类 似,对于字符a,检查g(S-{a}, i),其中i是前 缀L中字符a最后一次出现的位置。不要保存 不必要的状态 ? 因为是IPSC,所以可以用大内存+并行…

13. Bozo sort (PE 367)
? Bozo sort:如果没排好序则随机选三个数, 然后随机重排(3!=6种重排方式的概率均等) ? 对于1~4的所有4!种排列,排序步数的期望 的平均数为27.5 ? 对于1~11的所有11!种排列,排序步数的期 望的平均数是多少?

? 有56种办法把11写成若干正整数之和(顺 序不重要) ? 状态数为56的Markov链

14. Inside Job (IPSC 2010)
? 输入一个简单n(n<=500)边形R,对于R内的 任意点p,我们计算p到所有边的距离之和s。 ? 如果p在R内均匀分布(即:假设R的面积为 A,则对于R内的任意一个区域,如果它的 面积为B,则p落在该区域的概率为B/A), 求s的数学期望。

? 根据期望线性性,每条边分别求期望,再 加起来即可

? 对于一条边,先把整个图形旋转平移,使 得这条边在x轴上,则所求值为

? 其中f(y)表示一条y坐标为y的水平直线和多 边形相交,落在多边形内部的线段的长度 之和

? 你在赌场上玩一个游戏,每次的赌注是1美 元,赢了会得到2美元,输了什么也得不到。 赌场有一个优惠:在任何时候,赌场可以补 偿你x%的损失。使用优惠之后你可以继续玩, 也可以退出赌场。退出赌场之前最多只能使 用一次这样的优惠。 ? 比如x=20,你玩了10次,赢了3次,总共损 失10-3*2=4元,使用优惠后损失3.2元。但如 果你赢了6次,总共获利6*2-10=2元。 ? 假定每局比赛获胜概率为p%,输入x, p(0<=x<100, 0<=p<50),输出最优策略下最大 的期望获利。

15. Hey, Better Bettor (ACM/ICPC WF2013)

? 策略可以用两个整数表示:L, W,表示输L 元钱以后退出(实际只输(1-x)L元),或者 赢W元以后退出。这样,在确定L和W之后 只需要确定输钱的概率,就可以计算出数 学期望。 ? 假设你现在有D元钱,设最终赢钱的概率为 P(D),则P(W)=1, P(L)=0。可以得到一个方程: ? P(D)=p*P(D+1)+(1-p)*P(D-1),整理后得到线 性递推式:P(D+1)=P(D)/p – P(D-1)*(1-p)/p, 用传统方法求解即可。 ? 最后遗留一个问题:如何求最优的L和W?

16. Lovely Stamps (IPSC 2010)
? 有n种不同的1分邮票和m种不同的2分邮票。 一共有k分钱,必须全部花光,有多少种方 式买邮票?输出答案除以P的余数 ? 比如n=m=2, k=4,有三种情况 ? 买两个2分邮票,3种方案 ? 买两个1分和一个2分,2*3=6种方案 ? 买四个1分,有5种方案 ? 3<=p<=106, 0<=n,m<=300, 1<=k<=1012

? 设fi,t表示只有t个1分邮票(没有其他面值的 邮票),有多少种方法可以花完i分钱,gi,t 表示只有t个2分邮票,有多少种方法可以花 完i分钱,则答案不难算出。 ? 不难发现gi,t可以用fi,t得到,所以关键在于计 算fi,t。如何计算fi,t? 转化为不定方程后用组 合方法求解即可 ? 枚举2分邮票的张数i,整个问题的解等于:

? 直接计算这个时间需要O(k)时间,太慢。 ? 利用生成函数(母函数),可以得到一个 非常数学(推导很麻烦,但效率很高)的 解,不过使用一个小技巧,可以得到一个 虽然比“数学解”的效率低得多,但足以 解决Hard的算法。算法的关键在于这个等 式:

? 其中pt>y。

? 取pt>n且pt>m,我们有:

? 这样,我们就可以把求和项分成pt组,每一 组的值都相同

? 时间复杂度为O(pt)

17. Simple Encryption (ACM/ICPC KL 2010)
? 输入K1(0<K1<50000),解方程
? 即K1的K2次方的十进制末12位等于K2。注意, K2的十进制必须恰好包含12个数字,不能有 前导0。输入保证有解。

? 范围太大,不好办…先试试模103吧!K1=123 的唯一解为K2=547 ? 把模改为104后,惟一解是K2=2547 ? …

18. Amazing Mazes! (PE 380)
? 有多少个m*n矩形迷宫,使得左上角到其他 每个格子恰好有一条通路。

? 比如C(2,2)=4, C(3,4)=2415, 求C(100,500)

? Matrix-tree定理:G的生成树的个数为 Kirchhoff矩阵C(G)=D(G)-A(G)的任何一个n-1 阶主子式的行列式的绝对值。
– D(G)为 度数矩阵,只有i=j时dij等于vi的度数,其 他值为0 – A(G)为邻接矩阵,当且仅当存在边vij时aij=1,其 他值为0 – n-1阶主子式是把第r行第r列(1<=r<=n)同时去掉 以后得到的新矩阵,用Cr(G)表示

? 可是!一个n=50000的矩阵的行列式也不是 那么好求的…

怎么办?
? 猜一猜?

? Band Matrix?

19. Hash (IPSC 2010)
? 考虑分块hash:先把文件分成n个256个字 节的block,分别计算128-bit的MD5,然后 把结果组合起来 ? XOR-HASH:把所有MD5取异或 ? ADD-HASH:把所有MD5加起来模2128。 ? 输入一个128-bit无符号整数,构造一个文件, 使得hash值为该整数 ? Easy: n=256, 使用XOR-HASH ? Hard: n=128, 使用ADD-HASH

? 本题不需要用MD5的任何性质 ? Easy: 随机构造256个集合,每个集合只有两 个元素,分别算出每个元素的MD5。然后 每个集合二选一。令bi=0表示第i个集合选的 是第1个元素,bi=1表示选择第2个元素。共 n=256个未知数 ? 各bit独立,所以每个bit都可以列一个模2的 线性方程,共128个方程。高斯消元 ? (吐槽一下:比赛时的两个checker,有一 个是错的,害得我耽误了不少时间检查…)

? Hard:和Easy类似,随机生成128个集合 L1~128,在每个集合中选一个xi,但是每个集 合不是只有两个元素,而是有多个… ? 我们先解决目标hash值为0的情况,即: ? 等这个问题解决之后,只需要给L1的每个元 素都减去h,问题就转化为了目标为0的情 况了。 ? 下面我们先考虑4个集合的情况,然后把方 法推广到128个集合。以下所有的加法都是 模2128的

? 算法分成两步, ? 第一步:把L1和L2合并成L1,2,类似可以得到 L3,4 ? 第二步:把L1,2和L3,4合并为L1,2,3,4 ? 这里的“合并”有两种不同的含义,下面 详细叙述。这个“分阶段合并”算法是基 于这样的想法:随机串的MD5值比较均匀, 因此在一个2128个元素的集合中,很可能包 含一个和为0的元素(即我们想要的结果)。

? 完全合并。两个集合L1和L2合并成{(x1,x2)}, 其中xi是Li中的元素。这样的话,如果L1,2和 L3,4各有264个元素,合并之后的L1,2,3,4很可能 包含0。要达到这样的效率,Li各需要有232 个元素。这个方法的总时间复杂度为264 (注意计算L1,2,3,4时可以用查表法) ? 精挑细选。另一个极端是 L1,2={(x1,x2)|x1+x2=0},这样从L1,2里任选一个 元素,L3,4里也任选一个元素,拼起来就可 以了。可惜,为了让L1,2非空,Li各需要有 264个元素。

? 看来得折中一下。比如,让L1,2等于那些满 足x1+x2的最后z个比特均为0的元素。如果Li 各有2s个元素,那么合并以后有22s个元素, 平均2z个元素就有一个满足条件(最后z个 比特均为0),因此合并后集合的大小约为 22s-z。合并时间的级别约为2max (s,2s-z)。 ? 最初取s=128/3。 ? 第一阶段:取z=128/3,则合并之后L1,2的 s=128/3。 ? 第二阶段:取z=128*2/3(后面的0直接无 视),合并后L1,2,3,4的s=0,即约有1个元素 ? 时间复杂度级别是2128/3=243。

? 4个集合,时间复杂度为243,推广到128个 集合,时间复杂度岂不是更高? ? 恰恰相反!初始取s=16,每个阶段均取z=16, 则每个阶段的单次合并都只需要216时间, 并且合并之后集合大小仍是s=16。 ? 最后一个阶段可以取z=32,因为最后一次合 并之后集合里只需要有一个元素即可。

20. (False) faces (CERC 2009)
? 输入一个左右各n(n<=300)个结点的二分图, 判断完美匹配的个数是不是4的倍数

? 积和式很难计算,但是行列式好算 ? 对比二者,只是其中一些项的正负号不同 ? 所以如果行列式不是2的倍数,输出肯定应 该是NO

各种奇怪的策略题

21. Lame crypto (IPSC 2011)
? Bob喜欢给女朋友Alice发PNG图片。他不想 让其他人看到这些图片,所以他用自创的 SSP加密协议和Alice通讯。 ? 你是一个坏人。你收买了他们的网络提供 商,使得Bob发给Alice的信息都发得特别慢, 使得你有空把图片截获下来篡改成恶意图 片,这样子Alice看完图片以后就会跟Bob生 气(因为她以为是Bob发的)

? 为了达到这个目的,你需要了解SSP协议。 Alice有一个私钥KA,Bob有一个私钥KB。每 当Bob准备发一个长度为n的消息M时,会 发生以下事情
– Bob选KB的一个连续序列K’B,然后把M XOR K’B 发给Alice – Alice收到C=M XOR K’B之后选KA的一个长度为n 的连续序列K’A,然后把C XOR K’A发给Bob – Bob收到D之后把D XOR K’B发给Alice – Alice收到E之后,所求消息M=E XOR K’A

? 协议的核心在于XOR有交换律且A XOR A = 0

? 每次通讯发了三次信息:B->A, A->B, B->A ? Easy: 所有消息都可以改 ? Hard: 只能修改Alice发给Bob的消息(即只 有一次机会!) ? 所有消息的长度都是10000,私钥长度均为 50000。Easy和Hard各有一套KA和KB,可以 收听多次通讯(KA和KB不变),但是一旦修 改了消息,并且那次通讯的最后Alice没有 收到恶意图片,则算作Wrong Answer。 ? 当Alice收到最终图片之后的6分钟后才会发 起下一次通讯,所以在300分钟比赛时间内 需要合理安排解题时间

? Easy很容易解决:比如第一次改成全0,然 后就可以拿到K’A了,然后… ? Hard比较麻烦,因为每次的信息量比较小… 不过50000仅仅是10000的5倍,所以经过很 多次通讯之后,随机到的K’A和K’B会有很多 重叠!所以…

22. Feeling Lucky (IPSC 2013)
? N个硬币,其中一个是假的,可能比其他硬 币重或者轻(概率均等)。你可以发s封信, 每封信可以猜答案或者提出k个称量请求。 收信人很懒,因此每个请求有0.7的概率被 无视(收信人不会真的称量,而是随机给 出一个结果),而其他情况下会告诉你正 确结果。你无法分辨出哪些结果是随机给 出的。 ? 要求猜出答案,使得正确率不低于99% ? Easy: n=81, s=6, k=50 ? Hard: n=250, s=11, k=15

? Easy可以用确定性方法解决 ? Hard只能有概率方法
– 随机问问题 – 找一个符合尽量多结果的解

? 还可以做得更好:用贝叶斯方法,不是随 机问问题,而是问一个“期望获得最多信 息”的问题

23. Candy for each guess (IPSC 2011)
? 猜数字游戏:H选一个0~n-1的整数x给G猜。 每次G猜一个整数g,H告诉他是g<x, g>x还 是g=x。H希望猜的次数尽量多,G希望猜的 次数尽量少。不能猜一个不会获得新信息 的数(比如,得知x>3以后不能猜2)。策略 用决策树的先序遍历表示 ? Easy: H和G只有8岁,因此G只会从一些确定 性策略(比如按照0, 1, 2…的顺序一个一个 猜,或者是二分查找)中随机选一个来猜 ? Hard: H和G都长大了,学会最优策略了

? Easy: G有k个策略,每次随机选一个。求H 的最优策略(用每个数的选择概率表示)

? Hard: 输入n,输出H的最优策略(表示法同 上)和G的最优策略(用若干个决策树先序 遍历及其概率表示)

? Easy: 对于每个数x,求出G选每个策略时, 猜测次数的期望,然后选 择让期望最大的 那个x,H每次都选它。 ? Hard: 这个问题恐怕比大多数人想象的要困 难!为什么呢?当G长大以后,突然发现H 每次都选同一个数x,于是他就改成直接猜x! 后来,H发现G改策略了,于是自己也改策 略,然后G又改… ? 这是一个zero-sum游戏,一方越好,另一方 就越差。

? 想象有一个矩阵,每行是H的一个选择(要 猜的数),每列是G的一个选择(策略), 则我们的问题是:H(按照某种概率分布) 随机选一行,G随机选一列,H希望选出的 数尽量大,G希望选出的数尽量小 ? 比如n=3,设H的概率分布为hi,选出的数为 v,则有如下线性规划(目标是最大化v):

v=min{…}

? 问题:n=16时有35357670种策略,怎么办? ? 结论1:H选i和选n-1-i的概率应当一样。 ? 这样,很多策略完全败给另外一些策略, 不需要考虑。比如:

? n=16时,需要考虑的策略小于100,000个

24. Flipping coins (IPSC 2011)
? n个人玩游戏:每人抛一枚硬币(正反概率 相等),抛完以后不看,立刻贴在脑门上。 这样,每个人只能看到其他n-1个人脑袋上 的硬币。每个人需要猜自己脑门上的硬币 是正还是反。可以写head/tail/pass,其中 pass表示弃权。如果至少有一个人猜对且没 有人猜错(即没猜对的人都是弃权),则 游戏成功。 ? 输入3<=n<=8,求一个策略使得成功概率最 大

? 策略的表示:共n行,每行2n-1列,即看到其 他n-1个人的各种组合时,自己猜什么(用 H/T/P)表示。 ? 比如,N=3的最优策略如下:如果看到一个 H和一个T,则pass,否则猜你没有看到的那 种(看到两个H就猜T,看到两个T就猜H)。 这种策略的获胜概率是3/4

? 分析一下n=3的最优策略。实际上,对于每 个人来说,他猜对猜错的概率是均等的, 最优策略的聪明之处是把每个人猜错的时 候“凑在一起”,而不是每次只有一个人 错(这样很不划算) ? 考虑一个n维超立方体,每条边表示一个人 的一种处境。比如001-011表示第2个人看到 第1个人是H,第3个人是T。

? 如何表示策略?对于每条边u-v,如果决定 不pass,就在u和v中的一个结点放一个蓝色 硬币(代表正确),另一个放红色硬币 (代表错误) ? 我们的任务是:让好结点(有蓝硬币没有 红硬币的结点)尽量多。

? 好结点一定有一个相邻点里有红硬币,所 以坏结点形成一个支配集。另一方面,给 定一个支配集,也有一个策略与之对应: 对于一条边u-v,如果u和v恰好有一个点在 支配集中(不妨设为u),则猜v;其他情 况pass

25. Prisoners, Boxes and Pieces of Paper (UVa11118)
? 监狱里有n个犯人(n是偶数),看守和他们玩 一个游戏:看守拿出n张纸条,分别写上一 个犯人的名字,然后各装到一个全等的盒 子里,放在房间A的桌子上。接下来犯人可 以在房间B里商量对策(此时看守可以把盒 子顺序打乱)。再接下来看守按照某种顺 序把犯人叫到房间A里来。每个犯人可以依 次打开 n/2个盒子(即每次可以先看盒子里 的内容,再决定接下来打开哪个盒子)。

? 对于每个犯人,如果打开的所有盒子里都 没有他自己的名字,则游戏以犯人全体失 败告终,否则这个犯人就进入房间C(与房 间B里的犯人完全隔绝,不能交流),然后 看守再选一个房间B里的犯人带到房间A选 盒子。 ? 输入n(2<=n<=1000),求犯人采用最优策略 时的获胜概率。注意:犯人只能事先商量 对策,一旦看过盒子之后就不能和没看过 盒子的犯人交流了。 ? 例如n=2的最优策略是:犯人1打开盒子1, 犯人打开盒子2,获胜概率为0.5。如果两个 犯人都打开盒子1,则获胜概率为0

? 还记得圈覆盖么? ? 把犯人编号为1~n,盒子任意编号为1~n。 如果盒子a里有犯人b的名字,我们说盒子a 指向盒子b ? 这样,盒子们构成了一个有向图。可以证 明这个图由若干个不相交的有向圈构成

double p = 1; for (int k = N/2+1; k <= N; k++) p -= 1.0 / k; printf("Case #%d: %.8f %.8f\n", cs, p, 1.0/p);

几何题和“假几何题”

26. Directional Resemblance (Aizu 2013)
? 给定3维空间中的n+m条向量,找出两个向 量,夹角最小。2<=n+m<=12*104 ? 如果有多解,输出字典序最小的

? 我们只关心向量的方向而非长度 ? 假设OA和OB都是单位向量,则OAB越大, 线段AB越长… ? 问题转化为三维最近点对

? 输入两条线l1, l2和两个点p1, p2,找一条直线 l,使得p1关于它的对称点在l1上,且p2关于 它的对称点在l2上。换句话说,如果以l为折 纸痕,p1会折到l1上,p2会折到l2上。

27. Huzita Axiom 6 (NEERC 2011, UVa1678)

? 输入保证l1, l2不同,但p1, p2可以相同。p1不 在l1上,p2不在l2上。坐标都不超过10。多 解输出任意解,无解输出四个零。

28. Problem of Apollonius (Hangzhou 2013)
? 给你两个圆(C1,C2)和一个点P,两圆外离, 点也在两圆的外部。求你找一个圆,和给 你的圆相外切,且经过所给的点。问这样 的圆有几个,给出他们的坐标和半径。

29. Easy Geometry (NEERC 2013, UVa1679)
? 输入一个凸n(3<=n<=100,000)边形,在内部 找一个面积最大的,边平行于坐标轴的矩 形,如下图。

? 固定x, w之后,最大面积S(x,w)等于 w*(min{y2(x), y2(x+w)} – max{y1(x), y1(x+w)}) ? 如果只固定w,S(x,w)是x的凸函数,最大值 是w的凸函数

30. Smallest Enclosing Box (Rujia Liu’s Present 4, UVa12308)
? 给定三维空间中的n(n<=10)个点,求一个体 积最小长方体包含所有点。这个长方体的 各个面不一定要平行于坐标平面。只需输 出最小长方体的体积。

? 2维情况:旋转卡壳。原理:

? 定理:一定存在一个最小包围矩形(不管 是面积最小还是周长最小),贴着凸包的 一条边。 ? 是否有这样的结论呢?
? 猜想:一定存在一个最小包围长方体,贴 着凸包的一个面 ? 如果这个结论成立,问题就简单了:把点 旋转以后降维即可

? 可惜,猜想是错的。在正四面体中,最小 包围长方体的每个面都贴住了一条边,但 是没有贴住任何一个面

? O’Rourke的论文《Finding Minimal Enclosing Boxes》告诉我们:可以用三维旋转卡壳解 决这个问题,可惜算法太复杂 ? 还是延续上面的思路:如果能找到最小包 围长方体的一个平面,问题就解决了。 ? 如何找这个平面呢?随机算法!比如,模 拟退火..

神题?

31. Jukebox (IPSC 2012)
? 给你若干首单声道“钢琴曲”(WAV/MP3格 式,或者纯文本格式),听写出旋律。这些 曲子的各个音之间有较为清晰的间隔 ? 只需要写出音名,不需要写是哪个八度 ? Easy: 曲子都是世界名曲 ? Hard: 曲子都是瞎弹的,没有任何美感可言

? 简化版的音频处理问题

? 第一步是把各个音“剪”开,忽略“噪声” 干扰 ? 然后尝试识别各个音

32. Invisible Cats (IPSC 2013)
? 给若干32*32的灰度图片,其中第21张图有 猫咪,且前20张图中恰好有10张有猫咪。 现在已经用相同的方法把这些图片变得面 目全非,请你找出另外10个猫咪。 ? Easy: 每张图片的所有32个列按照相同的方 法随机排列 ? Hard: 每张图片的所有32*32个像素按照相 同的方法随机排列

33. Fishes
? 在一片群岛里有一些鱼。每天,所有鱼在 同一时刻醒来,在水里游动(不一定是匀 速的)大半天以后在同一时刻回到各自的 起点(即醒来时的位置),然后睡着。注 意,每天晚上鱼睡着以后可能会被水流冲 到一个相邻的格子。 ? 群岛用w*h(3<=w,h<=1000)的字符矩阵表 示,’#’表示陆地,’.’表示水。鱼只能在水里 游动,且只能沿着相邻格子中心的连线游 动。输入保证所有水的格子连通

? 鱼的路线很特别:在任意时刻(此时鱼不 一定在一个水格的中心),鱼总是能看见 自己在前一天同一时刻(即恰好24小时之 前)的位置。点A能看见点B的条件是线段 AB不会碰到任何陆地格的内部或者边界。 ? 任务:输入一个地图和若干条鱼的n条路线, 判断最少有几条鱼。每条路线的格式为x, y, d(1<=x<=w,1<=y<=h,1<=d<=10000)。每条鱼 的路线不一定发生在连续若干天内

鱼的路线举例(连续5天)

10 8 2 .......... 1 2 3 .......#.. 4 ........#. .......... ...#...... ......###. ......###. .......... 4 2 7 12 NNNEEESSSWWW 2 8 24 WNNNNNNNEEEEESSSSSSSWWWW 1 8 46 NNNNNNNEEEEESSSSSSSEEEENNNNNNNSSSSSSSWWWWWWWWW 1 8 32 NNNNNNNEEEEEEEEESSSSSSSWWWWWWWWW

? 解决问题的关键:理解什么样的两条路线 可能是同一条鱼?为了方便,我们说这两 条路线是等价的
– 形状位置相同但起点不同的路线是等价的 – 如果路线A可以“连续变形”为路线B,二者也 是等价的。在拓扑学上叫同伦(homotopic)

– 没有岛屿的情况下,所有路线都是等价的,如 果有岛屿的话…绕岛的路线和不绕的路线肯定 不等价

? 绕一遍和绕两遍的肯定也不等价…绕的方向 还有关系(顺时针和逆时针),所以,是 不是可以根据绕岛屿的次数和方向来统计 等价类的个数呢? ? 反例:

? 那怎么办?用收缩橡皮筋的方法…然后每条 路线求环状最小表示即可

34. Morning hassle (IPSC 2013)
? 你的任务是从数轴上的x=0点(家)以最短 时间在x=xend >0点(目标)停车。出发的速 度为0,停车时的速度也必须为0。 ? 数轴上还有n个点要过火车,你的私家车在 通过这些火车点的速度必须是不超过vmax的 整数,而且不能和火车相撞。加速度必须 是-amax~amax的任意实数。整个数轴都可以 开车。车的移动是连续的,速度可以是任 意实数,没有上限。

? 每个火车点的描述方式如下:
– 位置xi, 火车个数mi,然后是2mi个实数,即每个 火车到达时间si,j和离开时间ei,j。0<=si,j<ei,j<=106 – 你可以在区间端点时穿过这个点。

– 同一个火车点的各趟火车区间按照先后顺序给 出,且前一趟火车的离开时间严格小于下一趟 火车的到达时间。

? 限制:
– 0.5<=xend<=1500.0, 0.1<=amax<=10.0 – 1<=vmax<=40 – 0<=n<=30, 0<=mi<=25

? 注意:火车点初的速度v是整数,并且有上 限。这是解决本题的关键! ? 位移公式:s=v0t+at2/2 ? 考虑两种简单情况
– n=0。先用最大加速度到达中点,然后减速。根 据对称性,肯定是在速度减到0的同时到达中点。 – n=1,且这个火车点没有火车。虽然没有火车, 但是速度有要求(上限、整数)的情况。枚举 速度vtarget后需要解决这样一个问题: – 从x=0,v=0最快要多久到达状态x=xcross, v=vtarget。 根据对称性,经过火车点后的减速过程道理是 一样的。

? 最快当然是一直加速了…加速时间 tacc=vtarget/a,这段时间的位移x=1/2a*tacc2
– 最x=xacc:刚好! – 最x>xacc:继续加速,到中点后减速 – 最x<xacc:倒着开xacc-x,然后加速!

? 这样就可以解决Easy了:枚举vtarget,在穿过 火车点之前和之后分别求解,然后合并。 注意,如果穿过火车点的时候有火车经过, 需要在一开始多一段等待时间,而不是在 火车点等待。

? Hard: 整个路径可以分成若干段,每一段要 么正着开,经过下一个火车点,要么倒着 开,从相反方向再次经过刚才经过的火车 点。定义Ti+,v和Ti-,v分别表示位于火车点i的 右侧和左侧(v分别要求大于0和小于0)时 可能的时刻。可以得到这样的递归表达式

? 这个式子很容易考虑火车——只需要去掉有 火车经过的区间即可

? 情况1:先经过火车点i,再经过火车点i+1。 ? 首先解决这样问题:是否可以从速度v加速 到v’>v,使得距离不超过s?速度改变的时 间tchange=(v’-v)/a。s>=schange时答案为“是” ? 此时最短时间等于tchange加上之前那种“先 加速后减速”的策略所需要的时间,即 ? 可是,只算出最短时间是不够的!!! ? 需要算出所有可行的时间集合。在最短时 间基础上,我们可以故意磨蹭一下,即先 减速再加速。如果减速过猛,还可能先停 下来,然后倒着开,再加速!

? 如何把时间拖得最长呢?先以最大加速度 减速,再加速回v,最后加速到v’: ? 这个方程可能有两个正根t1’’<t2’’!所以可能 有三种情况
– 情况1a:s太大,可以刹一点车,也可以刹车到 停下来。解为[tmin,∞) – 情况1b:s太小,只能刹一点车但不能停下来, 所以解为区间[tmin, t1’’+tchange] – 情况1c:s不大不小,解为 [tmin,t1’’+tchange]U[t2’’+tchange, ∞]

? 情况2:连续两次经过同一个火车点。和情 况1的分析方法类似,这里略 ? 主算法:注意到T的递推方程都是单调的, 所以可以迭代法不断更新所有的T,根据 Knaster-Tarski不动点定理,迭代最终会收敛 到正确答案。

35. Matrix Nightmare (IPSC 2012)
? 输入一个整系数多项式p,设计一个n*n矩 阵M,要求: ? M是Z-var矩阵(即元素均为整数或单个变量 的矩阵) ? M的n-step traversal weight等于

? 本题的矩阵行列编号均为0~n-1

? di称为double factorial,定义为d0=1, di=di-1*i!。 比如d3=1!*2!*3!=12。 ? 长度为n,每个元素均为0~n-1的整数的序列称 为limited sequences of order n,比如(0,2,0,1)。 所有这样的序列的集合记为Sn。 ? 序列A=(a0,…,an-1)的spread factor定义为

? 对于A=(a0,…,an-1), B=(b0,…,bn-1),记 PA,B=((a0,b0),(a1,b1),…,(an-1,bn-1))。当所有 (ai,bi)<(ai+1,bi+1)(字典序)时定义ρ(PA,B)=1,否 则为0

? 让我们先来化简那个恐怖的表达式…

? 哪些项不为0呢? ? Spread factor不能为0,意味着A和B不能有 相同元素,因此都必须为0~n-1的排列

? ρ(PA,B)必须等于1(否则就得等于0),因此 A必须为升序排列。另外不难验证

? 总结一下。要计算的表达式实际上可以化 简为:

? 问题转化为了:构造一个z-var矩阵,使得 它的行列式等于给定多项式。行列式的符 号怎么办?加一些行列,主对角线的元素 都设为1,其余元素为0。这样,行列式值 不变,但可以让n是4的倍数

? 还记得圈覆盖么(又来了)?观察行列式 的表达式

? 这里有一个求和符号,然后连乘的那些项 中,每一项都是一个结点i到“i指向的结点 bi”的边的权值。也就是说,那是一个圈覆 盖! ? 符号呢?简单的处理方法是总是让圈的个 数是偶数,具体方法见后。

? 假定自环和虚线的权为1,则下图有3个圈 覆盖:aef, bef, cdef,长度分别是奇数、奇 数、偶数,因此行列式为(-a-b+cd)ef。 ? 注意,这个图很像一个网络,最左边的是 源,最右边的是汇。 ? 为了方便,我们总是让所有源-汇路径的长 度同奇偶

? ? ? ?

递归构造,共三条规则 单字母:只有一条边的图 p*r:构造Gp和Gr后合并Gp的汇和Gr的源 p+r:仍然先构造Gp和Gr,合并Gp和Gr的源, 然后分两种情况讨论:
– 两个图中源-汇路径长度的奇偶性相同,构造一 个点作为新图的汇。两个图的汇到新汇连一条 权值为1的边 – ...奇偶性相反,则Gp的汇连一条权值为1的边到 Gr,Gr的汇是新图的汇

? 递归构造过程结束之后还需要一点调整:
– 非源非汇点均有权值为1的自环 – 如果所有源-汇路径均有奇数个结点,则从汇向 源连一条边,权值为1;否则合并源和汇

其他讨论题

36. Light in a room (IPSC 2012)
? 一个房间的天花板上有一盏灯,求地面和 墙面上照亮部分的总面积。地面和顶面都 是水平的,墙面都是竖直的。灯的轴线是 竖直的。地面是凸n边形(n<=100)。

37. Range flips (PE 430)
? N个白球排成一行。每次可以均匀随机选出 1~N的两个整数A和B(可以相同),然后翻 转A到B之间的所有球(包括A和B)。白色 翻转后变成黑色,黑色变成白色 ? 经过M次操作后,白色球的个数的数学期望 定义为E(N,M)。比如E(3,1)=10/9, E(3,2)=5/3 ? 求E(1010, 4000)

38. 2x2 positive integer matrix (PE 420)
? 每个元素都是正整数的矩阵称为正整数矩 阵。有些正整数矩阵有两个不同的“平方 根”,比如

? ? ? ?

F(n)为满足如下条件的2*2正整数矩阵个数 有两种方法写成两个2*2正整数矩阵的乘积 Trace(即主对角线上的元素和)小于N 比如F(50)=7, F(1000)=1019。求F(107)。

39. Eating pie (PE 394)
? 有一张面积为1的圆饼,先沿着半径切一刀 (叫initial cut),然后重复下面过程:
– 如果还剩下的面积严格小于F,停止,否则

– 在剩下的扇形饼中随机切两刀(也是沿着半 径),按照从initial cut逆时针的顺序吃掉前两 块,剩下第三块

? 对于x>=1,设E(x)为F=1/x时上述过程的重复 次数的期望。比如E(1)=1, E(2)=1.26765… ? 求E(40),保留小数点后10位

40. Evil Matching (IPSC 2012)
? 考虑两个正整数串T,P。如果存在一个序列a ? k = a0 < a1 < ... < am使得:
Ta 0 +Ta 0 +1 +...+Ta1 -1 =P1 Ta1 +Ta1 +1 +...+Ta 2 -1 =P2 ... Ta m?1 +Ta m?1 +1 +...+Ta m -1 =Pm

? 称串P在位置k Evil-matches串T ? 输入三个正整数串T,P1,P2

? 回答下面四个问题:
– P1能在多少个位置Evil-matches T – P2能在多少个位置Evil-matches T – 求最小的正整数n使得P1· n· P2能在最多的位置 Evil-matches T – 求第三问中位置个数的最大值是多少

? 其中‘· ’表示串的连接。 ? Easy: |T|<=5000,|P1|,|P2|<=600,所有输 入数字的和不超过11000 ? Hard:|T|<=11000000,|P1|,|P2|<=2000000, 所有输入数字的和不超过22000000

41. Reciprocal cycles II (PE 417)
? 1/6=0.1(6)的循环节长度为1,1/7=0.(142857) 的循环节长度为6。有限小数的循环节长度 规定为0 ? 一般的,设L(n)为1/n的循环节长度,求 L(3)+L(4)+…+L(108)。

42. Look and say sequence (PE 419)
? 序列1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 ? 可以证明这个序列只包含数字1,2,3 ? 求n=1012时,有多少个数字1,2,3。比如n=40 时有31254, 20259, 11625个1,2,3

43. Subsequence of The Thue-Morse sequence (PE 361)
? Thue-Morse序列Tn定义如下:
– T0=0 – T2n=Tn – T2n+1=1-Tn

? Tn的开头如下: 01101001100101101001011001101001.... ? A是满足如下条件的整数k集合:k的二进制 表示是Tn的连续子串。k=18=10010(2)在A中

? A排序后如下表

? 比如A100=3251, A1000=80852364498 ? 求下式的最后9位数字

44. Pencils of rays (PE 372)
? R(M,N)表示满足M<x<=N, M<y<=N并且[y2/x2] 为奇数的整点(x,y)的个数,比如 R(0,100)=3019 ? 求R(2*106, 109)

45. A Kempner-like series (PE 368)
? 调和级数1+1/2+1/3+1/4+…是发散的
? 可是,如果删除所有分母包含三个连续数 字的项,这个数列就会收敛,比如前1200 项只会删除20项:1/111, 1/222, …, 1/1119。 ? 求这个级数的极限,保留10位小数


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com