牛客网OJ题解--20210226
凌波微步
https://ac.nowcoder.com/acm/problem/14346
本系列记录翀翀😐痛苦的刷题日志,所有题目均来自于牛客网OJ题目,坚持刷题谈起来容易做起来难,希望我可以坚持下去,这里仍然分享一段励志文案:每个人都有梦想,然而有些人把梦想变成了现实,有些人的梦想依旧是梦想,只因为他们为梦想付出的努力程度不一样,他们坚持的时间不一样,最终才有这样的结果。
请在这里输入引用内容
NC14346-凌波微步
题目链接
https://ac.nowcoder.com/acm/problem/14346
题目描述
小Z的体型实在是太胖了,每次和小D一起出门都跟不上小D的脚步,这让小Z很气馁,于是小Z跋山涉水,仿名山,遍古迹,终于找到了逍遥派。掌门看小Z求师虔诚,决定传小Z一套《凌波微步》。这种腿法可以无视距离的行进,但缺点是只能走向高处,否则强行发功极易走火入魔。一天,练习《林波微步》的小Z来到一处练武场,这里从左到右,共有n个木桩,这些木桩有高有低,在这里小Z勤奋的练习着凌波微步,你知道小Z在这处练武场最多能练习多少次么?
本题有T组数据。
对于每组数据第一行有一个正整数n表示有多少个木桩。
第二行有n个数 a_i,表示木桩与水平地面的相对高度。
1≤T≤10,1≤n≤100000,1≤a_i≤1000000000
测试样例
输入
2 6 1 2 3 4 5 6 5 1 3 5 3 6
输出
6 4
说明
第一组: 1->2->3->4->5->6 共6步 第二组: 1->3->5->6 共4步
解题思路
注意题干只是要求从低到高走,没说是从左往右走,所以每次小Z都跳当前高木桩中的最低木桩即可。所以只需要将木桩高度从低到高排序,然后去掉重复高度的木桩,剩余的木桩数量就是可以走的最多次数。
解题代码
#include <bits/stdc++.h> using namespace std; int a[100005]; int main() { int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } //木桩从小到大排序 sort(a + 1, a + n + 1); int ans = 0, tmp = 0; // for (int i = 1; i <= n; i++) // { // //记录增大木桩的数量 // if (a[i] > tmp) // { // tmp = a[i]; // ans++; // } // } //实际上也可以使用数组去重更简单,只需要把相同高度的木桩去重 ans = unique(a + 1, a + n + 1) - (a+1); cout << ans << endl; } system("pause"); return 0; }
NC14347-珠宝店
题目链接
https://ac.nowcoder.com/acm/problem/14347
题目描述
小Z向女神告白成功,成功脱单,为了庆祝,小Z决定送女神一个礼物。在珠宝店,小Z终于发现一种既便宜又大气的手链。手链的价格是看手链上的宝石决定的,每一种宝石的价值不一样。具体规则如下:宝石A的价值是1、宝石B的价值是2、宝石C的价值是3·····宝石Z的价值是26。为了防止被销售员虚报价格,小Z决定请你帮忙计算一下手链的价值。
本题有T组数据。对于每组数据只有一行。1≤T≤20,1≤手链长度≤100000。
测试样例
输入
2 ABCD LOVELOVE
输出
10 108
解题思路
水题,就是字符ASCII码均减'A'再加一即可。然后累加求总价值即可。
解题代码
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while (n--) { string s; cin >> s; int ans = 0; for (int i = 0; i < s.size(); i++) { ans += s[i] - 'A' + 1; } cout << ans << endl; } system("pause"); return 0; }
NC14345-布置会场(1)
题目链接
https://ac.nowcoder.com/acm/problem/14345
题目描述
今天是Tabris和mengxiang000来到幼儿园的第3天,mengxiang000接到了一个布置会场的任务。他需要将贵宾观众席的椅子排成一排,一共需要N个。幼儿园只有两种椅子,所以他也只能使用两种椅子。(A类型和B类型)并且假设每种椅子的数量都是无限的。而其如果想要摆置一个B类型的椅子,对应就需要必须有连续两个一起布置。换句话说,就是如果出现了B类型的椅子,其必须且只有两个连着B类型的椅子。mengxiang000突然想知道对应N个椅子排成一列,他能够有多少种布置的方式。
本题包含多组输入第一行输入一个整数t,表示测试数据的组数
每组测试数据包含一行,输入一个整数N,表示一共需要摆放的椅子数量
t<=30,1<=N<=30。
测试样例
输入
2 2 4
输出
2 5
解题思路
一开始想的是直接对于每一种情况进行计算,使用排列组合的方法写,但是实现很难,并且时间复杂度高,会超时。后来发现枚举以下n=2,3,4的情况不难看出就是斐波那契数列的dp,所以问题迎刃而解。
解题代码
#include <bits/stdc++.h> using namespace std; int t, n, dp[50]; void init() { dp[0] = 0, dp[1] = 1; for (int i = 2; i < 50; i++) dp[i] += dp[i - 1] + dp[i - 2]; } int main(void) { init(); cin >> t; while (t--) { cin >> n; cout << dp[n + 1] << endl; } system("pause"); return 0; }