[编程题] 连续最大和
时间限制：1秒 空间限制：32768K 一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3 输入描述: 输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。 输出描述: 所有连续子数组中和最大的值。 输入例子1: 3 -1 2 1 输出例子1: 3
解析：
用f[i]表示以元素i结尾的子数组的最大元素和，则： f[i] = a[i] , i==0 或者 f[i-1] < 0 （前面的元素和小于0，则可以直接抛弃） f[i] = f[i-1] + a[i] , f[i-1] > 0 然后求出max(f[i])即可。
c++代码实现：
#include <iostream> using namespace std; long long maxSubSum(int *a,int n) { long long sum = 0; long long result = -2147483648; for(int i=0; i<n; i++){ if(sum<=0) sum = a[i]; else sum += a[i]; if(sum > result) result = sum; } return result; } int main() { int n; cin>>n; if(n<=0) return 0; int a[n]; for(int i=0; i<n; i++){ cin>>a[i]; } cout<<maxSubSum(a,n); return 0; }[编程题] 餐馆
时间限制：1秒 空间限制：32768K 某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大 输入描述: 输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。 输出描述: 输出一个整数,表示最大的总预计消费金额 输入例子1: 3 5 2 4 2 1 3 3 5 3 7 5 9 1 10 输出例子1: 20
解析：
贪心算法。将客人信息按照：金额降序，人数升序进行排序。然后将桌子按容量进行升序排序。然后枚举每批客人查找当前最适合的桌子容量，采用二分查找。
C++代码实现：
#include <iostream> #include <algorithm> #include <set> using namespace std; typedef struct{ int num; int money; }Customer; unsigned long long maxIncoming(int n,int m,int *container,Customer* customer) { multiset<int> table(container,container+n); sort(customer,customer+m,[](const Customer &c1,const Customer& c2){ if(c1.money != c2.money) return c1.money > c2.money; return c1.num < c2.num; }); unsigned long long total = 0; for(int i=0; i<m; i++){ auto it = table.lower_bound(customer[i].num); if(it!=table.end()){ total += customer[i].money; table.erase(it); } } return total; } int main() { int n,m; cin>>n>>m; int container[n]; Customer customer[m]; for(int i=0; i<n; i++) cin>>container[i]; for(int i=0; i<m; i++) cin>>customer[i].num>>customer[i].money; cout<<maxIncoming(n,m,container,customer); return 0; }[编程题] 地下迷宫
时间限制：1秒 空间限制：32768K 小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。 输入描述: 输入包括n+1行: 第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100) 接下来的n行: 每行m个0或者1,以空格分隔 输出描述: 如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出”Can not escape!”。 测试数据保证答案唯一 输入例子1: 4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 输出例子1: [0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
解析：
深度搜索。从起点开始，有四个方向可以走，每走一步，判断其是否到达出口且体力大于0，如果是，则表示找到一条路径，更新路径信息；如果不是出口，则依次探测4个方向。直至所有路径遍历完毕。代码有详细解释。
C++代码实现：
#include <iostream> #include <vector> using namespace std; typedef struct Point{ int row; int col; Point(int x,int y):row(x),col(y){} Point():row(0),col(0){} }Point; int direction[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; int cost[4] = {0,-1,-3,-1}; int maze[10][10]; int n,m,p; vector<Point> bestPath; vector<Point> curPath; int maxPower = 0x80000000; void printPath() { int i=0; for(; i<bestPath.size()-1; i++) cout<<"["<<bestPath[i].row<<","<<bestPath[i].col<<"],"; cout<<"["<<bestPath[i].row<<","<<bestPath[i].col<<"]"; } void findPath(int x,int y,int curPower) { //将当前节点加入路径中标记为visited curPath.push_back(Point(x,y)); maze[x][y] = 2; //visited //到达出口，找到一条路径 if(x==0 && y==m-1 && curPower>=0){ //找到一条路径 if(curPower > maxPower){ bestPath = curPath; maxPower = curPower; } curPath.pop_back(); //回退至上一步 maze[x][y] = 1; //还原 return; } //当前节点并非出口，且体力不为0，则往4个方向上继续探测 if(curPower>=0){ for(int i=0; i<4; i++){ int cx = x+direction[i][0]; int cy = y+direction[i][1]; int cp = curPower+cost[i]; if(cx>=0 && cx<=n && cy>=0 && cy<=m && cp>=0 && maze[cx][cy]==1) findPath(cx,cy,cp); } } curPath.pop_back(); //回退至上一步 maze[x][y] = 1; //还原 } int main() { cin>>n>>m>>p; for(int i=0; i<n; i++){ for(int j=0; j<m; j++) cin>>maze[i][j]; } findPath(0,0,p); if(maxPower>=0) printPath(); else cout<<"Can not escape!"; return 0; }[编程题] 末尾0的个数
时间限制：1秒 空间限制：32768K 输入一个正整数n,求n!(即阶乘)末尾有多少个0？ 比如: n = 10; n! = 3628800,所以答案为2 输入描述: 输入为一行，n(1 ≤ n ≤ 1000) 输出描述: 输出一个整数,即题目所求 输入例子1: 10 输出例子1: 2
解析
分析一下末尾0会在什么情况下出现？ （1） 5（数字末尾位5）乘于一个偶数，结果肯定有0； （2）数字末尾就是0的，结果也有0； 第二条可以转变成5*x的形式，比如15=5*3，25=5*5 因此，计算n！结果中末尾0的个数，只需要找到[1-n] n个数中，因子5的个数。 注意：类似于25，可以拆分成5*5，需要注意。
C++代码实现：
#include <iostream> using namespace std; int endWithZero(int n) { if(n<5) return 0; int count = 0, i,j; for(i=5; i<=n; i+=5){ j = i; while(j%5==0){ count++; j /= 5; } } return count; } int main() { int n; cin>>n; if(n<1 || n>1000) return 0; cout<<endWithZero(n); return 0; }[编程题] 进制转换
时间限制：1秒 空间限制：32768K 给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数 输入描述: 输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。 输出描述: 为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等） 输入例子1: 7 2 输出例子1: 111
解析：
（1）注意负数，需要转换成正数； （2）如果是-2147483648，转换位正数是214748648，超出了32位int范围，得用unsigned int或者long 。
c++代码实现：
#include <iostream> using namespace std; string factor = "0123456789ABCDEF"; void decToN(int num,int n) { if(num==0){ cout<<0; return; } bool flag = true; unsigned int m = 0; if(num<0){ m = ~num + 1; //注意-2147483648 ~ 2147483647 flag = false; } else m = num; int index = 31; char str[32]={0}; while(m!=0){ str[index--] = factor[m%n]; m /= n; } if(!flag) cout<<'-'; for(int i=index+1; i<32; i++) cout<<str[i]; } int main() { int m,n; cin>>m>>n; if(n<2 || n>16) return 0; decToN(m,n); return 0; }[编程题] 数字和为sum的方法数
时间限制：1秒 空间限制：32768K 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述: 输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数Ai，以空格隔开。 输出描述: 输出所求的方案数 输入例子1: 5 15 5 5 10 2 3 输出例子1: 4
解析：
（1）深度搜索。先对数组降序排序。然后用深度搜索。注意递归容易超时，需要用一个额外的数组来保存中间结果。 （2）动态规划。dp[i][j]代表前i个元素和为j的方案数量。 初始：dp[i][0] = 1(全部元素都不取，则和为0), dp[0][j] = 0; 推导方程： dp[i][j] = dp[i-1]j + dp[i-1][j-num[i]] (取第i个元素)，if(j>=num[i]) dp[i][j] = dp[i-1][j], if (j < num[i])。
C++代码实现： 深度搜索
#include <iostream> #include <algorithm> #include <vector> using namespace std; int num[1000] = {0}; int sum = 0; int n = 0; vector<vector<long long>> dp; long long dfs(int last,int restSum) { if(restSum==0) return 1; if(dp[last][restSum]!=-1) return dp[last][restSum]; long long count = 0; for(int i=last; i<n; i++){ if(restSum >= num[i]) count += dfs(i+1,restSum-num[i]); } dp[last][restSum] = count; return count; } long long numberOfSum() { sort(num,num+n,greater<int>()); return dfs(0,sum); } int main() { cin>>n>>sum; dp.resize(n+1,vector<long long>(sum+1,-1)); for(int i=0; i<n; i++) cin>>num[i]; cout<<numberOfSum(); return 0; }动态规划
#include <iostream> using namespace std; int num[1000] = {0}; int sum = 0; int n = 0; long long dp[1001][1001]={0}; long long numberOfSum() { for(int j=0; j<1001; j++) dp[0][j] = 0; for(int i=0; i<1001; i++) dp[i][0] = 1; //前i个元素和为0只有一种方案，就是全都不取 for(int i=1; i<=n; i++){ for(int j=0; j<=sum; j++){ if(j>=num[i-1]) dp[i][j] = dp[i-1][j] + dp[i-1][j-num[i-1]]; else dp[i][j] = dp[i-1][j]; } } return dp[n][sum]; } int main() { cin>>n>>sum; for(int i=0; i<n; i++) cin>>num[i]; cout<<numberOfSum(); return 0; }