Home > Old Blog Posts > NOIP2009初赛问题求解题解

NOIP2009初赛问题求解题解


痛定思痛……

第一题,求拓扑排序的个数,先把图转成类似树的形式,自底至上计算:

6:1种

4、7、6:2种,分别为476和746

3、4、7、6:2种

2、3、4、7、6:2种

1、2、3、4、5、6、7:1肯定是排在最前面的,5可以排在1后面任何一个位置,共有6个空,所以这时的方法数是2*6=12种

1、2、3、4、5、6、7、8、9:8和9本身是有序的,插到1~7时,有2种情况:8和9在一起,则共有C(8,1)=8种,8和9隔开,则共有C(8,2)=28种,根据加法原理和乘法原理,最终答案为12*(8+28)=432种

第二题,先将10015转换为7进制得到(10015)10=(41125)7,但可以先付41130,再找回2张,这样总共需要35张

第一题写了336,第二题写了33的,悲剧路过

NOIP出题人,我和你隔的不过是一朵菊花而已

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: