腾讯 秋招 2023.09.15 编程题目与题解（算法岗）

发表于 分类于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 4 分钟

1、子序列计数

给定一个长度为\(n\)的数组，求有多少子序列满足：子序列中元素种类数\(=\)子序列长度。

由于答案可能很大，请输出答案取模\(998244353\)后的结果。

输入

第一行一个整数\(n,1\le n\le 10^5\)

第二行\(n\)个整数，\(a_1,a_2,\dots,a_n(1\le a_i \le 10^5)\)

输出

一行一个整数，表示答案。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入：
3
2 3 3

输出：
5

提示：
符合条件的子序列有（按照下标方式给出）
{1},{1,2},{1,3},{2},{3}

输入：
3
1 3 4

输出：
7

提示：
符合条件的子序列有（按照下标方式给出）
{1},{1,2},{1,2,3},{1,3},{2},{2,3},{3}

备注

子序列可以理解为从原数组中选择一些元素删掉（或者不删）并保持剩余元素的相对位置不变。

解答

这道题意味着求出\(a\)有多少个子序列，其元素各不相同。

由于元素各不相同，因此\(a\)中的每个数在子序列中最多出现一次。对于不同的数而言，其出现的情况都是独立的，因此按照乘法原理，我们可以给出答案为：

\[\prod_{x} (c(x,a)+1)-1\]

其中\(c(x,a)\)表示元素\(x\)在\(a\)出现的次数。上面的式子所表达的意思是：选择将\(x\)放进子序列一共有\(c(x,a)\)种方式，不将\(x\)放进子序列有\(1\)种方式，因此对\(x\)的处理情况有\(c(x,a)+1\)种。为了避免所有元素都没被放进子序列，最终答案还需要减去\(1\)，即一个空子序列的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
from collections import Counter

input()
c = Counter(list(map(int, input().split())))
mod = 998244353
ans = 1
for k, v in c.items():
    ans = ans * (v + 1) % mod
ans = (ans - 1) % mod
print(ans)

2、盲盲盒

最近盲盒活动非常火热，商家A和商家B打算进一步增加盲盒的“盲”，于是在各自的仓库，即仓库A和仓库B里面进行盲盒交换。

具体操作如下：

  1. 首先仓库A里面有\(k\)个普通盲盒以及\(1\)个超珍稀盲盒，仓库B里面有\(k+1\)个普通盲盒；

  2. 每次从两个仓库里面以均匀分布抽样出一个盲盒，并进行交换；经过\(n\)次盲盒交换之后，超珍稀盲盒仍然在仓库A的概率为\(p/q\) (最简分数)，那么\(p+q\)模\(10\)的数值是多少？

输入

第一行为测试组数\(T\)，接下来有\(T\)行数据，每行数据是交换次数\(n\)和盲盒数量\(k\)。

  • \(1<n<1000，1<T<20，1<k<100\)

输出

经过\(n\)次盲盒交换之后，超珍稀盲盒仍然在仓库A的概率为\(p/q\) (最简分数)，那么\(p+q\)模\(10\)的数值。

样例

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

输出：
1
6
9
9

备注

解答：若令\(X(n)\)表示在\(n\)次交换之后，仓库A中超珍稀盲盒的数量。那么\(X(n)\)的状态空间为\(0\)或者\(1\)，容易得到状态转移矩阵为\(\begin{bmatrix}\dfrac{k}{k+1}&\dfrac{1}{k+1}\\\dfrac{1}{k+1}&\dfrac{k}{k+1}\end{bmatrix}\)。令\(a=\dfrac{k}{1+k}\)，可以求得\(P^n\)的第一行第一列元素（即所求概率，本来超珍稀在仓库A，\(n\)次操作后仍然在仓库A中的概率）为\(\dfrac{1}{2}+\dfrac{1}{2}(2a-1)^n\)。另外难度在获得最简分数\(p/q\)，需要用欧几里得算法及时计算最大公约数并约分，否则容易数值溢出。

解答

根据备注，可以知道这道题的答案是\(\dfrac{(k-1)^n+(k+1)^n}{2(k+1)^n}=\dfrac{1}{2}\left(1+\dfrac{(k-1)^n}{(k+1)^n}\right)\)，根据经验，这道题可以使用暴力直接过（如下面代码实现的solve2所示）。

接下来讲解正确做法（如下面代码实现的solve1）。令\(u/v=(k-1)/(k+1)\)表示化简后的结果。那么可见\(\dfrac{1}{2}\cdot \dfrac{u^n+v^n}{v^n}\)就是最终的概率值。此外，\(\dfrac{u^n+v^n}{v^n}\)是一个最简分数。接下来考虑两种情况：

  • 如果\(u+v\)是奇数，那么上面的分数可以写成\(\dfrac{u^n+v^n}{2v^n}\)。因此这种情况的最终答案为\(((u^n\bmod 10)+(v^n\bmod 10)+(2v^n\bmod 10))\bmod 10\)。

  • 如果\(u+v\)是偶数，那么分母的\(2\)可以进一步和分子\(u^n+v^n\)进行约分，因此上面的分数可以写成\(\dfrac{(u^n+v^n)/2}{v^n}\)。为了保证除法的正确性，我们先对分子对\(20\)取模，然后再除以\(2\)。因此这种情况的最终答案为\(\left(\dfrac{((u^n\bmod 20)+(v^n\bmod 20))\mod 20}{2}+(v^n\bmod 10)\right)\bmod 10\)。

代码

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
from fractions import Fraction


# 正确做法
def solve1(n, k):
    num, den = k - 1, k + 1
    if num % 2 == 0:
        num, den = num >> 1, den >> 1
    if (num + den) % 2 == 0:
        p = (pow(num, n, 20) + pow(den, n, 20)) % 20 // 2
        q = pow(den, n, 20)
    else:
        p = (pow(num, n, 10) + pow(den, n, 10)) % 10
        q = pow(den, n, 10) * 2 % 10
    return (p + q) % 10


# 暴力做法
def solve2(n, k):
    f = Fraction((k + 1) ** n + (k - 1) ** n, 2 * (k + 1) ** n)
    return (f.numerator + f.denominator) % 10


T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    print(solve1(n, k))

3、数组变幻

一个长度为\(n\)的数组，每秒都在发生变幻。

每一次变幻，第\(1\)个位置的数字将会和第\(2\)个位置的数字合并，第\(3\)个位置的数字将会和第\(4\)个位置的数字合并，以此类推。。

这个数组会一直变幻到只剩两个数字为止。

合并数字时，将会使得两个数字相加。例如数组\([1,2,3,4,5]\)第一秒会变成\([3,7,5]\)（前两个数字合并，第三和第四个数字合并，由于没有第六个数字，所以第五个数字不变）第二秒会变成\([10,5]\)，此时数组中只剩两个数字，变幻结束。

小q有一个变量\(x\)，初始等于\(0\)。每次数组变幻后，小q会把数组的第一个元素加到\(x\)上。小q希望你输出最终\(x\)的值。

由于这个数组长度很大，所以小q在给你数据时采用了一种新的方式。小q总共会给出\(k\)条信息，每条信息包含两个正整数 \(a,b\)，表示这个数组中有一段长度为\(a\)的区间，区间中所有数字均为\(b\)。（详见样例）

由于答案可能很大，请输出答案对\(10^9+7\)取模后的结果。

输入

第一行给出两个正整数\(n,k\)，意义如题面所示。

接下来\(k\)行分别给出两个正整数\(a_i,b_i\)。表示数组有\(a_i\)个数字\(b_i\)。注意本题保证所有\(a_i\)的和为\(n\)。

  • \((1\le a_i\le n \le10^{18}, 1\le b_i \le 10^9, 1\le k \le10^5)\)

输出

输出最终\(x\)的值。

样例

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
输入：
5 5
1 1
1 2
1 3
1 4
1 5

输出：
13

提示：
初始数组为[1,2,3,4,5]
第一次操作后，数组变成[3,7,5]，x加上3。
第二次操作后，数组变成[10,5]，x加上10。
最终x等于13。

输入：
7 2
3 1
4 2

输出：
7

提示：
输入为3个1和4个2，即数组为[1,1,1,2,2,2,2]，第一秒变为[2,3,4,2]，第二秒变为[5,6]，最终的x等于2+5=7。

解答

这题是一道模拟题，需要注意一些细节。在模拟的过程中，我们依旧使用题目中的那种对数组的表达方式，即第\(i\)段元素有\(a_i\)个元素\(b_i\)。以下分两种情况进行讨论。

  1. 如果\(a_i=1\)，那么这时需要考虑和下一段数（如果存在的话）中的第一个进行合并。这时会产生一个段\((1,b_i+b_{i+1})\)。

  2. 如果\(a_1>1\)，那么这一段数会产生一个新段\((\lfloor a_i/2\rfloor,2\cdot b_i)\)，同时令\(a_i'=a_i\bmod 2\)，如果\(a_i'=1\)，那么转为情况1继续进行，否则考虑下一段。

由于每次变换过后，数组的元素数量都会减少一半，因此这种变换最多只会进行\(\log n\)次。此外，如果两个相邻段都只有一个元素，那么这些段必定会被合并。因此，在模拟过程中，数组的总段数不会超过\(3k\)。因此本题的时间复杂度为\(O(k\log n)\)。

代码

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
# include <bits/stdc++.h>
# define pl pair<ll,ll>
# define X first
# define Y second
using namespace std;
typedef long long ll;

ll n,mod=1e9+7;
int k;
bool ok(deque<pl> &v){
    ll t=0;
    for(auto &[x,y]:v){
        t+=x;
        if(t>2) return 1;
    }
    return 0;
}
int main(){
    scanf("%lld %d",&n,&k);
    ll a,b;
    deque<pl>q;
    for(int i=1;i<=k;i++){
        scanf("%lld %lld",&a,&b);
        q.push_back(pl(a,b));
    }
    ll ans=0;
    while(ok(q)){
        deque<pl>q2;
        while(!q.empty()){
            if(q[0].X==0) q.pop_front();
            else if(q[0].X==1){
                if(q.size()>=2){
                    --q[1].X;
                    q2.push_back(pl(1,(q[0].Y+q[1].Y)%mod));
                }
                else q2.push_back(pl(1,q[0].Y));
                q.pop_front();
            }
            else{
                q2.push_back(pl(q[0].X>>1,(q[0].Y<<1)%mod));
                q[0].X&=1;
            }
        }
        ans=(ans+q2[0].Y)%mod;
        q=q2;
    }
    printf("%lld\n",ans);
}

4、最短路

初始有\(n\)个点，第\(i\)个点坐标为\((x_i,y_i)\)，起点是第\(s\)个点，终点是第\(t\)个点，原本任意两点间都有一条线段代表能在两点间通行(长度为欧几里得距离)，但因为一些意外，\(s\)和\(t\)之间的线段被删除了，现在求\(s-t\)的最短距离是多少。

其中保证\(s\neq t\)。

\(i,j\)两点欧几里得距离即\(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\)

输入

第一行有三个正整数，依次表示有\(n\)个点，以及起点\(s\)和终点\(t\)。

接下来\(n\)行每行\(2\)个整数，第\(i\)行代表第个点的坐标为\(x_i,y_i\)。

  • \(3 \le n \le 10^5 ,1 \le s,t \le n, 1 \le x_i,y_i \le 10^6\)

输出

输出一行一个数代表答案（输出四舍五入到小数点后两位）

样例

1
2
3
4
5
6
7
8
9
10
输入：
5 1 5
17253 15901
25501 15698
28676 32041
30711 11015
18651 9733

输出：
17333.65

解答

由于每个边权都是欧几里得距离，因此这些边权满足三角形不等式。也就是说，如果存在一条路径经过了\(k\)个点，那么必定存在一条更短的路径，其经过\(k-1\)个点。

因此，最终答案为\(\displaystyle{\min_{1\le i\le n,i\not\in\{s,t\}}\{\text{dist}(s,i)+\text{dist}(i,t)\}}\)，其中\(\text{dist}(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\)。

代码

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
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
ll x[N],y[N];
int n;
double dis(int p,int q){
    ll dx=x[p]-x[q],dy=y[p]-y[q];
    return sqrt(dx*dx+dy*dy);
}
int main(){
    int s,t;
    scanf("%d %d %d",&n,&s,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&x[i],&y[i]);
    }
    double ans=1e14;
    for(int i=1;i<=n;i++){
        if(i==s||i==t) continue;
        ans=min(ans,dis(s,i)+dis(t,i));
    }
    printf("%.2f\n",ans);
}

5、三国无双游戏

牛牛最近三国演义入了迷，他时常幻想着自己是一代枭雄，坐拥城池百万，精锐无数。

然而他只能做做美梦玩玩三国无双的游戏罢了qwq。

游戏中牛牛有\(n\)座城池，城池编号为\(1\sim n\)，由于某些城池地理位置极其重要，因此牛牛要设置一些关卡来建立防御工程。现在牛午有\(m\)个工程计划，每个工程计划有两个整数\(L,R\)，表示从第\(L\)座城池到第\(R\)座城池中，至少有一个城池被设置为关卡。

牛牛想知道，为了使得每个计划都满足，有多少中不同的设置关卡的方法？

游戏难度：保证\(m\)个计划中，可能会出现相交的区间。

输入

第一行输入两个整数\(n\)和\(m\)，其中\(n\)表示城池的数量，\(m\)表示工程计划的数量。

接下来\(m\)行，每行两个整数\(L ,R\)，表示该计划要求从第\(L\)座城池到第\(R\)座城池中，至少有一个城池被设置为关卡。

\(1\le n,m\le 10^5,1\le L\le R\le n\)

输出

输出一个整数，表示设置关卡的方案数，对\(10^9+7\)取模。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入：
3 2
2 3
1 2

输出：
5

提示：
用1表示关卡，0表示普通城池，那么这5种方案分别是: 010，011，110，111，101

输入：
12 3
1 7
6 12
5 10

输出：
3988

解答

本题的统计要点在于：假设现在已经填了一个\(1\)比特，那么下一个\(1\)比特该往哪里填？需要注意的是，不存在两个相邻的\(1\)比特中间包含了我们输入给定的区间。

因此，我们可以考虑使用动态规划来解决这个问题。令状态\(f(i)\)表示已经填充了前\(i\)个比特，其中第\(i\)个比特为\(1\)，并且对于右端点小于等于\(i\)的区间，都满足要求的方案数。

令\(l_i\)表示右端点小于等于\(i\)的所有区间中，这些左端点的最大值（如果所有区间的右端点都大于\(i\)，那么令\(l_i=0\)。这意味着，对于任意\(i\ge 1\)，如果\(l_i>0\)，那么从\(l_i\)到\(i\)必须要有至少一个\(1\)。

那么我们可以写出如下状态转移方程：

\(f(i)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0 \\ &\sum_{j=l_{i-1}}^{i-1} f(j) & & \text{if}\quad i\ge 1 \\ \end{aligned}\right.\)

对于这个方程的第一行，这是一个空串，它显而易见是合法的。对于一个从\(f(j)\)到\(f(i)\)的转移，它是将第\(j+1,j+2,\dots,i-1\)都填上\(0\)，最后才在\(i\)填上\(1\)。也就是说，从\(f(l_{i-1}),f(l_{i-1}+1),\dots,f(i-1)\)中转移而来的方案都是不尽相同的，它们确保了区间\([l_{i-1},i-1]\)都至少包含了一个\(1\)。

因此，为了确保\([l_n,n]\)也是合法的，最终答案只包含\(\displaystyle{\sum_{i=l_n}^n f(i)}\)。

可见，\(f(i)\)的转移是\(O(n)\)的，令\(\displaystyle{s(i)=\sum_{j=0}^i f(j)}\)表示\(f(i)\)的前缀和，那么我们可以使用\(O(1)\)的时间优化这个转移结果。因此最终答案为：如果\(l_n=0\)，那么答案为\(s(n)\)，否则为\(s(n)-s(l_n-1)\)。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
ll mod=1e9+7;
int lp[N],n,m;
ll s[N];
int main(){
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        lp[y]=max(lp[y],x);
    }
    s[0]=1;
    int l=0;
    for(int i=1;i<=n;i++){
        ll w=s[i-1];
        if(l>0) w=(w-s[l-1]+mod)%mod;
        s[i]=(s[i-1]+w)%mod;
        l=max(l,lp[i]);
    }
    ll ans=s[n];
    if(l>0) ans=(ans-s[l-1]+mod)%mod;
    printf("%lld\n",ans);
}

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝