烹饪问题
时间限制：1.0 s
内存限制：128.0 MB
问题描述
有N种食材，编号从0至N-1，其中第 种食材的美味度为 。
不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为x和y，那么它们的契合度为x and y。
其中，and运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足0，再逐位进行与运算。例如，12与6的二进制表示分别为 1100 和 0110 ，将它们逐位进行与运算，得到 0100 ，转换为十进制得到4，因此。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。
现在，请你找到契合度最高的两种食材，并输出它们的契合度。
输入描述
第一行一个整数N，表示食材的种数。
接下来一行N个用空格隔开的整数，依次为a0,…,aN-1，表示各种食材的美味度。
输出描述
输出一行一个整数，表示最高的契合度。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
3 1 2 3
样例输出 1
2
样例解释 1
可以编号为1,2的食材之间的契合度为2 and 3=2，是所有食材两两之间最高的契合度。
样例输入 2
5 5 6 2 10 13
样例输出 2
8
样例解释 1
可以编号为3,4的食材之间的契合度为10 and 13=8，是所有食材两两之间最高的契合度。
数据规模
对于40%的测试点，保证N≤1000；
对于所有测试点，保证N≤106，0≤ai≤2147483647。
相似题推荐
相等序列
时间限制： 1.0 s
内存限制：512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · · ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作：
选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai * P ，P 为任意质数；
选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai /P ，P 为任意质数，要求Ai能被p整除。
小 A 想请你帮他计算出令序列中所有整数都相同 ，最少需要花费多少金币。
输入格式
第一行一个正整数N ，含义如题面所⽰ 。
第二行包含 N 个正整数 A1 , A2 , · … ,AN ，代表序列 A。
输出格式
输出一行 ，代表最少需要花费的金币数量。
输入样例
5 10 6 35 105 42
输出样例
8
数据范围
对于60%的测试点 ，保证 1 ≤ N, Ai ≤ 100 。
对于所有测试点 ，保证 1 ≤ N, Ai ≤ 105 。
小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。
// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
bool check(int L, int K, int x) {
int cuts = (L - 1) / x;
return cuts <= K;
}
// 二分查找最小可行的 x
int binary_cut(int L, int K) {
int l = 1, r = L;
while (l < r) {
int mid = l + (r - l) / 2;
________________________________ // 在此处填入代码
}
return l;
}
int main() {
int L = 10; // 木头长度
int K = 2; // 最多切 K 刀
cout << binary_cut(L, K) << endl;
return 0;
} A．if (check(L, K, mid)) r = mid; else l = mid + 1; |
B．if (check(L, K, mid)) r = mid+1; else l = mid + 1; |
C．if (check(L, K, mid)) r = mid + 1; else l = mid - 1; |
D．if (check(L, K, mid)) r = mid + 1; else l = mid; |
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n +1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
________________________________ { // 在此处填入代码
is_prime[ i * primes[j] ] = 0;
if (i % primes[j] == 0)
break;
}
}
return primes;
}A．for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) |
B．for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++) |
C．for (int j = 1; j <= sqrt(n); j++) |
D．for(int j = 1; j < n && i * primes[j] <= n; j++) |
下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。
int factorial1(int n) {
if (n <= 1) return 1;
return n * factorial1(n - 1);
}
int factorial2(int n) {
int acc = 1;
while (n > 1) {
acc = n * acc;
n = n - 1;
}
return acc;
} | A． 上面两种实现方式的时间复杂度相同，都为O(n) |
B． 上面两种实现方式的空间复杂度相同，都为O(n) |
| C． 上面两种实现方式的空间复杂度相同，都为O(1) |
D． 函数 factorial1() 的时间复杂度为O(2^n)，函数 factorial2() 的时间复杂度为O(n) |
