A,B,C 都是语法题,跳了。
D 就是考虑两个数都不超过 \(10^6\) ,所以就枚举一个,二分另外一个。
前四题都水就没写。
E
我不会下国际象棋。
象只能斜着走,可以走任意长的距离,问最少能走到目标位置的步数。
01 BFS 。
我们记录上一次走过来的方向,如果相同就说明这一次可以和上一次算作一步,这次走的距离就算作 \(0\) ,不同就说明需要不能和上一步合并,所以距离算作 \(1\)。然后就转化成了 01 BFS
F
容斥原理。
就相当于我们要求所有字母可能出现的情况的并集。考虑字母只来自一个字符串,这些字符串构成的不同种情况中可能有交集,所以要减掉交集,然后就转化成了容斥原理的模型。
G
这是一道模拟赛题。
我找找我当时写没写小记
Ex
我之前听说外国人不会科技
首先考虑不带修的方案数。
设 \(f_{i,0/1}\) 表示到第 \(i\) 个位置,以 \(0/1\) 结尾的方案数。
然后如果当前位置是 \(0\) 的话,\(f_{i,1}=f_{i-1,1},f_{i,0}=f_{i-1,0}+f_{i-1,1}+1\)。
如果当前位置是 \(1\) 的话,\(f_{i,1}=f_{i-1,1}+f_{i-1,0}+1,f_{i,0}=f_{i-1,0}\)。
问号就各把他们当作 \(0\) 或 \(1\) 重算一次。
如果当前位置和 \(j\) 相同的话考虑把他们接到上一段或者另起一段。不会算重是因为我们的策略是所有前面开头后面都会接上。
把式子合并起来长这样 \(f_{i,0}=f_{i-1,0}+[a_i \not =1] (f_{i-1,1}+1),f_{i,1}=f_{i-1,1}+[a_i \not = 0](f_{i-1,0+1})\)。
考虑如何让他带修。
DDP!
我们构造一个转移矩阵。
就是让 \(\begin{pmatrix}f_{i-1,0}\\f_{i-1,1}\end{pmatrix}\) 乘上一个矩阵后变成 \(\begin{pmatrix}f_{i,0}\\f_{i,1}\end{pmatrix}\)。
因为式子种有加一的项,所以两行可能不够用,所以我们加一行为 \(1\) 的行。
于是我们可以构造出 \(\begin{pmatrix}f_{i-1,0}\\f_{i-1,1}\\1\end{pmatrix}\times\begin{pmatrix}1&(a_i\not =1)&(a_i\not =1)\\(a_i\not = 0)&1&(a_i\not = 0)\\0&0&1\end{pmatrix}=\begin{pmatrix}f_{i,0}\\f_{i,1}\\f_{1}\end{pmatrix}\)
我他喵的发现这里写反了,结果矩乘的规则让我直接改了,变成前面的每一列成后面的每一行了(((
额他不影响,就知道是这样构造的就行。
然后把转移矩阵架到线段树上就能快速修改和转移了。
标签:begin,end,位置,矩阵,pmatrix,ABC246,考虑 From: https://www.cnblogs.com/cc0000/p/16815258.html