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

发表于 分类于 阅读次数： 本文字数： 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
5
6
7
8
9
输入：
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\)以内一共有\(\lfloor n/a\rfloor\)个数是\(a\)的倍数，那么不考虑重复计算的话，这个问题的答案为\(\lfloor n/a\rfloor+\lfloor n/b\rfloor+\lfloor n/c\rfloor\)。一些数如果既是\(a\)的倍数，又是\(b\)的倍数，那么它是\(\text{lcm}(a,b)\)的倍数，其中\(\text{lcm}\)是最小公倍数，我们需要将这些算重复的减回去。但是如果一个数同时是\(a,b,c\)的倍数，那么这些数也被重复减去了，需要加回来。因此，这道题使用容斥原理后，其答案为：

\[\lfloor n/a\rfloor+\lfloor n/b\rfloor+\lfloor n/c\rfloor-\lfloor n/\text{lcm}(a,b)\rfloor-\lfloor n/\text{lcm}(b,c)\rfloor-\lfloor n/\text{lcm}(c,a)\rfloor+\lfloor n/\text{lcm}(a,b,c)\rfloor\]

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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\le k\le n\le 10^5\)

输出

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

样例

1
2
3
4
5
6
7
8
输入：
10 3

输出：
6

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

解答

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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\)。

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

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入：
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\)的强连通分量后生成，那么只会有两种情况：

  1. \(i_a,i_b\)相互不可达，此时选择哪一个决策都没有问题。
  2. \(i_b\)可达\(i_a\)，这时只需要选择\(i_a\)就不会产生任何问题。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 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;
}
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝