注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

NOIP2014酱油记 && 简要题解  

2014-11-10 14:05:00|  分类: noip,oi |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

10.7:从偏远小渔村坐动车去广州,速度还是一如即往的快,在车上和神犇们差不多补了三个小时空境就到了,想想几年前要整整一个白天大巴啊!!到了之后,其他人一群没事去找网吧,然后全部年龄不足失望而归2333。。。本蒟蒻没事和其他一两人补了一个下午月刊少女,晚上补恋物语--西尾二人转+一本正经的胡说八道QAQ。。。一日无视

10.8:NOIP day1。。。看了题目之后感觉姿势不太对啊。。。怎么我这种两个月都没碰代码的都会?一个小时残了一下前两道题,T3蒙了个70%的暴力了事(懒得想。。。),出来之后才发现自己傻爆了。。。T3不就一傻叉DP优化么。。。

下午雅姐来了,然后几只人一起滚去动漫城转了一圈,一个手贱就花了好多软妹币啊!!!剁手剁手!!!

10.9:NOIP day2。。。题目还是不对啊~!!!!说好了今年的NOI试题和NOIP搞混了呢!!!T1的数据范围简直笑抽。。。还是一个小时蒙掉前两题+T3暴力,然后继续补觉(昨晚追fate和SAO玩到2点多伤不起!)下午坐车滚粗回家。。。于是人生最后一次OI比赛就这么酱油掉了。。。(TAT。。。)


NOIP2014 简要题解:

day1:

T1:暴力枚举。。。。

T2:对于一个节点,找祖父,找兄弟,找孙子,然后dfs一遍统计即可。。。。

T3:dp暴力,然后我们看看这个DP方程f( i , j ) = min{ f( i - 1 , k ) + ( j - k ) / X( i - 1 ) } ,DP过程中令k0为最优决策,k1为其他决策。。。有:

f( i - 1 , k0 ) + ( j - k0 ) / X( i - 1 ) < f( i - 1 , k1 ) + ( j - k1 ) / X( i - 1 )

化成:f( i - 1 , k0 ) - k0 / X( i - 1 ) < f( i - 1 , k1 ) - k1 / X( i - 1 )

那么只要把(j-1)mod X[i-1]相同的分为一组DP,DP过程中维护个min{ f( i - 1 , k ) - k / X( i - 1 ) }就可以做到整体O(nm)了,应该就可以AC。


day2:

T1:暴力。。。。

T2:反向建图,bfs一遍,正向建图,再bfs一遍。。。。

T3:首先f( x ) = 0 的话 任意p有 f( x ) = 0 ( mod p )

那么暴力模拟可以70%。。。

接下来本蒟蒻一直想不出,知道在贴吧上看到某神犇这么一句话:f( x + p ) = f( x ) ( mod p )。。。然后就傻掉了,首先证明这个式子f( x + p ) = a0 ( x + p )^0 + a1 ( x + p )^1 + ... + an ( x + p )^n = a0 x ^0 + a1 x^1 + ... + an x^n + K p = a0 ( x + p )^0 + a1 ( x + p )^1 + ... + an ( x + p )^n = a0 x ^0 + a1 x^1 + ... + an x^n = f( x ) ( mod p )

那么其实只需要枚举1...p的数字 不需要1...m 所以复杂度降成了O(kpn)(k表示你选取的p的个数),应该可以AC。。。



  评论这张
 
阅读(385)| 评论(23)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018