牛客网OJ题解--20210204

牛牛的星际旅行

https://ac.nowcoder.com/acm/problem/21783

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC21783-牛牛的星际旅行

题目链接

https://ac.nowcoder.com/acm/problem/21783

题目描述

在一个遥远的星球上，每周有N天，牛牛去了这个星球旅游，他恰好只带了N件不同的衣服，编号为1到N。每一天他会穿其中的某一件衣服，一周之内不能穿同一件衣服两次，而且假如某件衣服是在第x天穿的，那么下一次最早能穿这件衣服的时期为x+N-1。现在已知牛牛在这个星球第一周穿衣服的顺序以及最后一周穿衣服的顺序，计算牛牛在这个星球上最少居住了几周。

第一行输入一个整数N
第二行输入N个整数表示第一周穿衣服的排列
第三行输入N个整数表示最后一周穿衣服的排列（保证2 ≤ N ≤ 2500）

测试样例

样例1

输入

4
1 2 3 4
4 3 2 1

输出

样例2

输入

4
1 2 3 4
1 2 3 4

输出

样例3

输入

8
8 4 5 1 7 6 2 3
2 4 6 8 1 3 5 7

输出

解题思路

过程太复杂，很明显不能逐一分析，我们这里以一件衣服的视角来分析，假设对于一件衣服x他在周5穿过，那么他下一次最早在周4串，如果下一周真的周4穿了，那么下下周就是最早周3穿，所以我们可以推断出如果最后一周x所在的顺序靠后了，那么就不用了关心他了，他可以随时换到后面去，但是如果他在最后一周顺序更靠前了，那么我们需要将它向前移，并且每周只能向前移一天，所以我们就逐一暴力查找后来跑到顺序更靠前的衣服，然后相减求出最少（即每次都往前一天穿）需要多少周，最后找出最大值再加1即可输出。

解题代码

#include <bits/stdc++.h>
using namespace std;
#define maxn 3000
int a[maxn], b[maxn], c[maxn];

int main()
{
    int n;
    cin >> n;
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        //寻找后来跑到前面穿的衣服，后面的不关心
        {
            if (a[i] == b[j])
            {
                //对于后来衣服穿在更前面的情况，那么至少需要i-j周才可以到
                c[i] = i - j;
                break;
            }
        }
    }
    int r = -1000000;
    for (int i = 1; i <= n; i++)
    {
        if (c[i] > r)
        {
            r = c[i];
        }
    }
    //注意要+1
    cout << r + 1 << endl;
    system("pause");
    return 0;
}

NC21796-最长公共包含串

题目链接

https://ac.nowcoder.com/acm/problem/21796

题目描述

给你四个字符串，你需要求出包含这四个字符串作为子串的最短字符串长度，并且字符集为'a'-'z'每个字符串长度在10以内。

测试样例

样例1

输入

abc
ab
bc
b

输出

样例2

输入

a
bc
def
ghij

输出

样例3

输入

thereare
arelotsc
lotsof
ofcases

输出

解题思路

因为必定4个串，也就是说只能用4!=24种排列情况，我们就暴力枚举每一种情况从最开始的第一个串注意向后拼接，所以只需对比前串的后缀和后串的前缀的公共部分，然后对于公共部分不拼接，只拼接非公共串部分，最后拼接完再统计这个拼接串的长度，最终24个串中取最少的串长度输出。

解题代码

//参考了大佬的代码，这里给出几个知识点：
// rfind从字符串a末尾开始寻找包含字符串b的第一个位置，没有就返还::npos
// substr(i,j)截取字符串c的起始位置i到结束位置j的部分子串
#include <bits/stdc++.h>
using namespace std;
string arr[5];
void work(string &a, string b)
{
    if (a.find(b) != string::npos)
        return; //a中包含b,不用拼接了
    for (int i = b.size() - 1; i >= 0; i--)
    {
        if (a.rfind(b.substr(0, i)) != string::npos && a.rfind(b.substr(0, i)) == a.size() - i) //a的后缀等于b的前缀
        {
            a += b.substr(i, b.size() - i); //a加上b前缀之外的部分
            break;
        }
    }
}

int main()
{
    for (int i = 0; i < 4; i++)
        cin >> arr[i];
    int r = 60; 
    //随便设一个必定大于最短公共串长度的数字
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                for (int l = 0; l < 4; l++)
                {
                    if (i == j || i == k || i == l || j == k || j == l || k == l)
                    {
                        //如果是这种情况，那么没有选出4个不同的直接跳过字符串
                        continue;
                    }
                    //应该一共会有4！个情况
                    string tmp = arr[i];
                    //tmp分别和另外三个比较寻找，tmp是最开始的串，其他的拼到后面
                    work(tmp, arr[j]);
                    work(tmp, arr[k]);
                    work(tmp, arr[l]);           //暴力，把每种组合都试一遍//题目说了只有4个串，其实也可以写4个循环
                    r = min(r, (int)tmp.size()); //必须要把长度化为整型
                }
            }
        }
    }
    cout << r << endl;
    system("pause");
    return 0;
}