题目描述Farmer John's N (1 \leq N \leq 50,000)N(1≤N≤50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, the...

题目描述BackgroundCharlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death!  The teacher points to the blackboard (Fig. 4) and says: "So here is the problem:There are three to...

题目描述很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。 输入描述:第一行一个 DNA 字符串 S。接下来一个数字 m，表示 m 次询问。接下来 m 行，每行四个数字 l1, r1, l2, r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。其中 1≤length(S),m≤1000...

题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，...

题目描述在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。 输入描述:第一行一个整数N，第二行N个整数A[1]~A[N]。 输出描述:一个整数，表示距离之和的最小值。 思路：这类问题都是：在数轴上选一点到其他点的距离最短，直接中位数就行了。 代码： #include <iostream> #include <algorithm> using namespace std; const int N = 1e+5; int...

题目描述监狱有连续编号为1到n的n个房间，每个房间关押一个犯人。有m种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。 输入描述:输入两个整数m和n。 输出描述:可能越狱的状态数，对100003取余。 思路：根据推导，得出了不能出狱的情况。将所有情况减去不能出狱的情况就好了：m的n次幂-m*（m-1）的（n-1）次幂。这道题暴力很难出奇迹啊。所以只能用快速幂过了。 什么是快速幂：快速幂是一种简化运算底数的n次幂的算法，理论上其时间复杂度为 O(log₂N)，而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数...

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 输入描述:第一行一个正整数n ≤ 987654321，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数． 输出描述:求使所有人获得均等糖果的最小代价。 思路：开始是n个小孩围成一圈，第i个小孩有ai个糖果（可以自己画个图）。他们的平均值ave就是：总的糖果数/n。可以用Xi表示第i个小孩给了第i-1个小孩Xi个糖果（即，第1个小孩给了第n个小孩X1个糖果，第二个小孩给了第一个小孩X2个糖果）。如果Xi为负数，反过来就是索取了Xi个糖果。我们这里可以推导出：...

题目描述n个小伙伴（编号从0到n-1）围坐一圈玩游戏。按照顺时针方向给n个位置编号，从0到n-1。最初，第0号小伙伴在第0号位置，第1号小伙伴在第1号位置，……，依此类推。游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m号位置，第1号位置小伙伴走到第m+1号位置，……，依此类推，第n−m号位置上的小伙伴走到第0号位置，第n-m+1号位置上的小伙伴走到第1号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。现在，一共进行了轮，请问x号小伙伴最后走到了第几号位置。 输入描述:输入共1行，包含4个整数n、m、k、x，每两个整数之间用一个空格隔开。 输出描述:输出共1行，包含1个整数...

题目描述BSNY在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第k项的值吗。如果第k项的值太大，对200907取模。 输入描述:第一行一个整数T，表示有T组测试数据；对于每组测试数据，输入前三项a,b,c，然后输入k。 输出描述:对于每组数据输出第k项的值，对200907取模。 思路：一看题目就知道使用快速幂了，不多解释了。 什么是快速幂与时间复杂度分析：快速幂是一种简化运算底数的n次幂的算法，理论上其时间复杂度为 O(log₂N)，而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就...

*题目描述 *People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that ...

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 输入描述:第一行一个正整数n ≤ 987654321，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数． 输出描述:求使所有人获得均等糖果的最小代价。 思路：开始是n个小孩围成一圈，第i个小孩有ai个糖果（可以自己画个图）。他们的平均值ave就是：总的糖果数/n。可以用Xi表示第i个小孩给了第i-1个小孩Xi个糖果（即，第1个小孩给了第n个小孩X1个糖果，第二个小孩给了第一个小孩X2个糖果）。如果Xi为负数，反过来就是索取了Xi个糖果。我们这里可以推导出：...

*题目描述 *Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum i...

题目描述Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。 输入描述:Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是 。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？ 输出描述:第一行包含两个用空格隔开的整数，N和W。接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量 。  思路：狗粮题（划掉）。看...