1、创意吃鱼法Time Limit:3000MS Memory Limit:65536KTotal Submit:70 Accepted:13 Description 回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢。她发现，把大池子视为 01 矩阵（0 表示对应位置无鱼，1 表示对应位置有鱼）有助于决定吃鱼策略。 在代表池子的 01 矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“ 对角线的一端 ”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。 猫猫是个贪婪的家伙，
2、所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？ Input 第一行有两个整数 n 和 m（n，m1），描述池塘规模。接下来的 n 行，每行有m 个数字（非“0”即“1”）。每两个数字之间用空格隔开。Output 只有一个整数猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。Sample Input 4 60 1 0 1 0 00 0 1 0 1 01 1 0 0 0 10 1 1 0 1 0Sample Output 3Hint 数据范围 Date Range： 对于 30%的数据，有 n、m100；对于 60%的数据，有 n、m1000 ；对于 100%
3、的数据，有 n、m2500。 瑞士轮Time Limit:2000MS Memory Limit:65536KTotal Submit:5 Accepted:3 Description 在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。 本题中介绍的瑞士轮赛制，因最早使用于 1895 年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折衷，既保证了比赛的稳定性，又能使赛程不至于过长。 2*N 名编号为 12N 的选手共进行 R 轮比赛。每
4、轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关：第 1 名和第 2 名、第3 名和第 4 名、第 2K-1 名和第 2K 名、第 2N-1 名和第 2N 名，各进行一场比赛。每场比赛胜者得 1 分，负者得 0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值，试计算在 R 轮比赛过后，排名第Q 的选手编号是多少。我们假设选手的实力值两两
5、不同，且每场比赛中实力值较高的总能获胜。Input 输入文件名为 swiss.in。 输入的第一行是三个正整数 N、R、Q，每两个数之间用一个空格隔开，表示有 2*N 名选手、R 轮比赛，以及我们关心的名次 Q。 第二行是 2*N 个非负整数 s1, s2, , s2N，每两个数之间用一个空格隔开，其中 si 表示编号为 i 的选手的初始分数。 第三行是 2*N 个正整数 w1, w2, , w2N，每两个数之间用一个空格隔开，其中 wi 表示编号为 i 的选手的实力值。Output 输出文件名为 swiss.out。 输出只有一行，包含一个整数，即 R 轮比赛结束后，排名第 Q 的选手的编号
6、。Sample Input 2 4 27 6 6 710 5 20 15Sample Output 1Hint 输入输出样例说明 本轮对阵 本轮结束后的得分 选手编号 初始 7 6 6 7 第 1 轮 7 6 7 8 第 2 轮 7 6 8 9 第 3 轮 8 6 9 9 第 4 轮 9 6 10 9 数据范围 对于 30%的数据，1N100；对于 50%的数据， 1N10,000； 对于 100%的数据，1N100,000，1R50，1Q2N，0s1, s2, , s2N108，1w1, w2, , w2N108。 Source NOIP2011P农田个数Time Limit:1000MS
7、Memory Limit:65536KTotal Submit:56 Accepted:28 Description 你的老家在河北农村。过年时，你回老家去拜年。你家有一片 N*M 农田，将其看成一个 N*M 的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题。他问你：这片农田总共包含了多少个不存在水域的正方形农田。 两个正方形农田不同必须至少包含下面的两个条件中的一条： （1）边长不相等； （2）左上角的方格不是同一方格。 Input 输入数据第一行为两个由空格分开的正整数 N、M（1=mn=1000） 第 2 行到第 N+1 行每行有 M 个数字（0 或 1），
8、描述了这一片农田。0 表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格） Output 满足条件的正方形农田个数。Sample Input 3 3110110000Sample Output 5Hint 样例解释 Sample Explan： 边长为 1 的正方形农田有 4 块；边长为 2 的正方形农田有 1 块；合起来就是 5块。 恺撒的规划Time Limit:1000MS Memory Limit:65536KTotal Submit:57 Accepted:31 Description 亚特兰蒂斯是一块富饶美丽的土地。恺撒大帝率领他的大军，经过了一整年的浴血
9、奋战，终于将它纳入了罗马帝国的版图。然而，长期的战火彻底抹去了这里的繁华，昔日的富庶之地如今一片荒芜。恺撒大帝作为一位有着雄才大略的君主，决心在战争的废墟上建起一座更为宏伟的城市。所以，在建城之前，他需要对整个城市进行规划。 亚特兰蒂斯是一块矩形平原，恺撒准备在上面修建一些建筑。为了规划方便，他将矩形划分成 N*M 格。棘手的是，部分古老的神庙残存下来，散布在某些格子内。亚特兰蒂斯的原住民原本就十分信奉神灵，而这些经过战火洗礼的神庙更是被他们视为圣物，是万万不能拆除的，否则将激起民愤，甚至引发暴动。恺撒深知这一点，因此，他的新建筑在选址时要避开这些神庙。 假设新的建筑物有 P 种规格，每种建筑
10、物都是正方形的，占地为 Ti*Ti 格（1=i=P）。恺撒想知道对于每种规格的建筑，有多少种不同的合适选址方案（一种合适的选址方案指的是在该建筑所占的正方形区域内不存在神庙）。作为他的内务部长，这个光荣而艰巨的任务自然交给你来完成。 Input 输入文件第一行包含三个数，分别代表N、M、P（1 =N、M=2000，1=P=1000）。 随后的 n 行，每行有 m 个 0 或 1（1 表示该格为废墟， 0 表示该格有神庙）。 接下来的 P 行每行有一个整数 X（1X=max(M,N)），代表的第 i 种建筑物的边长。 Output 输出文件有 P 行，每行一个整数，第 i 行的数代表边长为 Ti 的建筑物选址方案数。Sample Input 4 4 2101111111110111023Sample Output 51
