SRM566

大半夜。。。看完IMBA高手录像。。。头脑昏沉。。。黑灯瞎火做SRM..。

250pt:给定n个点,和连接这些点的边(无重边)。然后要删掉一些边,使剩下的边中任意两条边都有公共顶点。求删掉边的方法数。

思路:分析后可知,满足要求的边组合只有三种情况:

  1. 没有边
  2. 以某一个点为中心发散
  3. 三个点围成三角形

依次求出个数即可。

500pt:当时毫无思路,刚看了些大神的代码,发现原来是DP- -||

题意:0,1,2,…,n-1围成一个环,第0天企鹅待在0,然后的第i天,企鹅可以从当前位置顺时针或逆时针移动i个位置,求第K天移动到0的方法数。K<10^18

思路:由于K非常大,模拟是不可能的。分析之后可以发现,N+i的状态和i是一样的(顺时针或逆时针i个位置),也就是说每N步一个轮回,由此我们可以求出0->n->2n->4n->8n->…..的位置改变过程

0->n的直接模拟得到,2n的可以直接从n得到。。。。

对于K,对K/N进行二进制位的分解,然后得到K/N*N后到达每个位置的方法数

然后再乘以经过K%N步后从K/N*N到达0的方法数即可。

1000Pt:无视了- -||

 

标签:
文章分类 SRM

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>