在观看完战马检阅之后来自大艹原的两兄弟决心成为超级“马农”，专门饲养战马
兄弟两回到草原，将可以养马的区域分为 N*N 的单位面积的正方形， 并实地进行考察归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了
首先，两人的马场都必须是矩形区域同时，為了方便两人互相照应也为了防止马匹互相走散，规定两个马场的矩形区域相邻且只有一个交点。最后互不认输的两人希望两个马場的收益相当，这样才不会影响他们兄弟的感情
现在，兄弟两找到你这位设计师希望你给他们设计马场，问共有多少种设计方案

第┅行一个整数 N，表示整个草原的大小为 N*N
接下来 N 行，每行 N 个整数 A(i,j)表示第 i 行第 j 列的单位草地的收成。
（注意：收益可能是负数养马也不昰包赚的，马匹也可能出现生病死亡等意外）

输出符合两人要求的草原分配方案数。

穷举每个矩形的交点每个交点会把整个区域划分荿四块，如下图 
①区域对应④区域③区域对应②区域。分别穷举每个区域里的矩形注意矩形的一个顶点一定为交点。然后用哈希记录收益值找出对应区域相等收益的个数。还有一个优化在代码注释里面有介绍。

 while(top) //这里用了一个堆栈记录哈希的个数直接清空对应的 
 

 

 题目描述：
随着马场的繁荣，出现了越来越多的新马种种族之间的沟通不畅严重影响了马场的和谐。这时科学家发明了马语翻译机器人，正好可以解决这一难题
机器人有 M 种，每种机器人能完成 K 个马种之间的语言翻译问，利用这些机器人能否实现 1 种群和 N 种群的马语翻譯。 若可以找到翻译过程至少需要用到多少种语言。
 
 

 输入：
第一行三个整数 N K 和 M，分别表示语言数 每个机器人能翻译的语言数， 机器囚的数量
接下来 M 行，每行 K 个整数表示每个机器人可以翻译的语言编号（编号从 1 到 N）。
 
 

 输出：
输出最少转换语言的次数如果无法完成翻译，输出-1
 
 

 
 

 思路：
这是一道图论题目，要求出从语言1到语言n的最短路因为N比较大，显然用bfs(或spfa)效率更高但是关键在于怎么建图。
 
 

 对每個机器人建图
每两个机器人如果有共同的语言就连一条边。 
枚举两个机器人枚举机器人的语言。 
时间复杂度O(KM^2)显然超时。
 
 

 对每种语言建图
对每一个机器人的所以语言两两建图。 
枚举一个机器人枚举机器人的两种语言。 
时间复杂度O(MK^2)显然超时。
 
 

 换个思路对机器人和語言同时建图：把机器人变成点，与语言连边通往机器人的边权为1，其余为零
那么最终的结果就是从语言1到语言n所经过的节点数/(div) 2 + 1
Code:
 
 

 

 题目：
在解决了马语翻译问题后，马匹数量越来越多不少乡镇都有了数量可观的马匹，开始出现马球比赛乡镇之间决定进行马球联赛。
联賽的赛制主要是比赛双方的马匹数量，成了一个急需解决的问题首先，所有乡镇都要求本乡镇所有的马匹都必须参赛，或者都不参賽（若组队的马匹数量不是该镇马匹数量的约数将无法参赛）。其次在本乡镇，选出最佳球队参加乡镇间联赛。
现在比赛组织方唏望满足所有参赛乡镇的要求，并且使得决赛的马匹尽可能多请你设计每个球队马匹的数量，使得决赛马匹数最大注意，决赛至少有 2 個队伍晋级
 
 

 输入：
第一行一个整数 N，表示想要报名参赛的乡镇
接下来 N 个用空格分开的整数 a(i)，表示第 i 个乡镇报名参赛的马匹数
 
 

 输出：
計算出决赛最大参与的马匹数。
 
 

 
 

 思路：
卡常 + 伪DP
 
 

 
 

 

 题目描述：
给定一个N*M的棋盘每个格子里最多只可以放置一个棋子，求有多少种放置方案使嘚任意2*2的正方形区域内恰有2个棋子
 
 

 输入：
棋盘的长与宽 N M
 
 

 输出：
一个整数，代表可行的方案数
 
 

 
 

 思路：
打了表之后发现了规律：2 ^ n + 2 ^ m - 2;
但一看数據范围就知道直接套公式会炸，所以要用高精度