/ BZOJ

NOI题目做题记录

NOI 2012

random

BZOJ2875
题目大意
随机数生成器会生成一个数列:x_ {n+1}=(ax_ n+c)\bmod m,给定a,c,m,x0,ga,c,m,x_ 0,g,求x_ n\bmod g的值。所有数字1018\leq 10^18

算法讨论
回忆起之前学习DirectX的时候,为了区分点和向量,给它们加了一维,如果那一维是11表示点,是00则表示向量。这么做是因为在用矩阵进行线性变换的时候,点可以被平移,即某个坐标加上一个常数;而向量不能。这个做法让我困扰了很久,但最后终于明白了。

对于这道题,构造转移矩阵:

[xn+11]=[ac01][xn1]\left[\begin{matrix}x_ {n+1}\\1\end{matrix}\right]=\left[\begin{matrix}a&c\\0&1\end{matrix}\right]\left[\begin{matrix}x_ n\\1\end{matrix}\right]

矩阵快速幂+快速乘即可。

bicycling

BZOJ2876
题目大意
nn段路,nn个变量viv_ i,限制能量i=1nkisi(vivi)2EU\sum_ {i=1}^nk_ is_ i(v_ i-v_ i')^2\leq E_ U,求最短走完这些路的时间,即mini=1nsivi\min\sum_ {i=1}^n\frac{s_ i}{v_ i}n10000n\leq 10000

算法讨论
预备知识:拉格朗日乘数法。为了做这题,我就学习了一下这种黑科技。

预备知识的预备知识:偏微分、梯度向量、等高线。快速学习笔记:

  • 偏微分是在一个多变量函数f(v1,v2,...,vn)f(v_ 1,v_ 2,...,v_ n)中把其它变量当成常数的时候的导数,这个和我之前的理解是一致的。几何意义:其它变量固定时的fvif-v_ i图像,或者说是切片的投影,在vi0v_ {i_ 0}这一点的切线斜率。
  • 某点的梯度向量就是某点的各变量偏微分组成的向量。记为f\nabla f。注意梯度向量不包含函数值这一维!所以如果ff是一个二维函数,那么梯度向量始终是平的。
  • 等高线就是方程f(v1,v2,...,vn)=cf(v_ 1,v_ 2,...,v_ n)=c的解的图像。

拉格朗日乘数法解决的问题是,有一个限制条件g(v1,v2,...,vn)=cg(v_ 1,v_ 2,...,v_ n)=c,求f(v1,v2,...,vn)f(v_ 1,v_ 2,...,v_ n)的极值。

在普通的平面直角坐标系里面,我们求极值的方法很多,其中一种便是求切线。切线有很好的性质,经常意味着极值,所以在这个问题上,拉格朗日给出的方法也是求切线。

为了帮助理解,我们可以认为ffgg都是二变量的,画出图像来在空间直角坐标系中是两个曲面。在第一个限制条件下,可行域变成了曲线,即gg的一条等高线。我们尝试枚举ff值,得到ff的一条等高线;如果ff的这条等高线与g(v1,v2,...,vn)g(v_ 1,v_ 2,...,v_ n)这条线从上往下看(在xyxy平面上的投影)是相切的,那么ff取了一个极值。如果不相切,我们尝试改变ff的取值,来动态地改变f=cf=c的这条曲线,使得它与gg那条相切。

f与g
(图片来自维基百科)

这个极值也不知道是极小还是极大,反正是就对了。

因为梯度向量与等高线垂直,所以切点上ffgg的梯度向量是平行的。设该点f=λg\nabla f=\lambda\nabla g,这里面有nn个方程,再加上一个方程g(v1,v2,...,vn)=cg(v_ 1,v_ 2,...,v_ n)=cn+1n+1个方程n+1n+1个变量,能解切点了,那么极值也就出来了。

回归到bicycling这题上来。为了让时间最短,最好是能够用完能量EUE_ U,所以可以把不等式变成等式。求一下偏导就有方程组

{2λki(vivi)=1vi2(i=1,2,...,n)i=1nkisi(vivi)2=EU\left\{\begin{matrix} 2\lambda k_ i(v_ i-v_ i')&=&-\frac{1}{v_ i^2}&(i=1,2,...,n)\\ \sum_ {i=1}^nk_ is_ i(v_ i-v_ i')^2&=&E_ U \end{matrix}\right.

从题目出发,显然vi0v_ i\geq 0,等式1的右边是在二四象限的两条曲线,左边是一个经过点(vi,0)(v_ i',0)的直线,如果要在大于0的地方有交点,那么λ<0\lambda<0。观察图像,viv_ i是随着lambdalambda递增的。显然还有viviv_ i\geq v_ i',所以i=1nkisi(vivi)2\sum_ {i=1}^nk_ is_ i(v_ i-v_ i')^2是随着viv_ i递增的。

有了单调性关系,我们可以二分λ\lambda,再套一层二分求viv_ i的一元三次方程,最后把viv_ i带入i=1nsivi\sum_ {i=1}^n\frac{s_ i}{v_ i}

NOI 2014

这场在深外考……

zoo

BZOJ3670
UOJ5

题目大意
求变种KMP的next数组,要求这个next的大小不超过这个前缀的一半。

算法讨论
还是搞出正常的next数组,求新的next的时候只要长度太大就像失配一样跳回去就好了。

random

BZOJ3671
UOJ6

题目大意
太长了还是自己去看吧。

算法讨论
前面的随机过程暴力模拟就可以了,毫无意义。

后面的路径的选择只要从11开始枚举贪心地选择就可以了。