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

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

Dijkstra算法

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

        分解质因数算法是一种很重要的数论算法。

难度：省选/NOI-

题目背景

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

难度：提高+/省选-

题目描述

        给出如下定义:
        子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
        例如，下面左图中选取第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列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。

难度：提高+/省选-

题目描述

        “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2¹⁶范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。
这里是某支股票的价格清单:
        日期 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

难度：提高+/省选-

题目描述

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

难度：提高+/省选-

题目描述

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

难度：提高+/省选-

题目描述

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