本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网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;
}