0912NOI模拟

· · 个人记录

比NOI简单多了，只有一道不可做题

杀毒软件

字符串匹配，考虑AC自动机。区间跑AC自动机上的dp，而且AC自动机上的点还很少，考虑矩阵乘法优化。然后用线段树维护下动态dp就行了

结果矩阵卡常的部分写错了挂成40.。。早知道不卡这破常数了

[code](http://oi.nks.edu.cn/zh/Submission/Details?cid=991&id=388655) ## [政治正确](http://oi.nks.edu.cn/zh/Problem/Details?cid=991&tid=L) 不会做，好恶心，题面就看不懂。。。 放下官方题解，等我懂了再补code >NOI2010出现了一道穷凶极恶的题，叫成长快乐。 这道题类似于成长快乐，但是更简单一点。该题使用模拟退火或者爬山等算法是可以得到很高的分数的，同时只需要一点小小的手段就可以轻松得到满分。 > >我们需要最小化一个长相奇怪的函数。搞清楚这个函数究竟在描述什么也许要点时间，如果没有因为题面太恶心而放弃的话，我们不难发现，这个函数可以看成 维空间中有 个点和一个球壳，我们要在球壳内部找到一个点，使得所有点和球壳给这个点施加的影响总和最小。 > >实际上这个总影响一定可以最小化为0的。下面将证明这一点。所有点和球壳给空间中任意一点的影响可以看成是力，因为公式中对于每个政治问题的影响可以看成是力正交分解后在每个正交基上的分量。同时，这样的力一定是保守力，即选择相同的起点和重点，无论通过什么路线移动这个点，该点受外力做功相同，因此整个立场是保守力场。所以我们可以想象出这个空间中的势能的分布。并且我们知道，靠近球壳的地方势能区域正无穷，政客代表的点势能也趋近正无穷。所以假设你在球壳内随便放入一个小球，小球会沿着势能下降最快的方向加速。最终，由于阻力的作用，小球会停在某个势能的极小值处，而这个地方的受力一定为0，可以想象出，球壳内至少存在一个这样的点。 > >小球的滚动可以当做就是爬山算法的过程，因此，我们在爬山时不需要再枚举怎样更改政治主张，而是直接沿着受影响的反方向成比例改变政治主张，这个方向一定是最优的，沿着这个方向走，最终我们将会达到受影响为0的点。 ## [水果拼盘](http://oi.nks.edu.cn/zh/Problem/Details?cid=991&tid=M) 出题人整的什么烂活 题解里写的什么斯特林啊什么的，结果随便做下就水过去了 直接期望线性性求一下每个水果出现次数用组合数算下概率，乘起来累个和就行了 [code](http://oi.nks.edu.cn/zh/Submission/Details?cid=991&id=388651)