携程23年5月4日后端笔试（1，2，4题）

第一题：关于字符串处理（如果是'a'-'z'向后移动一个（'z'变为'a'），如果是'A'-'Z'向前移动一个（'A'变为'Z'））

比较简单，而且代码我忘记保存了

第二题：N个字符串，每个字符串有一个权重，求两个字符串的最大权重之和，要求这两个字符串是一个是另一个的子串。

考的手撕KMP

#include <iostream>
using namespace std;

const int N = 15;
const int M = 110;
string strs[M];
int values[M];
int m;

bool KMP_Func(string s, string p)
{
    // 判断p是否为s的子串
    int n = s.size();
    int m = p.size();

    if (n < m)
        return false;
    else if (n == m)
        return s == p;
    else
    {
        int ne[N] = {};
        ne[0] = -1;
        for (int i = 1, j = -1; i < m; i++)
        {
            while (j != -1 && p[i] != p[j + 1])
                j = ne[j];
            if (p[j + 1] == p[i])
                ne[i] = ++j;
            else
                ne[i] = -1;
        }

        for (int i = 0, j = -1; i < n; i++)
        {
            while (j != -1 && s[i] != p[j + 1])
                j = ne[j];
            if (s[i] == p[j + 1])
            {
                j++;
                if (j == m - 1)
                    return true;
            }
        }

        return false;
    }
}

int main()
{
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
        cin >> strs[i] >> values[i];

    int ans = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (i != j && KMP_Func(strs[i], strs[j]))
                ans = max(ans, values[i] + values[j]);

    if (ans)
        printf("%d", ans);
    else
        printf("-1");
    return 0;
}

第三题：没写....

// 仅由0 1 2组成的字符串，其中一些字符被替换成了？
// 满足以下性质：
// 1. 相邻字符串不相等
// 2. 所有字符串长度为3的连续子串。三进制数为偶数

第四题：

1号城市到n号城市，城市之间有道路连接，每条道路有距离、最大承重

求总路程不超过h的前提下，1到n的最大承重为多少？

第一行三个正整数n, m, h城市数量、道路数量、路程限制

接下来m行 u, v, w, d 表示uv两个城市之间有一条长d限重w的道路

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

结果为6

考试的时候没写出来，之后自己回去写了个暴力做法，能过样例，但我估计不能全通过

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int al[N], e[N], ne[N], weight[N], dist[N], idx;
bool visit[N];
int n, m, h;
int cur_distance;
int ans;

void add(int u, int v, int w, int d)
{
    e[idx] = v;
    ne[idx] = al[u];
    weight[idx] = w;
    dist[idx] = d;
    al[u] = idx++;
}

void dfs(int x)
{
    if (cur_distance > h)
        return;

    if (x == n)
    {
        int t = 1e9;
        for (int i = 1; i <= n; i++)
            if (visit[i])
                t = min(t, weight[i]);
        ans = max(ans, t);
        return;
    }

    for (int i = al[x]; i != -1; i = ne[i])
    {
        int p = e[i];
        if (!visit[p])
        {
            visit[p] = true;
            cur_distance += dist[p];
            dfs(p);
            cur_distance -= dist[p];
            visit[p] = false;
        }
    }
}

int main()
{
    memset(al, -1, sizeof al);
    scanf("%d%d%d", &n, &m, &h);
    for (int i = 0; i < m; i++)
    {
        int u, v, w, d;
        scanf("%d%d%d%d", &u, &v, &w, &d);
        add(u, v, w, d);
        add(v, u, w, d);
    }

    dfs(1);
    printf("%d", ans);

    return 0;
}