深圳企业网站建设服务中心个人网站

小欧的括号嵌套

题目描述

小欧想要构造一个合法的括号序列满足以下条件：

• 括号序列长度恰好为 $2\times n$。
• 括号序列的嵌套层数最大值为 $r$。

括号嵌套层数是指在一个字符串中，以左括号 “(” 和右括号 “)” 形成的括号对的最大嵌套深度。

输入描述

一行两个整数 $n,r(1\le r\le n\le 10^5)$。

输出描述

一行一个字符串表示括号序列。若有多种构造方案，输出任意一个即可。

解题思路

构造一种特殊的满足条件的括号序列即可。

代码实现

int main() {int n, r;scanf("%d%d", &n, &r);string s = string(r, '(') + string(r, ')');for (int k = n / r; k-- > 0; cout << s);cout << string(n % r, '(') + string(n % r, ')');return 0;
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

小欧的等差数列

题目描述

小欧有一个长度为 $n$，首项为 $a$，公差为 $d$ 的等差数列。现在，小欧把这 $n$ 个数看作一个集合，每次操作可以从集合中任意选两个数 $a_i,a_j$，如果 $a_i+a_j$ 是偶数，那么可以将 $(a_i+a_j)/2$ 加入到集合中。小欧想知道，经过若干次操作后，集合中最多能有多少个数。

输入描述

一行三个整数 $n,a,d$，表示等差数列的长度，首项和公差。

• $1\le n\le 10^5$
• $1\le a,d\le 10^9$

输出描述

输出一个整数，表示集合中最多能有多少个数。

解题思路

• $a_i+a_j$ = $a+i\times d+a+j\times d$
• 若 $i+j$ 为偶数，则 $(a_i+a_j)$ 为偶数，但 $(a_i+a_j)/2$ 已存在于集合中。
• 若 $d$ 为偶数，则 $(a_i+a_j)$ 为偶数，此时 $(a_i+a_j)/2$ 不一定在集合中。
• 若由集合衍生的数 $x$ 在 $a,a+d$ 之间，那么 $x$ 必然可以由 $a,a+d$ 衍生得到，$a+k\times d,a+(k+1)\times d$ 同理。
• 所以，仅需考虑由 $a,a+d$ 可以衍生得到多少数即可。
• 若 $d$ 的因数包含 $2^k$，那么，由 $a,a+d$ 可以衍生得到 $2^k-1$ 个数，由集合可衍生得到的数的个数为 $(2^k-1)\times (n-1)$。

代码实现

int main() {long long n, a, d, k = 0;cin >> n >> a >> d;while (!(d & 1))k++, d >>= 1;cout << n + ((1 << k) - 1) * (n - 1);return 0;
}

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

小欧喝水

小欧拿了 $n$ 个杯子排成了一排，其中有 $k$ 个杯子装满了水，剩余的 $n-k$ 个杯子为空的。小欧每回合的操作如下：

1. 随机选择一个杯子。
2. 杯子是空的。回合直接结束。
3. 杯子是满的。如果小欧上一回合喝过了水，则回合结束；否则将喝完这杯水，回合结束。

小欧想知道，她喝完所有水的回合数期望是多少？

输入描述

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

• $1\le k\le n\le 10^6$

输出描述

一个浮点数，代表期望的回合数。如果你的答案和正确答案的误差不超过 $10^{-6}$，则认为答案正确。

解题思路

本题留给读者小试牛刀。

END

题目来源：OPPO 2024届校招正式批笔试题-后端（C卷）

文章声明：题目来源 牛客 平台，如有侵权，请联系删除！