Code For C
Code For D
Code For F
HDU - 6482
存在一个 *LGV(Lindström–Gessel–Viennot)*定理
对于一张无权的DAG图,给定N个起点和N个终点
设e(ai,bi)为点i到点j的路径方案数,这N条不相交路径的方案数为
⎝⎜⎜⎜⎛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步的方案数,这样就转化为组合数问题,答案为Ci+ji
HDU - 6483
先用ST表处理出区间的最大最小值
对于每个询问,mx表示该区间最大值,mi表示该区间最小值
然后可以将问题转化为询问区间内不同数的个数是否等于mx−mi+1
后面部分可以用莫队算法解决
HDU - 6485
枚举串s的后缀,拿其与串t尺取
枚举串t的后缀,拿其与串s尺取
所得的长度最大值,就是答案