滴滴秋招 2023.09.08 编程题目与题解

发表于 2023-09-08 更新于 2023-09-12 分类于笔试阅读次数：本文字数： 1.5k 阅读时长 ≈ 1 分钟

1、糖果工厂

糖果工厂可以生产\(n\)种不同的糖果，这些糖果的编号分别为\(1\)到\(n\)，每一天工厂可以生产\(c_i\)个编号为\(i\)的糖果。

今天工厂接到了一个订单，需求是\(a\)包糖果，且每包糖果必须是同一种类的，每包数量不能少于\(b\)个。假设糖果工厂在无存货的情况下，至少需要多少天才能完成。

输入

第一行是三个正整数\(n,a,b\)，分别代表工厂可以生产的糖果种类数，订单的需求是\(a\)包糖果，每包不少于\(b\)个。

第二行是\(n\)个正整数\(c_1,c_2,\dots,c_n\)，其中第\(i\)个数\(c_i\)表示工厂每天能生产的编号为\(i\)的糖果的数量。

对所有的数据保证：\(1\le n\le 100000,1\le a,b\le 10^7,1\le c_i\le 10000\)。

输出

一行一个正整数，表示完成订单所需的最少天数。

样例

输入：
3 10 20
7 9 6

输出：
10

解答

这道题不难想到使用二分进行来进行处理。

假设现在需要判断\(d\)天能不能完成糖果的生产，那么\(d\)天我们能够生产\(\displaystyle{s=\sum_{i=1}^n\left\lfloor\dfrac{d\cdot c_i}{b}\right\rfloor}\)包完整的糖果，最终判断是否满足\(s\ge a\)即可。

代码

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

const int N=100004;
int c[N],n;
ll a,b;

bool ok(ll d){
    ll k=0;
    for(int i=1;i<=n&&k<a;i++){
        k+=d*c[i]/b;
    }
    return k>=a;
}
int main(){
    scanf("%d %lld %lld",&n,&a,&b);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    ll l=1,r=a*b;
    while(l<r){
        ll mid=(l+r)>>1;
        if(ok(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
}

2、冲突

现在有\(n\)个由大写英文字符组成的字符串，且这些字符串不会互相包含，也不会相等。现在想知道有哪些字符串满足如下条件。设满足条件的字符串为\(S\)，存在其他的两个字符串拼接在一起后，能通过去除一个非空前缀和一个非空后缀变为字符串\(S\)。这两个用于拼接的字符串可以是同一个，也可以为\(S\)。

输入

第一行一个正整数\(n\)，表示字符串的个数。

接下来\(n\)行，每行一个由大写英文字符组成的字符串。

对于所有数据，\(1\le n\le 5000\)，字符串长度\(\le 20\)。

输出

第一行输出一个正整数\(m\)，表示符合条件的字符串数量。

接下来输出\(m\)行，每行一个由大写英文字符组成的字符串，表示这个字符串符合条件。按照字典序升序输出。

样例

输入：
10
KPZOKNSTGLUNPPDKPFFW
NDPKU
KPFFWN
CCHXNNY
GWSGZ
NNYCCHX
FMVKSOHOPGZWG
SGZNNYCC
PKUFMVKSOHOPG
CCSGZN


输出：
6
CCHXNNY
CCSGZN
KPFFWN
NNYCCHX
PKUFMVKSOHOPG
SGZNNYCC

解答

本题考虑使用字符串哈希值进行解决。在这里，一个长度为\(m\)的字符串\(t\)的哈希值为\(\displaystyle{H(t)=\left(\sum_{i=1}^m t_i\cdot p^{m-i}\right)\bmod M}\)，其中\(p=131,M=2^{64}\)。

因此，对于输入的所有字符串\(t\)，假设其长度为\(m\)，我们将字符串\(t\)的所有真前缀（即不包含\(t\)自身的前缀）的哈希值全部保存起来，其中，长度为\(i(i<m)\)的前缀的哈希值保存在集合\(R_i\)中；类似的，我们也需要将所有真后缀（即不包含\(t\)自身的后缀）的哈希值全部保存起来，其中，长度为\(i(i<m)\)的后缀的哈希值保存在集合\(L_i\)中。

接下来，我们判断字符串\(t\)是否需要打印，其长度为\(m\)。判断过程非常简单，对于\(\forall i\in[1,m)\)，判断\(H(t[1:i])\in L_i\land H(t[i+1:m])\in R_{m-i}\)是否成立即可。如果成立，那么意味着存在一个字符串的真后缀是\(t[1:i]\)，并且存在另一个字符串的真前缀是\(t[i+1:m]\)，因此字符串\(t\)是需要输出的。

最终，使用哈希值就可以在\(\displaystyle{O\left(\sum_{t\in S}|t|\right)}\)的时间内完成本题，而和字符串的个数本身没有关系。

代码

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;

const int N=100004;
vector<ull>l[N],r[N];
unordered_set<ull>st_l[24],st_r[24];
ull pw[141],b=131;
string s[N];
int main(){
    pw[0]=1;
    for(int i=1;i<=23;i++)
        pw[i]=pw[i-1]*b;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
        int m=s[i].size();
        l[i].resize(m+1);
        r[i].resize(m+1);
        for(int j=1;j<=m;j++){
            l[i][j]=l[i][j-1]*b+s[i][j-1];
            r[i][j]=r[i][j-1]+pw[j-1]*s[i][m-j];
            if(j<m){
                st_r[j].insert(l[i][j]);
                st_l[j].insert(r[i][j]);
            }
        }
    }
    vector<string>v;
    for(int i=0;i<n;i++){
        bool ok=0;
        int m=s[i].size();
        for(int j=1;j<m&&!ok;j++){
            if(st_l[j].count(l[i][j])&&st_r[m-j].count(r[i][m-j])) ok=1;
        }
        if(ok) v.push_back(s[i]);
    }
    sort(v.begin(),v.end());
    cout<<v.size()<<"\n";
    for(string &s:v){
        cout<<s<<"\n";
    }
}