章4.2 上下文无关文法

\(\to\)和\(\Rightarrow\)的区别:

\( A \to \alpha\)是一个产生式,\(A\Rightarrow\alpha\)是一个替换。一个替换当中的A可以是一个文法符号串,不同于产生式头(产生式头只能是非终结符号。)

例如,应用\(C \to C*\textbf{number}\)的一个替换可以是\(\textbf{number} + C \Rightarrow \textbf{number} + C*\textbf{number}\)

 

最左推导和最右推导可以有多个吗?(定义P127)

4.2 求解线性递推关系

4.2.2 常系数线性齐次递推关系

$$a_n = c_1a_{n-1} + c_2a_{n-2} + … + c_ka_{n-k} \qquad \qquad (1)$$

这是个常系数线性齐次递推式。构造它的特征方程\(\lambda^k – c_1\lambda^{k-1} – c_2\lambda^{k-2} – … – c_k = 0\),求出这个方程的所有特征根\(\lambda_1, \lambda_2, …, \lambda_m\),称为特征值。令\(\lambda_i\)的重数是\(d_i\),那么递推关系的通解是

$$a_n = \sum_{i=1}^m {\alpha_i(\sum_{j=0}^{d_i} {n^j\lambda_i})}\qquad\qquad (2)$$

这个通解的形式和n阶齐次常系数微分方程的通解结构类似。

任务:证明(2)是(1)的解,且(1)的解必定能用(2)表示(即,证明充要关系)。

 

4.2.3 常系数线性非齐次递推关系

$$a_n = c_1a_{n-1} + c_2a_{n-2} + … + c_ka_{n-k} + F(n) \qquad \qquad (3)$$

如同n阶非齐次常系数微分方程,是齐次通解+1个特解的形式。

特解的构造:如果\(F(n) = (b_tn^t + b_{t-1}n^{t-1} + … + b_1n + b_0)s^n\),那么特解的形式是

$$a_n^{(p)} = n^d(p_tn^t + p_{t-1}n^{t-1} + … + p_1n + p_0)s^n \qquad \qquad (4)$$

这其中,d是s作为(3)相伴的线性齐次递推关系的特征方程根的重数(如果不是根,为0)。这如同n阶非齐次常系数微分方程的解法。

任务:证明(4)是(3)的一个特解,且(3)的解必定能用(4)+(2)表示(即,证明充要关系)。

 

 

4.3 分治法

P161 E4.\(O(n^{1.585})\)的快速乘

令二进制数\(a = \overline{A_1A_0},\ b = \overline{B_1B_0}\),即把2n位的a和b分割成位数尽可能相等的两个n位二进制数。那么

$$a = 2^nA_1 + A_0\ , \  b = 2^nB_1 + B_0 \qquad \qquad (5)$$

计算三个中间变量\(F_1 = A_1B_1, \ F_2 = (A_1-A_0)(B_0-B_1)\ , \ F_3 = A_0B_0\),有

$$ab = F_1 << (2n) + F_1 << n + F_2 << n + F_3 << n + F_3 \qquad \qquad (6)$$

把\(F_i\)的定义代入(6)会发现和(5)中的a和b相乘得到的表达式一致。

计算\(F_i\)的复杂度、加减位运算的复杂度都是\(O(n)\)。

设两个n位二进制数快速乘的复杂度是\(f(n)\),那么

$$f(2n) = 3f(n) + O(n)$$

根据主方法得到\( f(n) = O(n^{log_23})\),约等于\(O(n^{1.585})\),低于一般暴力做法的\(O(n^2)\)。

P162-163 主定理及其证明
P163 E12 \(O(nlogn)\)的最小距离点对算法

画一条垂直x轴的直线l使左右两边各有n/2个点。令\(d_L\)是左边n/2个点的最小距离,\(d_R\)是右边的最小距离,\(d = min(d_L,d_R)\)。

如果最小点对的两个点一个在左边,一个在右边,那么这两个点距离直线l一定不超过d,而且它们的y坐标相差也不超过d。

把所有距离直线l不超过d的点列出来,形成一个集合S。

核心:对每一个在S里面的点P,最多只有7个其他也在S里的点满足与它的y坐标相差不超过d。这一点的证明见P165 图4-6:两个在同一个d/2 * d/2正方形的点之间的距离一定小于d,这就违背了两个同侧点距离一定大于等于d的事实(d的定义。),所以8个格子每个最多只有一个点,其中一个是P。所以得证。

用一个队列可以让找到所有满足【都在S中且y坐标相差不超过d】的点对这一过程的时间复杂度降到\(O(n)\)。(每个点只需要考虑y坐标比它小的。)

设复杂度是\(f(n)\),那么

$$f(n) = 2f(n/2) + O(n)$$

根据主定理\(f(n) = O(nlogn)\)

 

题意:

Ivan有\(n\)个箱子和\(n\)种颜色的球,每种颜色的球有\(a_i\)个。现在所有的球都被放在1号箱子里,Ivan要经过一定的操作,使得每个箱子里恰好只有一种颜色的球。

Ivan可以进行的操作是,拿出某个箱子i里所有的球,将这些球分成均不为空的k份放到k个空箱子里(可以选择刚被清空的箱子i),k可以是2或3。这样一次操作的代价是拿出的球数。现在要求最小的总代价。

分析:

可以知道最后一步操作之前的状态一定是{k-1个空箱,1个箱子里装有k种球,n-k个箱子已经各装了一种颜色的球}。另外,最优的情况下同样一种颜色的球一定不会分散,否则会带来额外的代价。那么可以将同种颜色的\(a_i\)种球打包来看待。再有就是,k=2只有在只剩两种颜色的球需要拆分时才会出现。

但是,分球的策略不是很明确。简单思考到的两种策略都有相应的反例:

1. 每次拿出数目最多的两种球

反例:

6

1 1 1 1 1 1

(ans = 6)

2. 每次把当前的u种球分成尽可能含相同种类数的三堆

反例:

6

1 1 1 1 1000000 1000000

(ans = 2000006)

……

看了一下CF的题解之后才发现【还有这种操作】。

倒着看,从n个箱子里各有一堆球的状态开始,“每次将一堆球拆分成三堆”就成了“每次将三堆球合并成一堆”。这样每次取数目最少的三堆球合并直到剩下一堆,贪心地做就可以得到正解。

因为倒着做时每次操作减少2堆,如果n是偶数的话,需要加一个空堆(含0个球)。

据题解说,这样做正确的原因是Hoffman编码(有理有据令人信服

题解

 

代码:

 

上下界网络流的裸题。适当的建图之后,直接跑一边带上下界的费用流即可。但是要注意先判定是否存在可行流:不存在可行流=无解。

建图:

一个源点S,一个汇点T,n个点R1..Rn代表n行,同样n个点C1..Cn代表n列。
令RB[i]和CB[i]为第i行/列上黑子的个数,那么:

1、建边(S->Ri,RB[i],RB[i],0)、(S->Ci,CB[i],CB[i],0)

对每一对相关联且不同色的单元格(x1,y1)和(x2,y2),不妨设(x1,y1)上放置的是黑子,那么:

2、如果两个格子同列,那么建边(R(y1)->R(y2),0,1,1)。同行的话类似操作。

对每一行、列:

3、建边(Ri->T,Rl[i],Rh[i],0)或(Ci->T,Cl[i],Ch[i],0)

然后再按上下界费用流的求法求出最小费用,就是答案。


补这题时专门学了一下上下界网络流的解法。对无源汇的上下界网络流,建立附加源SS和附加汇TT对于每一条边(u,v,flowLow,flowHigh,cost)(u->v,流量下限flowLow,流量上限flowHigh,费用cost),我们把它拆成三条边(SS->v,流量上限flowLow,费用cost),(u->TT,流量上限flowLow,费用cost),还有(u->v,流量上限flowHigh-flowLow,费用cost).
对于这样构造出的新图跑一遍最大流/最小费用流,如果SS的所有出边/TT的所有入边都取到满流,那么这个新图对应原图的一个可行流,原图中每一条u->v的流量是新图中对应u->v流量+flowLow。与之相对的,如果与附加源、汇相连的边并没有全部取到满流,那么不存在可行流。这个结论的证明参考的是这里
对于有源汇的上下界网络流,只要加一条边(T->S,0,INF,0)就可以转化成无源汇的上下界网络流来求解。

 

A题 Too Rich 贪心+trick

一个需要一点点思考的贪心。思路是队友YZF大佬提供的,我只是代码的搬运工

然而还是调了三个小时
A题

 

F题 Almost Sorted Array 签到题 01:45(-6)

emmm….这可能是最难过的一道签到题….6发WA还行。

一开始是采用的“删去第一个不满足不降关系的点”的做法,但是由于不能确定要删去第一个不降关系中的前者还是后者,所以相对较繁。并且也没调出来

用了队友KK大佬的思路之后,1发AC。kkkkk太强辣!

G题 Dancing Stars on Me 结论题 02:17(-5)

结论:格点正多边形只有正四边形。

然后排除n != 4的情况,就好做了。

 

H题 Partial Tree ?? 02:53

队友做的。

J题 Chip Factory Trie树 00:54

队友做的,待补。

L题 House Building 签到题 01:03(-2)

对每一块孤立的高为\(h(i,j)\)的建筑物,其初始表面积为\(4h(i,j)+1\).
和上方建筑物重叠而损失的表面积为\(2*\min \left\{h(i,j),h(i-1,j) \right\}\)
和左方建筑物重叠而损失的表面积为\(2*\min \left\{h(i,j),h(i,j-1) \right\}\)
如果\(h(i,j)=0\),那么表面积\(S=0\)(特判)

如此可解。

历时三小时有余,反复WA了20+次的题。现在我到底是以怎样的心情写下这篇日志的呢?

题意:

  • 你手上有面值1,5,10,20,50,100,200,500,1000,2000元的硬币/纸币各若干,现在要用这些钱凑出恰好p元。并且,由于你实在太过土豪,钱乃身外之物,你希望花掉的货币的张数越多越好。如果能够凑出p元,输出最多能够花掉的货币张数,反之输出-1.

思路:

  • 这个思路的大致结构是由队友YZF大佬提出的。在训练的5个小时里我们一直在试着完善它,可惜一直未能成功。
  • 要求花掉货币张数最多 的做法不是很容易看出来,但是它的反面,即求 剩余货币张数最少相对容易一些,直接贪心就好。
  • 除了20->50,以及200->500,其它的小货币的面值都是更大面值货币的约数,也即,1张大面值货币一定能够被数张小面值货币表示(除了那两种特殊情况),因此要求花掉货币张数最少时,就要尽量选用大面值货币。
  • 20->50和200->500的处理办法是,把两张50/500当做一张100/1000花。如果有需要使用单张50/500的情况,特判即可:令剩余货币数量为rem,那么我们要求的答案就是

\(\min \left\{calc(rem), calc(rem-50), calc(rem-500), calc(rem-550) \right\}\)
当然,后三项需要满足对应的条件才能出现。

  • 而能够使用单张50/500的情况,是 有至少1张50/500 而不是 有奇数张50/500,这个误区也是我们在训练中陷入江局的原因。这是因为:

  • 4张50,p=50, rem=150. 要凑出150,只能是使用3张50,也即需要使用单张的50。但是,此处50元有4张,是偶数。

  • 算出这个最少张数之后,用总货币张数去减,就得到了答案。

  • 无解的情况,是 (1)货币总面值小于p (2)凑不出rem元。

代码: