Code For C
Code For D
Code For F
HDU - 6482
存在一个 *LGV(Lindström–Gessel–Viennot)*定理
对于一张无权的DAG图,给定NNN个起点和NNN个终点
设e(ai,bi)e(a_i,b_i)e(ai,bi)为点iii到点jjj的路径方案数,这NNN条不相交路径的方案数为
(e(a1,b1)e(a1,b2)⋯e(a1,bn)e(a2,b1)e(a2,b2)⋯e(a2,bn)⋮⋮⋱⋮e(an,b1)e(an,b2)⋯e(an,bn))\begin{pmatrix}
e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n) \\
e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n) \\
\vdots & \vdots & \ddots & \vdots \\
e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n)
\end{pmatrix}⎝⎜⎜⎜⎛e(a1,b1)e(a2,b1)⋮e(an,b1)e(a1,b2)e(a2,b2)⋮e(an,b2)⋯⋯⋱⋯e(a1,bn)e(a2,bn)⋮e(an,bn)⎠⎟⎟⎟⎞
这里我们有两个起点两个终点,代进去就就可以求出不相交的方案数了,然后用总路径数减去就好
至于如何求到点(i,j)(i,j)(i,j)的方案数,这里可以理解为,你需要走(i+j)(i+j)(i+j)步,在这(i+j)(i+j)(i+j)步中在何时往下走iii步的方案数,这样就转化为组合数问题,答案为Ci+jiC_{i+j}^iCi+ji
HDU - 6483
先用ST表处理出区间的最大最小值
对于每个询问,mxmxmx表示该区间最大值,mimimi表示该区间最小值
然后可以将问题转化为询问区间内不同数的个数是否等于mx−mi+1mx - mi +1mx−mi+1
后面部分可以用莫队算法解决
HDU - 6485
枚举串sss的后缀,拿其与串ttt尺取
枚举串ttt的后缀,拿其与串sss尺取
所得的长度最大值,就是答案
Read More ~
标签:#
莫队