1、[编程题]合唱团
有 n个学生站成一排,每个学生有一个能力值,牛牛想从这 n个学生中按照顺序选取 k名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k个学生的能力值的乘积最大,你能返回最大的乘积吗?
输入描述:
每个输入包含 1个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的2一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k和 d (1 <= k <= 10, 1<= d <= 50)。
输出描述:
输出一行表示最大的乘积。
输入例子:
3
7 4 7
2 50
输出例子:
49
思路:注意有负数的情况,因此当前最小值和最大值都应该存下来。
c++代码:
#include<iostream> #include<cmath> #include<limits.h> using namespace std; long long a[51]; long long maxval[11][51]; long long minval[11][51]; int main(){ int n; //n个学生 while(cin>>n){ int i,j,m; for(i=0;i<n;i++){ cin>>a[i]; }//输入n个学生的能力值 int k,d; cin>>k>>d; for(i=0;i<=k;i++){ for(j=0;j<=n;j++){ maxval[i][j] = minval[i][j] =0; //全部初始化为0 } } long long res=LONG_LONG_MIN; //max[k][i]:表示选中k个学生,以第i个学生结尾,产生的最大乘积 for(i=1;i<=n;i++){ //依次以这n个学生作为结尾 maxval[1][i] = minval[1][i] = a[i-1]; for(m=2;m<=k;m++){ for(j=i-1;j>0 &&(i-j)<=d;j--){ maxval[m][i] =max(maxval[m][i], max(maxval[m-1][j] * a[i-1], minval[m-1][j] * a[i-1])); minval[m][i] =min(minval[m][i], min(maxval[m-1][j] * a[i-1], minval[m-1][j] * a[i-1])); } } res = max(res, maxval[k][i]); } cout<<res<<endl; }//while return 0; }
2、[编程题]地牢逃脱
给定一个 n行 m列的地牢,其中 '.'表示可以通行的位置,'X'表示不可通行的障碍,牛牛从 (x0 , y0 )位置出发,遍历这个地牢,和一般的游戏所不同的是,他每一步只能按照一些指定的步长遍历地牢,要求每一步都不可以超过地牢的边界,也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下,他需要多少步才可以离开这个地牢。
输入描述:
每个输入包含 1个测试用例。每个测试用例的第一行包含两个整数 n和 m(1 <= n, m <= 50),表示地牢的长和宽。接下来的 n行,每行 m个字符,描述地牢,地牢将至少包含两个 '.'。接下来的一行,包含两个整数 x0, y0,表示牛牛的出发位置(0 <= x0 < n, 0 <= y0< m,左上角的坐标为(0, 0),出发位置一定是 '.')。之后的一行包含一个整数 k(0 < k <= 50)表示牛牛合法的步长数,接下来的 k行,每行两个整数 dx, dy表示每次可选择移动的行和列步长(-50 <= dx, dy <= 50)
输出描述:
输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢,如果永远无法离开,输出 -1。以下测试用例中,牛牛可以上下左右移动,在所有可通行的位置.上,地牢出口如果被设置在右下角,牛牛想离开需要移动的次数最多为3次。
输入例子:
3 3
...
...
...
0 1
4
1 0
0 1
-1 0
0 -1
输出例子:
3
思路:做这道题,理解题意很重要。我又没看懂题目,郁闷。在把别人的代码看懂了之后我还是觉得题目起的很烂。
这里解释一下难理解的部分:
(1)合法步数是指你可以选择这些步数里面的任意一个组合,所以才会有遍历所有步数的那段代码(这里我理解了很久)。采用广度优先遍历算法通过队列queue来实现。
(2)要求的问题是我们知道牛牛自己的起点,在终点(出口)是所有可通行格子中的一个的情况下,设哪一个格子为终点,会导致牛牛要走出去的最小步数最大?
(3)可瞬间移动,即不管中间是否有障碍物,只要目标位置不是障碍物,就可以移动到该位置。
c++代码:
#include<iostream> #include<queue> #include<limits.h> #include<algorithm> using namespace std; char ground[55][55]; //表示n行m列地牢的结构 int n,m; //表示地牢的长和宽,n行m列 int k; //表示合法的步长数 int direction[55][2]; //表示第i次时可选择移动的行和列步长 int dis[55][55]; //dis[i][j]表示从起点到(i,j)点的最小步数 struct Point{ int x,y; //表示该点的x和y Point(){}; Point(int a, int b):x(a),y(b){}; //构造函数 Point go(int i){ //在走第i次时 return Point(x+direction[i][0], y+direction[i][1]); } bool isOk(){ //表示当前节点的位置是否在地牢内 return x>=0&&y>=0&&x<n&&y<m&&ground[x][y]=='.'; } }; int main(){ while(cin>>n>>m){ int i,j; for(i=0;i<n;i++){ cin>>ground[i]; }//for 输入地牢结构 //输入起点 Point start; //起点 cin>>start.x; cin>>start.y; //输入合法步长 cin>>k; //输入每次可选择移动的行和步长 for(i=0;i<k;i++){ cin>>direction[i][0]>>direction[i][1]; } //初始化到所有点的距离为无穷大 fill(dis[0], dis[54]+55, INT_MAX); dis[start.x][start.y] = 0; //起点到起点的距离为0 queue<Point> q; //用广度遍历策略 q.push(start); //将起点加入队列 while(!q.empty()){ //当队列非空时 Point x = q.front(); //取出队列中第一个点 q.pop(); for(i=0;i<k;i++){ //遍历所有合法的步数 Point y = x.go(i); //假设x在走第i步后得到的节点 if(y.isOk()){ //当该节点在地牢内时 if(dis[y.x][y.y]>dis[x.x][x.y]+1){ dis[y.x][y.y] =dis[x.x][x.y]+1; q.push(y); } } } }//while int res=0; //表示最后的结果 for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(ground[i][j] =='.'){ res = max(res, dis[i][j]); } } } if(res == INT_MAX){ cout<<-1<<endl; }else{ cout<<res<<endl; } }//while return 0; }
3、[编程题]下厨房
牛牛想尝试一些新的料理,每个料理需要一些不同的材料,问完成所有的料理需要准备多少种不同的材料。
输入描述:
每个输入包含 1个测试用例。每个测试用例的第 i行,表示完成第 i 件料理需要哪些材料,各个材料用空格隔开,输入只包含大写英文字母和空格,输入文件不超过 50行,每一行不超过 50个字符。
输出描述:
输出一行一个数字表示完成所有料理需要多少种不同的材料。
输入例子:
BUTTER FLOUR
HONEY FLOUR EGG
输出例子:
4
思路:这道题不难,用set和map都容易写出来代码,但是一直在纠结怎么判断输入结束然后输出结果呢。后来发现测试的时候本来就是没办法输出。但是提交到牛客网显示AC。(摊手…)
c++代码(使用map):
#include<iostream> #include<map> using namespace std; int main(){ map<string,int> a; string tmp; int count=0; while(cin>>tmp){ if(a[tmp] == 0){ a[tmp] = 1; count++; }else{ a[tmp]++; } }//while cout<<count<<endl; return 0; } 使用set: #include<iostream> #include<set> using namespace std; int main() { string str; set<string> mat; int res=0; while(cin>>str) { if(mat.find(str)==mat.end()) { res++; mat.insert(str); } else continue; } cout<<res<<endl; return 0; }
4、[编程题]分田地
牛牛和 15个朋友来玩打土豪分田地的游戏,牛牛决定让你来分田地,地主的田地可以看成是一个矩形,每个位置有一个价值。分割田地的方法是横竖各切三刀,分成 16 份,作为领导干部,牛牛总是会选择其中总价值最小的一份田地,作为牛牛最好的朋友,你希望牛牛取得的田地的价值和尽可能大,你知道这个值最大可以是多少吗?
输入描述:
每个输入包含 1个测试用例。每个测试用例的第一行包含两个整数 n和 m(1 <= n, m <= 75),表示田地的大小,接下来的 n行,每行包含 m个 0-9 之间的数字,表示每块位置的价值。
输出描述:
输出一行表示牛牛所能取得的最大的价值。
输入例子:
4 4
3332
3233
3332
2323
输出例子:
2
思路:“最小值最大问题”,先二分试试。
枚举横向的三刀,纵向上在二分答案后贪心地靠左切,使得每个区域刚好全部大于等于答案,根据能否切满三刀来确定答案区间。这个时间复杂度算一下是O(n3mlogx)的,其中x是最大可能答案。
对于枚举横向的三刀,现在问题是如何确定这三刀,使得16个区域最小值最大。不妨先切中间那刀,那么问题变为如何切左边那刀和右边那刀,很显然这两个问题相互独立。用f[i]表示前i列的最优切法所得到的值,g[i]表示i~m列的最优切法得到的值,那么答案=max(min(f[i],g[i+1])),1<=i<m。容易证明f[i]和g[i]的最优决策都是单调的,于是它们都可以在O(m)的时间内算出来,因此最后复杂度变为O(n3m)。
此题较难理解,请多写几遍代码,死记硬背也要记下来。o( ̄ヘ ̄o#)
c++代码:
#include<iostream> #include<cstring> using namespace std; int a[76][76]; //存储每块田地的价值 int n,m; //表示田地的大小 int sum[76][76]; //sum[i][j]表示从(0,0)到(i, j)的田地总价值 int getArea(int x1, int y1, int x2, inty2){ return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1]; } bool judge(int mid){ //先枚举列切三刀的情况,然后横扫一遍 int i,j,k; for(i=1;i<=m-3;i++){ for(j=i+1;j<=m-2;j++){ for(k=j+1;k<=m-1;k++){ int pre_x=0,count=0; //pre_x 前一个x for(int x=1;x<=n;x++){ int area1 = getArea(pre_x,0, x, i); int area2 = getArea(pre_x,i, x, j); int area3 = getArea(pre_x,j, x, k); int area4 = getArea(pre_x,k, x, m); if(area1>=mid &&area2>=mid && area3>=mid && area4>=mid){ pre_x = x; count++; } } if(count>=4){ return true; } } } } return false; } int main(){ while(cin>>n>>m){ if(n<4 || m<4){ cout<<0<<endl; continue; } memset(sum, 0, sizeof(sum)); int i,j; char ch; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>ch; a[i][j] = ch-'0'; sum[i][j] = sum[i-1][j] +sum[i][j-1] - sum[i-1][j-1] + a[i][j]; }//for }//for int ans=0; //二分 int left=0, right=sum[n][m]; while(left<=right){ int mid=(left+right)>>1; //除以2 if(judge(mid)){ left = mid+1; ans = mid; }else{ right = mid-1; } }//while cout<<ans<<endl; } return 0; }
5、[编程题]分苹果
n 只奶牛坐在一排,每个奶牛拥有 ai 个苹果,现在你要在它们之间转移苹果,使得最后所有奶牛拥有的苹果数都相同,每一次,你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上,问最少需要移动多少次可以平分苹果,如果方案不存在输出 -1。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n(1 <= n <= 100),接下来的一行包含 n 个整数 ai(1 <= ai <= 100)。
输出描述:
输出一行表示最少需要移动多少次可以平分苹果,如果方案不存在则输出 -1。
输入例子:
4
7 15 9 5
输出例子:
3
思路:
(1)随着每头奶牛苹果的输入,算出总的苹果数,如果除以奶牛头数n可以除断,那么可以得到每头奶牛的苹果数。如果除不断,那么返回-1即可。
(2)得到了每头奶牛的苹果数each,遍历一遍所有奶牛的苹果,以苹果数大于each的奶牛为准。算出相差的苹果数tmp,如果tmp除不断2,直接返回-1。否则count += (tmp-each)/2。最后输出count。
c++代码:
#include<iostream> using namespace std; int main(){ int n; //n只奶牛 int a[101]; //a[i]表示第i只奶牛拥有的苹果数 while(cin>>n){ int i; int total=0; for(i=0;i<n;i++){ cin>>a[i]; total+=a[i]; }//for 输入 if(total%n != 0){ //说明不可能存在n头奶牛拥有苹果数相同的时候 cout<<-1<<endl; continue; } //否则每头奶牛拥有的苹果数是 total/n 个 int each = total/n; int count=0; for(i=0;i<n;i++){ if(a[i] == each){ continue; }else if(a[i]>each){ if((a[i]-each)%2 != 0){ cout<<-1<<endl; break; }else{ count += (a[i]-each)/2; } }else{ // a[i]<each的情况 if((each-a[i])%2 != 0){ cout<<-1<<endl; break; } } } if(i==n) cout<<count<<endl; }//while return 0; }
6、[编程题]星际穿越
航天飞行器是一项复杂而又精密的仪器,飞行器的损耗主要集中在发射和降落的过程,科学家根据实验数据估计,如果在发射过程中,产生了 x 程度的损耗,那么在降落的过程中就会产生 x2 程度的损耗,如果飞船的总损耗超过了它的耐久度,飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器,假设在飞行过程中不产生损耗,那么为了保证其1可以安全的到达目的地,只考虑整数解,至多发射过程中可以承受多少程度的损耗?
输入描述:
每个输入包含一个测试用例。每个测试用例包含一行一个整数 h(1 <= h <= 10^18)。
输出描述:
输出一行一个整数表示结果。
输入例子:
10
输出例子:
2
总结:
对于数字输入的时候能用long就别用int,这里经常会出现溢出。
c++代码:
#include<iostream> using namespace std; int main(){ long h; //一个飞行器的耐久度 while(cin>>h){ long i=0; while((i+i*i)<=h){ i++; } cout<<i-1<<endl; }//while return 0; }
7、[编程题]藏宝图
牛牛拿到了一个藏宝图,顺着藏宝图的指示,牛牛发现了一个藏宝盒,藏宝盒上有一个机关,机关每次会显示两个字符串 s 和 t,根据古老的传说,牛牛需要每次都回答 t是否是 s 的子序列。注意,子序列不要求在原字符串中是连续的,例如串 abc,它的子序列就有{空串, a, b, c, ab, ac, bc, abc} 8 种。
输入描述:
每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10的不包含空格的可见 ASCII字符串。
输出描述:
输出一行 “Yes”或者 “No”表示结果。
输入例子:
x.nowcoder.com
ooo
输出例子:
Yes
c++代码:
#include<iostream> #include<cstring> usingnamespace std; intmain(){ string s,t; //t是否是s的子序列 while(cin>>s>>t){ int len1 = s.length(); //总序列 int len2 = t.length(); //子序列 int i=0,j=0; while(i<len1 && j<len2){ if(s[i] == t[j]){ i++; j++; }else{ i++; } } if(j == len2){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } }//while return 0; }
8、[编程题]数列还原
牛牛的作业薄上有一个长度为 n 的排列 A,这个排列包含了从1到n的n个数,但是因为一些原因,其中有一些位置(不超过 10 个)看不清了,但是牛牛记得这个数列顺序对的数量是 k,顺序对是指满足 i < j 且 A[i] < A[j]的对数,请帮助牛牛计算出,符合这个要求的合法排列的数目。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n和 k(1 <= n <= 100, 0 <=k <= 1000000000),接下来的 1行,包含 n个数字表示排列 A,其中等于0的项表示看不清的位置(不超过 10个)。
输出描述:
输出一行表示合法的排列数目。
输入例子:
5 5
4 0 0 2 0
输出例子:
2
思路:先算出哪些元素是被模糊的了,用num_2存储起来,然后对于num_2进行全排列加入原数组中计算其顺序对是否等于k,若等于k,计数count加1。最后输出count。
c++代码:
#include<iostream> #include<vector> #include<algorithm> using namespace std; int cal(vector<int> a){ //计算a中顺序对的个数 int len=a.size(); int i,j; int count=0; for(i=0;i<len;i++){ for(j=i+1;j<len;j++){ if(a[j]>a[i]){ count++; } } }//for return count; } int main(){ int n,k; //长度为n,牛牛记得的顺序对对数为k对 while(cin>>n>>k){ int count=0; vector<int> a; //存原始的元素 vector<int> flag_1; //存不为0的元素下标 vector<int> flag_2; //存为0的元素下标 vector<int> num_1; //存不为0的元素值 vector<int> num_2; //存为0的元素值实际是哪些 int i,j; int tmp; for(i=0;i<n;i++){ cin>>tmp; a.push_back(tmp); if(tmp == 0){ flag_2.push_back(i); }else{ flag_1.push_back(i); num_1.push_back(tmp); } } for(i=1;i<=n;i++){ if(find(num_1.begin(), num_1.end(), i) == num_1.end()){ num_2.push_back(i); } } //对所有num_2中元素进行全排列 do{ vector<int> b = a; //讲num_2的元素按顺序放入b中 //flag_2的元素个数和num_2的元素个数相等 int len= (int) flag_2.size(); for(i=0;i<len;i++){ b[flag_2[i]] = num_2[i]; } //计算b的顺序对个数 if(cal(b) == k){ count++; } }while(next_permutation(num_2.begin(), num_2.end())); cout<<count<<endl; }//while return 0; }