题目链接

题意：

给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。

思路：

很容易想到矩阵，但是i^4不是线性的差评，我们可以拆一下

i^4=(i-1+1)^4,然后二项式展开即可

起因是队里的大佬们都会这东西，而我一个老年选手竟然还不会，实在说不过去。

cdq分治显然是分治的一种，cdq的意思就是超短裙啦（

这东西网上资料很多（然而还是学不会

Description

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

题目链接

Description

Input

Output

样例太长了，就不写了。

题意是说，现在有n个在二维平面，m个操作，2种类型，一种是加入一个点，另一种是对于一个定点，询问距离其最近的点的距离。

hdu1724题目链接

题意：

求图示区域的面积。

思路：

辛普森积分学习笔记

容易推出被积函数为  f(x)=b_sqrt(1-(x_x/a/a));

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年10月09日 星期一 21时09分36秒
 4File Name :1724.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include …

16沈阳的阴影还在orz，来学习一下辛普森积分。

参考资料：梯形多步法和辛普森积分

辛普森计算定积分

辛普森积分是一种数值积分方法（然后现在只记得教计算方法的是一个小姐姐，并不记得当时学了什么orz

题目链接

题意：

给出若干个点，在给出一个定点，求距离该定点最近的m个点。

思路：

我们已经知道kd-tree可以得到最近邻，实际上M近邻，只需要维护一个size为M的优先队列就可以了。

题目链接

题意：

有若干个(2E5)旅馆，分别给出旅馆的坐标和价格。有m个查询，每个查询给出一个人的位置(x0,y0),以及其能接受的最高价格。问在该人能接受的价格内，距离其最近的旅馆的坐标和价格是多少。

题目链接：hdu2966  

题意：

给出二维平面上n(1E5)个点，问对于每个点，其他距离其最近的点的距离是多少。

思路：

kd-tree 裸题。

kd-tree 学习笔记

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年10月08日 星期日 18时43分38秒
  4File Name :2996.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8 …

老规矩，资料先行。

好久没学新算法了，有点忘记怎么学了orz

K-D tree 数据结构

hdu 2966 In case of failure　（k-d树　最近邻近点）

首先来看算法的提出。

现在二维平面上有n个点，知道这n个点的坐标，然后再添加一个点，问n个点中，距离新添加的点距离最近的点。

题意：

W_H的方格纸，共有(w+1)_(H+1)个整点，现在将2个蜡烛放在2个不同的整点上。蜡烛不会被放在边界上。现在给出方格纸的尺寸和2个蜡烛的坐标，求一条线段将方格纸拆成2部分，而且这条线段不经过任何一个蜡烛且使得每一部分恰好有一个蜡烛。问线段的起点和终点。

题目链接

题意：

有一只熊，初始在(sx,sy)处，如果当前的位置在(x,y)，那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处， dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1]，k表示的是某个点的花丛数目。

题目链接

题意：

求f[n] = f[n-1] + f[n-2] + 1，在b(10000)进制下的最后一位数字的十进制表示。

思路：

构造矩阵即可，M矩阵是一个3_3的矩阵，M1矩阵是一个3_1的矩阵。。很easy，就不说了。

hdu4686题目链接

题意：

An Arc of Dream is a curve defined by following function:

where a 0 = A0 a i = a i-1_AX+AY b 0 = B0 b i = b i-1_BX+BY What is the value of AoD(N) modulo 1,000,000,007?

思路：

看n的1E18的范围也知道是矩阵快速幂。。

难点还是构造矩阵。

uva10870题目链接

题意：

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f[1]..f[d],a[1]..a[d],问 f[n]%m是多少。

思路：

构造矩阵，加速递推式。

uva10655题目链接

题意：

给出a+b和ab的值，问a^n+b^n

思路：

构造矩阵,手写一下很显然…

转移矩阵M=[0 , 1]

[-q,p ]

初始矩阵M1=[p           ]

[p^2-2*q]

快速幂即可。

有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。

16年北京网络赛遇到了这个技巧…但是竟然忘记记了下来？

快速乘是为了解决 计算a_b % mod 时a_b溢出LL 的问题

比如a=1E16,b=1E16,mod=1E18，虽然最后的结果没有溢出，但是中间溢出了。

题目链接

题意：

给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n]

思路：

显然是矩阵快速幂，终点在于构造矩阵。

hdu5015题目链接

题意：

给出矩阵的构造规则： a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1)，对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]

hdu3642题目链接

题意：给出若干个（1000）长方体，求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x，y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.