小红书秋招 2023.08.19 编程题题目与题解

发表于 2023-08-19 分类于笔试阅读次数： 506 本文字数： 2.6k 阅读时长 ≈ 2 分钟

1、小红背单词

小红每天都要背单词，然后她会把每天记住了多少单词记录下来，并在小红书上打卡。

当小红背单词时，如果她已经记住了 $i$ 个单词，且背了一个没有记住的新单词 $i + 1$ 次，则她就会记住这个新单词。

例如，当她按顺序背 ["you", "thank", "thank"] 时，她第一次背单词 "you" 时她就能记住 "you"。而由于她已经记住了一个单词，所以需要背两次 "thank" 才能记住 "thank"。

现在你知道了小红背单词的顺序，请你求出小红今天记住了多少个单词。

输入

第一行一个整数 $n (1 \leq n \leq 10000)$

接下来 $n$ 行，每行一个字符串，保证每个字符串长度不超过 $10$ 。

输出

输出一个整数，表示她记住了多少个单词。

样例

输入：
5
you
thank
queue
queue
thank

输出：
2

提示：
小红先记住了单词"you"，又因为背了两次"queue"，于是记住了单词"queue"。
由于已经记住了两个单词，所以背两次"thank"还不能让小红记住。、

解答

直接按照题意模拟即可。按顺序读入每个单词 $s$ ，统计一下它当前出现次数是否达到了所需要的统计次数 $c n t + 1$ 即可。如果达到了，那么说明这个单词被记住了，并且将 $c n t$ 加上 $1$ 。

代码

# include <bits/stdc++.h>
using namespace std;

unordered_map<string,int>mp;
int main(){
    int n;
    string s;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        if(++mp[s]==cnt+1){
            ++cnt;
            mp[s]=-1e9;
        }
    }
    cout<<cnt<<endl;
}

2、小红的回文串

小红有一个字符串，她可以进行以下操作:

拆分。把'w' 拆成 $2$ 个，'m' 拆成 $2$ 个'n'。
轴对称。把'b' 轴对称成'd'，'p' 轴对称成'q'，反之亦然。
翻转。把'b' 翻转成'q'，把'd' 翻转成'p'，把'n' 翻转成'u'，反之亦然。

经过若干次操作后，小红想知道这个字符串能不能变成回文串。

输入

第一行输入一个整数 $T (1 \leq T \leq 10^{4})$ 表示询问次数。

接下来 $T$ 行，每行输入一个字符串表示询问。

所有字符串长度之和不超过 $10^{5}$ 。

输出

输出 $T$ 行，每行输出 "YES" 或 "NO" 表示是否可以变成回文串。

样例

输入：
5
wovv
bod
pdd
moom
lalalai

输出：
YES
YES
YES
YES
NO

提示：
第一个字符串可以变成: vvovv (将第一个w拆成两个v)
第二个字符串可以变成: bob、dod、pop或qoq
第三个字符串可以变成: bdb
第四个字符串本来就是回文的，不用进行操作。

解答

首先是将这个单词能拆则拆，这是为了避免 "muu" 这种情况的错误判断。

接下来考虑'bdpq' 这 $4$ 个字母，由于它们是可以通过有限次操作相互转换的，因此可以用同一个字符来表示（这里使用了'0'）。类似的，'nu' 这 $2$ 个字母也是可以相互转换的，因此也可以用同一个字符来表示（这里使用了'1'）。

最终判断处理完的字符串是否为一个回文字符串即可。

代码

T = int(input())
for _ in range(T):
    s = input()
    s = s.replace('w', 'vv').replace('m', 'nn')
    s = s.replace('b', '0').replace('p', '0').replace('d', '0').replace('q', '0')
    s = s.replace('u', '1').replace('n', '1')
    print("YES" if s == s[::-1] else "NO")

3、小红的旅游攻略

小红是小红书的一个博主，她有很多的粉丝，有一些粉丝想让小红出一篇上尾市的旅游攻略。

上尾名有 $n$ 个景点，有 $m$ 条路线，每个景点的攻略价值是 $a$ ，要花费 $h$ 时间浏览，不同景点之间的的交通时间为 $w$ 。小红最多会选择 $3$ 个相邻的景点，然后按顺序将景点写进攻略，她需要保证每个景点的浏览时间加上景点之间的交通时间总和不超过 $k$ ，并且使得攻略的价值尽可能大，即景点的总价值尽可能大。

求小红的攻略的景大价值。

输入

第一行输入三个整数 $n, m (1 \leq n, m \leq 10^{5}), k (1 \leq k \leq 10^{9})$ ，含义如题目描述所示。

第二行输入 $n$ 个整数表示数组 $a (1 \leq a_{i} \leq 10^{9})$ 。

第三行输入 $n$ 个整数表示数组 $h (1 \leq h_{i} \leq 10^{9})$ 。

接下来 $m$ 行，每行输入三个整数 $u, v (1 \leq u, v \leq n), w (1 \leq w \leq 10^{9})$ 表示点 $u, v$ 之间的交通时间为 $w$ 。

输出

输出一个整教表示答案。

样例

输入：
4 4 8
4 3 2 1
1 2 3 4
1 2 1
2 3 1
2 4 1
3 4 1

输出：
9

提示：
路线3-2-1的价值为:4+3+2=9，耗费的时间为1+1+2+1+3=8
路线1-2-3也是一样的，都是最优方案。
可以证明，答案最大不超过9。

解答

这一道题有点复杂，它似乎考了图论，但好像又没考。我们分三种情况讨论这个图 $G = (V, E)$ 。

第一种情况是只有一个景点，这意味着如果 $h_{u} \leq k$ ，那么 $a_{u}$ 则是一个候选解。

第二种情况是只有两个景点，这意味着对于 $(u, v) \in E$ ，如果 $w (u, v) + h_{u} + h_{v} \leq k$ ，那么 $a_{u} + a_{v}$ 则是一个候选解。

对于第三种情况，过程可能有些复杂。不过不难想到的是，我们可以枚举这条长度为 $3$ 的路径的中间点 $x$ ，然后每次枚举它的两个不同邻居 $(u, v)$ ，并判断 $w (u, x) + w (v, x) + h_{u} + h_{v} + h_{x} \leq k$ 是否满足即可，如果满足，那么就有答案 $a_{u} + a_{v} + a_{x}$ 。

然而，上面的枚举方式是 $O (n^{2})$ 的，会导致超时，其中 $n$ 是 $x$ 的邻居个数。

接下来我们只考虑 $x$ 的所有邻居对情况。可以看到，我们可以将判断时间长度的式子可以写成 $(w (u, x) + h_{u}) + (w (v, x) + h_{v}) \leq k - h_{x}$ 。如果令 $b_{u} = w (u, x) + h_{u}$ ，那么式子就可以简化成 $b_{u} + b_{v} \leq k - h_{x}$ ，注意不等式的右侧是一个常数。

我们可以在 $O (n)$ 时间内预处理出 $b$ 数组，问题可以进一步抽象为：

给定一个长度为 $n$ 的数组 $v$ ，数组的每个元素有两个属性 $a, b$ ，我们需要找到一对下标 $(l, r)$ ，满足 $l < r$ ，使得 $v [l] . b + v [r] . b \leq c$ ，并且使 $v [l] . a + v [r] . a$ 的值最大化。

其中 $c = k - h_{u}$ 。在这个问题中，每个节点都对应了其中一个下标。

考虑使用双指针法解决这个问题。首先对数组 $v$ 按照 $b$ 属性进行排序。对于 $l = 0, 1, 2, \dots, n - 1$ ，我们需要找到一个最大的 $r$ 使得 $v [l] . b + v [r] . b \leq c$ ，这个通过双指针可以解决。如果找到时发现 $r \leq l$ ，那么进行退出。这说明，答案 $v [l] . a + {max}_{i = l + 1}^{r} {v [i] . a} + a_{x}$ 是其中一个最终解。但是由于涉及了多个独立询问求解子数组 $v [l + 1 : r]$ 中 $a$ 的最大值，直接暴力求解这个值仍然是 $O (n^{2})$ 的时间复杂度。

但是我们可以发现，随着 $l$ 上升， $r$ 必定是下降的。也就是说，这些询问是一个接一个嵌套的。如果有 $o$ 个询问，那么必定满足 $l_{0} < l_{1} < \dots < l_{o - 1}, r_{0} \geq r_{1} \geq \dots \geq r_{o - 1}$ 。我们可以再次使用双指针法，先求出子数组 $v [l_{o - 1} + 1 : r_{o - 1}]$ 中 $a$ 的最大值，再求出子数组 $v [l_{o - 2} + 1 : r_{o - 2}]$ 中 $a$ 的最大值…… 最终求出 $v [l_{0} + 1 : r_{0}]$ 中 $a$ 的最大值，最终回到原问题进行求解即可。

代码

# include <bits/stdc++.h>
# define X first
# define Y second
# define pi pair<ll,ll>
using namespace std;
typedef long long ll;

const int N=100004;
vector<pi>g[N];
int n,m;
ll k,a[N],h[N];
vector<int>que;
int main(){
    ll ans=0;
    scanf("%d %d %lld",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&h[i]);
        if(h[i]<=k){
            // 只有一个景点的路线。
            ans=max(ans,a[i]);
        }
    }
    int u,v;ll w;
    for(int i=1;i<=m;i++){
        scanf("%d %d %lld",&u,&v,&w);
        g[u].push_back(pi(w+h[v],a[v]));
        g[v].push_back(pi(w+h[u],a[u]));
        if(h[u]+h[v]+w<=k){
            // 只有两个景点的路线。
            ans=max(ans,a[u]+a[v]);
        }
    }
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
        vector<pi>&v=g[i];
        int m=v.size();
        if(m<2) continue;
        que.clear();
        for(int l=0,r=m-1;l<r;l++){
            for(;l<r&&v[l].X+v[r].X+h[i]>k;r--);
            if(l==r) break;
            que.push_back(r);
        }
        if(que.empty()) continue;
        int o=que.size();
        ll tp=0;
        for(int l=o-1,r=o;l>=0;l--){
            int pr=que[l];
            for(;r<=pr;r++){
                tp=max(tp,v[r].Y);
            }
            // 三个景点的路线。
            ans=max(ans,v[l].Y+tp+a[i]);
            tp=max(tp,v[l].Y);
        }
    }
    printf("%lld\n",ans);
}