快速幂

        现在来认识一种新的求幂算法—快速幂算法。这个算法可以在O(logn)的时间复杂度下计算nm的值(要求m为自然数)。相比朴素O(n)累乘算法,效率大大提升。
        快速幂算法基于倍增思想,是倍增算法的一个应用。

阅读全文〉

Floyd算法

        除了Dijkstra算法和SPFA算法,另一种求最短路方法是Floyd算法。这个算法可以求出任意两点之间的最短路径长度,支持负边权,需要用邻接矩阵存图。
        算法缺点是耗时过大,时间复杂度O(n3)。
算法步骤:
        1 初始化dist数组,邻接节点dist值即为相邻边权值,否则为inf(无穷大)。
        2 枚举每一个节点,用这个节点作中介,更新所有节点对的最短路径值。
        最后dist即为最短路径数组,如果为inf则两点不连通。

阅读全文〉

Dijkstra算法与SPFA

Dijkstra算法

        Dijkstra算法是一种基于贪心思想的求单源最短路算法,时间复杂度为$O(n^2)$。Dijkstra算法要求边权为正。
步骤:
        ① 一个数组dis[]保存最短路径长的结果,源点值置为0,其余为inf。
        ② 一个集合S保存所有已求出最短路径长的节点,初始化S为空。
        ③ 从不在S中的节点集合中找到dis最小的节点,用这个节点更新与之相邻的的节点dis值(这个过程叫松弛),并将这个节点加入S。
        重复③,直到所有节点都加入S中。

阅读全文〉

[洛谷P2123]皇后游戏

难度:省选/NOI-

题目背景

        还记得 NOIP 2012 提高组 Day1 的国王游戏吗?时光飞逝,光阴荏苒,两年过去了。国王游戏早已过时,如今已被皇后游戏取代,请你来解决类似于国王游戏的另一个问题。

阅读全文〉

[洛谷P2258]子矩阵

难度:提高+/省选-

题目描述

        给出如下定义:
        子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
        例如,下面左图中选取第2,4行和第2,4,5列交叉位置的元素得到一个2×3的子矩阵如图所示。
9     3     3     3     9
9     4     8     7     4
1     7     4     6     6
6     8     5     6     9
7     4     5     6     1
的其中一个2×3的子矩阵是
4     7     4
8     6     9

        相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
        矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。
        本题任务:给定一个n行m列的正整数矩阵,请你从这个矩阵中选出一个r行c列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

阅读全文〉

[洛谷P1108]低价购买

难度:提高+/省选-

题目描述

        “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。
这里是某支股票的价格清单:
        日期 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8, 9 ,10 ,11, 12
        价格68 ,69 ,54, 64,68 ,64 ,70 ,67 ,78 ,62, 98, 87
最优秀的投资者可以购买最多4次股票,可行方案中的一种是:
        日期 2 , 5 , 6 ,10
        价格 69, 68 ,64 ,62

阅读全文〉

[洛谷P1736]创意吃鱼法

难度:提高+/省选-

题目描述

        回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中,然后开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法 ^_*)。她发现,把大池子视为01矩阵(0表示对应位置无鱼,1表示对应位置有鱼)有助于决定吃鱼策略。
        在代表池子的01矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线的一端”下口,只一吸,就能把对角线上的那一队鲜鱼吸入口中。
        猫猫是个贪婪的家伙,所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下,她一口下去,最多可以吃掉多少条鱼?

阅读全文〉

[洛谷P2158]仪仗队

难度:提高+/省选-

题目描述

        作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。

阅读全文〉

[洛谷P1052]过河

难度:提高+/省选-

题目描述

        在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,… ,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。
        题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

阅读全文〉