|
三、编程题（每题 25 分，共 50 分）
1、小杨的幸运数 问题描述
⼩杨认为，所有⼤于等于 a 的完全平⽅数都是他的超级幸运数。
⼩杨还认为，所有超级幸运数的倍数都是他的幸运数。⾃然地，⼩杨的所有超级幸运数也都是幸运数。
对于⼀个⾮幸运数，⼩杨规定，可以将它⼀直＋1，直到它变成⼀个幸运数。我们把这个过程叫做幸运化。例如，如果 a＝4，那么 4 是最⼩的幸运数，⽽1 不是，但我们可以连续对 1 做 3 次＋1 操作，使其变为 4，所以我们可以说，幸运化后的结果是 4。现在，⼩样给出 N 个数，请你⾸先判断它们是不是幸运数；接着，对于⾮幸运数，请你将它们幸运化。
输入描述
第⼀⾏ 2 个正整数 a，N。
接下来 N ⾏ ，每⾏⼀个正整数 x ，表⽰需要判断（幸运化）的数。 输出描述
输出 N ⾏，对于每个给定的 x ，如果它是幸运数，请输出lucky ，否则请输出将其幸运化后的结果。
特别提醒
在常规程序中，输⼊ 、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任何提⽰信息。 样例输入 1 2 4
1
4
5
9
样例输出 1 4
lucky
8
lucky
样例解释 1
1 虽然是完全平⽅数，但它⼩于 a， 因此它并不是超级幸运数，也不是幸运数。将其进⾏3 次＋1 操作后，最终得到幸运数 4。
4 是幸运数，因此直接输 lucky。
5 不是幸运数，将其进⾏3 次＋1 操作后，最终得到幸运数8。
9 是幸运数，因此直接输出 lucky。
样例输入 2 16 11
1
2
4
8
16
32
64
128
256
512
1024
样例输出 2 16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky
数据规模
对于 30%的测试点，保证 a,x≤ 100，N ≤ 100。
对于 60%的测试点，保证 a, x≤ 106
对于所有测试点，保证 a ≤1,000,001; 保证 N ≤2x 105，保证1 ≤ x ≤1,000,001
【题目大意】给一个完全平方数的标准，推导出哪些是超级幸运数，然后判断N个数字中，哪些是超级幸运数，是的输出“lucky”，不是的输出离该数字最近的比它大的数字。
【考纲知识点】数学知识，埃筛知识，循环知识
【解题思路】完全平方数按照定义，包括 1,4,9,16,25……。超级幸运数还可以是完全平方数的倍数，因此 8,12,18……也是超级幸运数。数据范围比较大，1e6，用埃筛的模板，判断每一个数字是否是幸运数字。不是幸运数字的话，保留离它最近的幸运数字作为答案。最终完成整个查询。
【参考程序】 #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1001*1001;
const double eps = 1e-8;
bool is_lucky[N +5];
int next_lucky[N + 5];
void init(){
}
int main(){
int a, T;
scanf("%d%d", &a, &T);
for(int i=1; i<=N; i++){
int t = int(sqrt(i) + eps);
if (i >=a && t*t == i)
is_lucky[i] = 1;
if(! is_lucky[i])
continue ;
for(intj = i+i; j <= N; j += i)
is_lucky[j] = 1;
}
for(int i = N; i; i--)
next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
while(T --){
int x;
scanf("%d",&x);
if(is_lucky[x])
cout << "lucky" << endl;
else
cout << next_lucky[x] << endl;
}
return 0;
}
2、烹饪问题
问题描述
有 N 种⾷材，编号从 0⾄N - 1，其中第 i 种⾷材的美味度为ai 。
不同⾷材之间的组合可能产⽣奇妙的化学反应。具体来说，如果两种⾷材的美味度分别为 x 和 y，那么它们的契合度为 x and y。其中，and 运算为按位与运算，需要先将两个运算数转换为⼆进制，然后在⾼位补⾜0，再逐位进⾏与运算。例如，12 与 6 的⼆进制表⽰分别为 1100 和 0110，将它们逐位进⾏与运算，得到0100,转换为⼗进制得到 4,因此 12 and 6 = 4。在 C++或Pythoy中,可以直接使⽤&运算符表⽰与运算。
现在，请你找到契合度最⾼的两种⾷材，并输出它们的契合度。 输入描述
第⼀⾏⼀个整数 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 ≤ 1,000；
对于所有测试点 ，保证 N ≤ 106 ，0 ≤ ai ≤ 2,147,483,647。 【题目大意】选出 2 个数字，求出这 2 个数字与操作的最大结果是多少。
【考纲知识点】位运算知识，循环知识，排序知识
【解题思路】需要选取 2 个数字，可以用双重循环枚举这2 个数字，取最大值，最终得到答案。对于前 40%的测试点是可以的。当数据量大的时候，就超时了。我们知道，两个数字对应的二进制，位数越高是 1，越有可能是答案。所以从最高位统计，是否至少有 2 个数字最高位是 1，保存最高位结果，并且把最高位非1 的数字删去；再查询次高位是否至少有 2 个以上的数字二进制位都是1，以此类推，求出哪 2 个数字与 结果最大。利用快速排序的方法每次将剩余数字中当前考虑的位为 1 的数字放在前面，时间复杂度是 O(N*log(a_i 值的最大值))。
【参考程序】 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAX_N = int(1e6)+100;
int a[MAX_N];
int sort(int l,int r,int k){
while(l<=r){
while((l<=r)&&(a[l] >> k & 1)) l++;
while((l<=r)&&(!(a[r] >> k & 1))) r--;
if(l<=r) swap(a[l++],a[r--]);
}
return r;
}
int main(){
int n,j, ans=0;
scanf("%d", &n);
for(int i=1; i <= n;i++) scanf("%d",&a[i]);
for(int i=31; i>=0; i--)
if((j=sort(1,n,i)) >= 2){
ans = ans | 1 << i;
n = j;
}
printf("%d\n", ans);
return 0;
}
(责任编辑：lizq) |