不开xx见xx

题目

十年OI一场空，不开 long long 见xx  // int 溢出
十年OI一场空，开了 long long 见xx  // #define int long long → MLE
十年OI一场空，不开 unsigned long long 见xx  // 对 2⁶⁴ 取模的题却只用了 long long
十年OI一场空，只开 unsigned long long 见xx  // 详见 csp-s 2020 T2，ans=2⁶⁴ 得特判
十年OI一场空，不写高精见xx  // 详见 NOIP 2020 T1
十年OI一场空，不看模数见xx  // p=998244353? p=998244853!

从上述 OI 梗中可以看出对问题中变量数据范围的正确识别是非常重要的。

leexzq 给了你这样一个问题：你有一个长度为 n 的非负数组 A，你现在要在 A_i 与 A_i+1 插入下表中的 C++ 运算符（无论是什么都从左向右依次运算，且运算必须合法），使得最后这个表达式的结果最大。

可以使用的运算符：+  -  *  /  %  ^  &  |  <<  >>

你研发了一种新的语言 ++C，可以支持类型 int_2^k（k 位有符号整型，k≥2），现在你想知道，为了解决上述问题，你至少需要开多大的数据类型（找到最小的 k 使得运算过程中不溢出）。

输入：第一行一个整数 n，表示数组长度；第二行 n 个整数 A_i，表示数组中的数。
输出：一行一个整数 k（k≥2），含义如题中所示。

样例：

4
3 0 0 1

4

提示：对于所有数据，1≤n≤10⁵，0≤A_i<10⁹。

思路

复杂度分析

• 时间复杂度：
• 空间复杂度：

← 返回菜鸟的coding