百度秋招 2023.10.17 编程题目与题解

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

1、小红的数字

小红想知道在区间 $[l, r]$ 内，有多少个数是 $a$ 的倍数，或者是 $b$ 的倍数，或者是 $c$ 的倍数。

输入

第一行输入一个整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行输入五个整数 $a, b, c$ 和 $l, r$ ，表示 $a, b, c$ 和 $l, r$ 的值。

$1 \leq T \leq 10^{5}$
$1 \leq a, b, c \leq 10^{9}$
$1 \leq l \leq r \leq 10^{9}$

输出

输出 $T$ 行，每行输出一个整数，表示答案。

样例

输入：
1
2 3 4 1 10

输出：
7

提示：
[1, 10] 内有 2, 3, 4, 6, 8, 9, 10 这七个数是 2 的倍数，或者是 3 的倍数，或者是 4 的倍数。

解答

为了方便，我们先求出 $r$ 以内满足条件的数有多少个，再求出 $l - 1$ 以内满足条件的数有多少个，再用前者减去后者就可以得到原问题的答案。

因此，接下来问题转化成了求 $n$ 以内满足条件的数有多少个。这个问题 Leetcode 1201 的子问题。

我们可以使用容斥原理进行求解。不考虑其它， $n$ 以内一共有 $⌊ n / a ⌋$ 个数是 $a$ 的倍数，那么不考虑重复计算的话，这个问题的答案为 $⌊ n / a ⌋ + ⌊ n / b ⌋ + ⌊ n / c ⌋$ 。一些数如果既是 $a$ 的倍数，又是 $b$ 的倍数，那么它是 $lcm (a, b)$ 的倍数，其中 $lcm$ 是最小公倍数，我们需要将这些算重复的减回去。但是如果一个数同时是 $a, b, c$ 的倍数，那么这些数也被重复减去了，需要加回来。因此，这道题使用容斥原理后，其答案为：

$⌊ n / a ⌋ + ⌊ n / b ⌋ + ⌊ n / c ⌋ - ⌊ n / lcm (a, b) ⌋ - ⌊ n / lcm (b, c) ⌋ - ⌊ n / lcm (c, a) ⌋ + ⌊ n / lcm (a, b, c) ⌋$

求解 $lcm$ 只需要使用欧几里得算法即可，另外由于最小公倍数满足结合性，因此可以通过递推的方式求解最小公倍数。

代码

from math import lcm


def solve(a, b, c, n):
    z = [a, b, c]
    ans = 0
    for s in range(1, 8):
        l = lcm(*[z[i] for i in range(3) if s >> i & 1])
        if bin(s).count('1') & 1:
            ans += n // l
        else:
            ans -= n // l
    return ans


T = int(input())
for _ in range(T):
    a, b, c, l, r = map(int, input().split())
    print(solve(a, b, c, r) - solve(a, b, c, l - 1))

2、小红的连续自然数乘积

小红想在 $[1, n]$ 取一些连续的正整数，使得它们的乘积最多有 $k$ 个不同的素因子。小红想知道，自己最多可以取多少个正整数？

所谓连续，指取的这些正整数不能重复，且相邻两个的差为 $1$ 。例如 $[2, 3, 4, 5], [5, 6, 7]$ 都是连续的取数。

所谓素因子：对于一个数 $n$ 来说，将它的因子拆到若干个素数相乘，这些素数被称为 $n$ 的素因子。

输入

两个正整数 $n$ 和 $k$ ，用空格隔开。

$1 \leq k \leq n \leq 10^{5}$

输出

一个整数，代表小红可以取的连续正整数最大值。

样例

输入：
10 3

输出：
6

提示：
选择1到6，乘积是720，有3个不同的素因子（2，3，5）。

解答

我们首先可以使用筛法，将每个数的所有质因子求出来。

先以某个数 $l$ 为起点，逐渐乘上 $l + 1, l + 2, \dots,$ 可以发现它的质因子个数不断增长，最终质因子个数超过 $k$ 后，这时这个数不再是我们所求的值。假设乘上某个数 $r$ 后，这个数立刻不符合要求，那么这时 $r$ 是这个极限，这时我们一共取到了 $r - l$ 个数。随着起点右移，这个极限点也是非递减的。

因此，我们可以使用双指针法完成这个过程，用一个数组来维护所有质因数出现的情况，以及用一个变量维护质因子的数量即可。

代码

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

const int N=100004;

vector<int>d[N];
int cnt[N],tot=0;
void add(int x,int o){
    if(o==1){
        if(++cnt[x]==1) ++tot;
    }
    else{
        if(--cnt[x]==0) --tot;
    }
}
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=2;i<=n;i++){
        if(d[i].empty()){
            for(int j=i;j<=n;j+=i){
                d[j].push_back(i);
            }
        }
    }
    int ans=0;
    for(int l=1,r=1;l<=n;l++){
        for(;r<=n&&tot<=k;r++){
            for(int x:d[r]) add(x,1);
        }
        if(tot>k){
            --r;
            for(int x:d[r]) add(x,-1);
        }
        ans=max(ans,r-l);
        for(int x:d[l]) add(x,-1);
    }
    printf("%d\n",ans);
}

3、小红的字符串构造（easy）

小红拿到了两个长度为 $n$ 的字符串 $a$ 和 $b$ ，她希望你构造一个新的字符串 $c$ ，要求 $c$ 的每个字符 $c_{i}$ 是 $a_{i}$ 和 $b_{i}$ 二选一生成。

小红希望最终字符串 $c$ 的每一种字符都恰好出现了 $1$ 次。你能帮帮她吗？

输入

第一行输入一个正整数 $n$ ，代表两个字符串的长度。

第二行输入字符串 $a$ 。

第三行输入字符串 $b$ 。

$1 \leq n \leq 10^{5}$
字符串保证仅包含大写和小写字母。

输出

如果无解，请输出 $- 1$ 。

否则输出一个合法的字符串。有多解时输出任意即可。

样例

输入：
6
abcdef
fedcba

输出：
abdcef

提示：
输出fbdcea等字符串也是合法的。

输入：
3
abB
bBA

输出：
aBA

解答

可以发现，字符串的长度 $n$ 最多不会超过 $52$ ，因为字符串 $c$ 只有可能包含小写字母和大写字母。因此，当 $n > 52$ 时是无解的。

进行判断完后，可以发现这是一道明显的 2-SAT 问题，因为每个位置 $i$ 都有两种选择：要么选择 $a_{i}$ ，要么选择 $b_{i}$ 。不失一般性，假设存在一对 $(i, j)$ 使得 $a_{i} = b_{j}$ ，那么如果位置 $i$ 选择了 $a_{i}$ ，那么位置 $j$ 就必须选择 $a_{j}$ ，这对于其它情况类似。

也就是说，其中一个位置的选择会影响到另外一个位置的选择。我们为每个位置和每个选择作为一个节点，并且将上面的抉择关系建立成一个图 $G = (V, E)$ 。对于一对 $i, j (i \neq j)$ ，如果 $a_{i} = b_{j}$ ，并且位置 $i$ 已经选择来自 $a$ ，那么位置 $j$ 也必须来自 $a$ ，从而得到一条边 $(i_{a}, j_{a}) \in E$ 。

最终，对于同一个位置的两个选择，如果发现它们是相互依赖的，即如果位置 $i$ 选择了 $a$ ，那么位置 $i$ 就要选择 $b$ ，并且反之亦然（也就是说 $i_{a}, j_{a}$ 相互可达），那么这很明显是矛盾的，无解。至于具体实现，我们可以使用 tarjan 算法求出每个图的强连通分量，并判断是否存在一个位置的两个选择在同一强连通分类即可。

接下来考虑构造一个有效方案。我们使用 tarjan 算法求出了原图中每个图的强连通分量，并为它们进行编号。下面实现的 tarjan 算法中，它是自底向上进行编号的。假设选择 $i_{a}, i_{b}$ 所在强连通分量的编号为 $t_{i, a}, t_{i, b}$ 。不失一般性，假设 $t_{i, a} < t_{i, b}$ ，也就是说 $i_{a}$ 所在的强连通分量先生成， $i_{b}$ 的强连通分量后生成，那么只会有两种情况：

$i_{a}, i_{b}$ 相互不可达，此时选择哪一个决策都没有问题。
$i_{b}$ 可达 $i_{a}$ ，这时只需要选择 $i_{a}$ 就不会产生任何问题。

总而言之，基于这个 tarjan 算法实现的性质，我们只需要选择强连通分量编号比较小的选项即可。

代码

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

const int N=104;
string s[2];
char t[N];
int n;
vector<int>g[N];
int dfn[N],low[N],idx=0;
int col[N],c=0;
bool ins[N];
stack<int>st;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    st.push(u);ins[u]=1;
    for(int v:g[u]){
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++c;int x;
        do{
            x=st.top();st.pop();
            ins[x]=0;col[x]=c;
        }while(x!=u);
    }
}
string solve(){
    if(n>52) return "-1";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            if(s[0][i]==s[0][j]) g[i].push_back(j+n);
            if(s[0][i]==s[1][j]) g[i].push_back(j);
            if(s[1][i]==s[0][j]) g[i+n].push_back(j+n);
            if(s[1][i]==s[1][j]) g[i+n].push_back(j);
        }
    }

    for(int i=0;i<n+n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=0;i<n;i++){
        if(s[0][i]!=s[1][i]&&col[i]==col[n+i]) return "-1";
        if(s[0][i]==s[1][i]) t[i]=s[0][i];
        else t[i]=s[col[i]>col[n+i]][i];
    }
    return string(t,t+n);

}
int main(){
    cin>>n>>s[0]>>s[1];
    cout<<solve()<<endl;
}