常规中的OI - 可以用信息方法解决的四道常规题

很久没发博了,AFO了也没什么好写的,都要忘记怎么搭博客了..
于在博客从gitcafe转到coding之际收集了些常规题,都4可以用OI姿势解哒.
都是水题裸题了..给大家娱乐娱乐 。

(这里卖个萌x) 拿我大酷玩阵帖。
这里写图片描述

P.S. [Explanation]是给没有信息基础的人看的,[Solution]是给OIer看的(然而OIer们都没必要看题解啊x)

食物链条数

[Description]

给出一个食物网的示意图,求其中食物链的条数(以生产者为起点,最高级消费者为终点)。

[Solution]

拓扑+DP
(计数菌: 图论 *1)

[Explanation]

这个题是有普适的解法的,然而生物老师并没有讲..他靠的好像是直觉..
那我们来举一个比较复杂栗子好了,做个动图来解释了——
这里写图片描述
有了这个方法是不是就很稳了呢!

[Expansion]

同样可以用DP解决一系列问题例如“位于多个营养级的生物有哪些”(可以自己想一想)。

有机物主链

[Description]

给出一个有机物(烃)的碳架,求最长碳链。

[Solution]

裸 · 树的直径
(计数菌: 图论 *2)

[Explanation]

注意到题意是要求找出最长碳链,而不是最长且支链最少最简单的碳链(这需要更复杂的方法),所以下面只给出找出一条最长链的方法。
直接给方法吧,原理可以自己思考。
操作:随便找一个结点(碳原子),记为A。从A向旁边扩展,找到离A最远的一个结点B(若有多个随便选一个),再由B向旁边扩展,找到离B最远的一个结点C。于是,BC间的唯一路径(想一想为什么是唯一)就是这个有机物的一条最长链了!
还是给个栗子吧er..
(我作图好渣的)
这里写图片描述
这个方法对于印在试卷上的一些复杂小分子有机物这个方法还是精准又快速的。

一道数学周考题

(突然发现常规题都没有取名字..)

[Description]

如图有一个正四面体,四个顶点分别为ABCD。现有一只蚂蚁位于A,每步蚂蚁可以从某个顶点移动到其他任意三个顶点,概率都为1/3,问7步后蚂蚁位于A的概率是多少?
这里写图片描述

[Solution]

入门DP..我在考场上竟然还手写了二维..变成一维还是很简单的..
设$f(n)$表示第i步在A的概率,转移方程为$f(n)=\frac{1-f(n-1)}{3} $
应该很好理解的

[Explanation]

推导参见上面[Solution].
然后!我们来体现一下常规相较信息的优越性了!
对于$a_n$的递推式,经过数学推导可以得出通项公式$a_n=\frac{3}{4}[(-3)^{-n}+\frac{1}{3}]$,可以直接得出$a_7=\frac{182}{729}$,即为答案了。
(常规的优越性在于,如果这是道信息题,我自己根本就不会去想着推通项公式啊——然而Picks表示不服)

[Expansion]

强行推广到如下题:
有一个正n面体,n个顶点分别为A1/A2/../An。现有一只蚂蚁位于A1,每次移动可以从某个顶点移动到其他任意n-1个顶点,其中由Ai移动到Aj的慨率为f(i,j),问第k步后蚂蚁位于At的概率是多少?(n,f,k均为变量)
于是为了凑字数,我们把它强行变成一道入门二维DP辣(然并卵——),而且还不能推导通项公式了..

一道数学作业题

[Description]

已知数列${a_n}$满足:$a_1∈N+$,$a_1≤36$,且

$$
a_{n+1}=
\begin{cases}
2a_n, & a≤18 \\
2a_n-36, &a_n>18\\
\end{cases}
$$

(n=1,2..).记集合$M={a_n|n∈N+}$。求集合$M$的元素个数的最大值。

[Solution]

Tarjan缩点+拓扑+DP
(计数菌: 图论 *3)

[Explanation]

这个解释起来有点困难啊..
我们可以把1-36每个数字看作一个结点,若存在对于每一个$a_{n+1}=f(a_n)$($f$为题干中给出的那个函数),则从an向an-1连一条有向边(可以简单理解为箭头)。
按照上述规则作出图:
这里写图片描述
我们发现,在一条单向链上的结点可以在一个集合内,所以找出最长的一条链就可以了(可包含环)。
但是这里和有机物那道题有点不一样,因为这里的边是单向边,所以不能用那个方法来做。
那怎么办呢?观察这个图,发现另外一条性质:即每个结点有且一条出边(从这个结点出去的边),这就导致了,任意一个环上都不会有出边(想一想为什么),于是问题简化成:找到最长的一条链或最长的一个环或最长的一条连着链的环(好绕)。
为了更清晰的看这张图,我们把每个环缩成一个点,并把结点的权值改成所代表的结点数。
这里写图片描述
现在问题就变成了找到权值最大的一条单向链了,答案就是它的权值。
很容易得到answer=1+1+6=8了。

[Expansion]

放上[BZOJ 1529] POI2005 ska Piggy banks:
n个存钱罐,只能用钥匙打开或砸开。每个存钱罐有一把钥匙,放在任意一个存钱罐中,问最少要砸开多少个存钱罐才能打开所有存钱罐。(给出每个存钱罐的钥匙放在哪个存钱罐里)

[Summary]

总结一下。
发现OI思想真的是有用又普适又简洁又粗暴又优美的,尤其是图论应用得也很广,自己受OI洗脑后感觉想问题的方式也跟以前也不一样了。
这里只是列举几个浅显的例子说明我这个观点..
其实是想最后顺便向大家安利OI辣~

最最后:安利一首贾老板的新歌[CAN’T STOP THE FEELING!] ,本周空降第一噢!