TZOJ
tzoj7929: Matrix Power Series
题意 给定一个n*n大小的矩阵A，求以A为公比的等比数列的前k项和。 解题思路 直接从1到k矩阵快速幂每项相加肯定是会超时的，而如果用公式计算需要求逆矩阵非常麻烦，而且有可能会溢出。 因此我们使用分治求解。 当n为奇数时， 当n为偶数时， 分治求解即可。 #include <bits/stdc++. ......
TZOJ3326--Barn Repair(优先队列，贪心)
题目简述： 某天刮了一阵大风，把牛棚的门吹飞了，总共有s个牛棚，幸运的是并不是每个牛棚都有牛。现在你可以购买m块木板，商店里有各种型号的木板，木板长度为多少就需要多少金钱。木板用来给牛棚装上门。要求把所有有牛的牛棚都装上门，并且花的金钱最少。 给了一正整数C，接下来C行每行一个正整数，表示该牛棚有牛 ......
tzoj3348 线段相交Ⅲ
就是个解方程。 #include <bits/stdc++.h> #define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; double ansx, ansy; bool pingxing(do ......
tzoj5103 Electric Fence 电网
题目大意 给定三个正整数n，m和p，将(0,0) (n,m) (0,p) 这三个点相连，求围成的三角形中的格点数目(三角形边上的格点不算) 利用皮克定理求出。 皮克定理 顶点全在格点上的多边形面积S=n+T/2-1。 n为多边形内部格点数量，T为多边形边上的格点数量。 解题方法 内部格点数量n=S- ......
TZOJ4295--Modular Inverse
题目简述： 给你一个整数a（0<a<=1000）和一个模数m(0<m<=1000)，问是否存在一个正整数x使得a*x%m=1，使x尽可能小。 标准输入 33 114 125 13 标准输出 4Not Exist8 思路1： 暴力，观察数据很显然，x的范围是0~（m-1），由于输出要求x为正整数，当x ......
tzoj1471 wall（凸包模板题）
题目大意 n个点构成的城堡，给出每个点的坐标。若要修建距离城堡最近距离为L的城墙，问城墙的最短长度。 凸包模板题，用Andrew算法求出凸包然后加上半径为L的圆的周长即可。 Andrew算法 首先对所有点按照y大小进行升序排序，如果y相同就按照x大小升序排序。 构造上凸包 前两个点直接入栈。随后遍历 ......
tzoj4954 矩阵游戏
题目大意: 已知 a,b,c,d,n,m已知, 求f(n,m). 数据范围 1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9 首先用到费马小定理将n和m缩小到int范围。 费马小定理 其中p为质数，a为不是p的倍数的正整数。 首先用到高中的数列。 F(n,m)=a·F(n,m ......
TZOJ8036--生日礼物
题目简述： 给你n个数，让你选取不超过m个连续的区间，区间不重叠，求区间总和最大。 标准输入 5 2 2 -3 2 -1 2 标准输出 5 思路： 1.很显然能够想到把原数组简化成形如一正一负的数组。 2.特殊情况，当正数连续块小于等于m时答案很显然是所有正数相加。 3.一般情况，当正数连续块大于m ......
TZOJ 1072: 编辑距离 动态规划
描述 假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需 ......
TZOJ 4776: 乘积最大 动态规划
描述 今年是国际数学联盟确定的“2000――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘 ......