A.给出n个平面上点，m条带权边，保证是个平面图。然后q组询问，问从起点到终点的最短消耗。
消耗是这样定义的：假设路径经过了e1，e2，……，ek。那么消耗是sigma(f[i]*w[i])
其中f[i]定义为f[0]=1,f[i]=f[i-1]*(c^i-1)%p c=4263 p=1632899
起点和终点保证在某个平面区域内。n,m,q<=10w
题解: 叫你平时不学计算几何，叫你看错题，爆零了吧
B.给出10个矩阵（固定的），然后一个n个数的序列1<=a[i]<=10，要求计算T[a[1]]*T[a[2]]*……。不但如此，还要在某些位置加入100个矩阵。
n<=100w
题解：求出新序列可以用treap或splay（不过你认为100W的splay能过？）。然后直接算矩阵乘法还是不行的，10亿。。。其实是O（n）的
因为初始的10个矩阵是固定的，所以考虑有什么特征。我刚开始以为会是任意两个相乘之后还是10个矩阵中的一个。。。真是太年轻了。。。
下来后听人说那10个矩阵满足交换律
好吧 分成100段然后每段里面用交换律10个分别计算，复杂度应该是100*10*10^3*logn应该可以过。
我是傻逼当然写了30分的暴力
C.给出n个平面上的点，m次询问，令每次询问的[l[i],r[i]]的最小圆覆盖的半径的整数部分为r[i],每次要求你输出下面的行列式的值:
r1^0 r1^1 r1^2……r1^i-1
r2^0 r2^1 r2^2……r2^i-1
………………………………
ri^0 ri^1 ri^2……ri^i-1
题解: 叫你平时不学计算几何，叫你不好好学数学，滚粗了吧
人太弱感觉真是没法活了
评论 (0)
