怎么做传奇网站,烟台网站制作企业,百度代做seo排名,屏蔽wordpress自带编辑器小欧的括号嵌套
题目描述
小欧想要构造一个合法的括号序列满足以下条件#xff1a;
括号序列长度恰好为 2 n 2n 2n。括号序列的嵌套层数最大值为 r r r。
括号嵌套层数是指在一个字符串中#xff0c;以左括号 “(” 和右括号 “)” 形成的括号对的最大嵌套深度。
输入…小欧的括号嵌套
题目描述
小欧想要构造一个合法的括号序列满足以下条件
括号序列长度恰好为 2 × n 2×n 2×n。括号序列的嵌套层数最大值为 r r r。
括号嵌套层数是指在一个字符串中以左括号 “(” 和右括号 “)” 形成的括号对的最大嵌套深度。
输入描述
一行两个整数 n , r ( 1 ≤ r ≤ n ≤ 1 0 5 ) n, r(1 ≤ r ≤ n ≤ 10^5) n,r(1≤r≤n≤105)。
输出描述
一行一个字符串表示括号序列。若有多种构造方案输出任意一个即可。
解题思路
构造一种特殊的满足条件的括号序列即可。
代码实现
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) O(n)
空间复杂度 O ( n ) O(n) O(n)
小欧的等差数列
题目描述
小欧有一个长度为 n n n首项为 a a a公差为 d d d 的等差数列。现在小欧把这 n n n 个数看作一个集合每次操作可以从集合中任意选两个数 a i , a j a_i,a_j ai,aj如果 a i a j a_ia_j aiaj 是偶数那么可以将 ( a i a j ) / 2 (a_ia_j)/2 (aiaj)/2 加入到集合中。小欧想知道经过若干次操作后集合中最多能有多少个数。
输入描述
一行三个整数 n , a , d n, a, d n,a,d表示等差数列的长度首项和公差。 1 ≤ n ≤ 1 0 5 1 ≤ n ≤ 10^5 1≤n≤105 1 ≤ a , d ≤ 1 0 9 1 ≤ a, d ≤ 10^9 1≤a,d≤109
输出描述
输出一个整数表示集合中最多能有多少个数。
解题思路 a i a j a_i a_j aiaj a i × d a j × d ai×daj×d ai×daj×d若 i j ij ij 为偶数则 ( a i a j ) (a_ia_j) (aiaj) 为偶数但 ( a i a j ) / 2 (a_ia_j)/2 (aiaj)/2 已存在于集合中。若 d d d 为偶数则 ( a i a j ) (a_ia_j) (aiaj) 为偶数此时 ( a i a j ) / 2 (a_ia_j)/2 (aiaj)/2 不一定在集合中。若由集合衍生的数 x x x 在 a , a d a,ad a,ad 之间那么 x x x 必然可以由 a , a d a,ad a,ad 衍生得到 a k × d , a ( k 1 ) × d ak×d,a(k1)×d ak×d,a(k1)×d 同理。所以仅需考虑由 a , a d a,ad a,ad 可以衍生得到多少数即可。若 d d d 的因数包含 2 k 2^k 2k那么由 a , a d a,ad a,ad 可以衍生得到 2 k − 1 2^k-1 2k−1 个数由集合可衍生得到的数的个数为 ( 2 k − 1 ) × ( n − 1 ) (2^k-1) × (n-1) (2k−1)×(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) O(1)。
空间复杂度 O ( 1 ) O(1) O(1)。
小欧喝水
小欧拿了 n n n 个杯子排成了一排其中有 k k k 个杯子装满了水剩余的 n − k n-k n−k 个杯子为空的。小欧每回合的操作如下
随机选择一个杯子。杯子是空的。回合直接结束。杯子是满的。如果小欧上一回合喝过了水则回合结束否则将喝完这杯水回合结束。
小欧想知道她喝完所有水的回合数期望是多少
输入描述
两个正整数 n , k n,k n,k用空格隔开。 1 ≤ k ≤ n ≤ 1 0 6 1≤ k ≤ n ≤ 10^6 1≤k≤n≤106
输出描述
一个浮点数代表期望的回合数。如果你的答案和正确答案的误差不超过 1 0 − 6 10^{-6} 10−6则认为答案正确。
解题思路
本题留给读者小试牛刀。
END
题目来源OPPO 2024届校招正式批笔试题-后端C卷
文章声明题目来源 牛客 平台如有侵权请联系删除
