NOIP2014酱油记 && 简要题解

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。。。