3
21
2015
0

20150322省选模拟测试#1

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 

题解: 叫你平时不学计算几何,叫你不好好学数学,滚粗了吧

人太弱感觉真是没法活了

Category: 模拟赛 | Tags: | Read Count: 262

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com