前缀和求矩阵子矩阵元素最大和 emmm很早之前我看这道题是直接放弃的，最近看了一下前缀和，对这道题重新进行了理解。 然后大概看了看别人的博客，结合自己的的理解，大概会做了。 题目链接：SWUST OJ 130 大概思路：  对于这样一个矩阵，最大的矩形前缀和就等于蓝的矩阵加上绿的矩阵，再减去重叠面积，最后加上小方块，即 sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j]； 我们就可以进行预处理： for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ su...

记忆化搜索： 顾名思义就是dfs+dp，简…一点不简单，很暴力。 不多BB，直接上题： Virtual Judge - How many ways Problem Description 这是一个简单的生存游戏，你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下： 1.机器人一开始在棋盘的起始点并有起始点所标有的能量。 2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。 3.机器人不能在原地停留。 4.当机器人选择了一条可行路径后，当他走到这条路径的终点时，他将只有终点所标记的能量。  如上图，机器人一开始在(1,1)点，并拥有4单位能量，蓝色方块...

再谈记忆化搜索 题目描述： FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going t...

完全背包简单题目 题目： Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and ...

多重背包之二进制优化 题目描述： Problem Description Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half...

题目描述： Problem Description People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, …, and 289-credit coins, are available in Silve...

变化的01背包 题目描述： 题目：Cow Exhibition Description “Fat and docile, big and dumb, they look so stupid, they aren’t much fun…”  Cows with Guns by Dana Lyons  The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by ...

两种素数筛法 引言： 唯一分解定理：算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3…Pnan，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。 **思想：**素数可以组成其他的所有合数，所以我们对每一个素数进行筛选的时候，可以考虑素数组成的数，那就一定不是素数，因此就有了两种筛法。 1.nlognlogn的算法： #include<stdio.h> #include<iostream> #include<algorit...

扩展欧几里得 定义： 扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。 注意： 对于我们求出的解只是一个特解，而且不是对应ax + by = c的解，需要去乘一个c/gcd(a,b)倍。他...

矩阵快速幂 大意： 就是对矩阵求快速幂，将快速幂中res=1换成单位阵，而取模运算完全在我们定义的乘法运算中进行，即Mul，其他的跟快速幂没有区别，当然我现在只掌握了基础，所以做了一道模板题。 题目描述： 题目链接：洛谷-p3390 题目背景 矩阵快速幂 题目描述 给定n*n的矩阵A，求A^k 输入输出格式 输入格式： 第一行，n,k 第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素 输出格式： 输出A^k 共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7 输入输出样例 输入样例#1： 2 1 1 1 1 1 输出样例#1： 1 1 ...

最短路径问题 引言： 最短路大家都不陌生吧，他可以是两点之间的最短路（Floyd），也可以是单源最短路，即一个点到其他点的最短距离（Dijkstra和SPFA）。Floyd对于n个顶点（n>100）的图，就会T，所以我们经常用后面两种算法。 相关题目： HDU-1874:畅通工程续  这道题吧，随便一种方法都能过…很神奇。 接下来是三种方法解这道题： 1.Floyd： for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(mp[i][j]>mp[i][k]+mp[k][j]) mp...

拓扑 定义： 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 方法： 由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。 (1) 选择一个入度为0的顶点并输出之； (2) 从网中删除此顶点及所有出边。 删除顶点以及出边的操...

题目： HDU-1863  Kruskal算法： int f[maxn]; struct node{ int u,v; int w; bool operator < (const node &s) const{ return w<s.w; } }edge[maxn];  用一个结构体来存储每一条边，f数组用来作点集，即并查集。细心你会发现我重载了小于号，用于对边的权值按从小到大排序，你写成w>s.w就是从大到小了，嘻嘻嘻。 wait，我刚刚说并查集，嘿嘿，没错。我们算法的思想是每次选择价值最小的边，然后选择了之后，就要将这两条边的顶点归入同一个集合。下一次选择的时候就...

扩展欧几里得 题目链接：The Balance 题目描述： Description Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weight...