信息学奥赛-入门级 题库
为了统计一个非负整数的二进制形式中 1 的个数,代码如下:
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
___________;
}
return ret;
}
则空格内要填入的语句是( )。
考虑如下递归算法
solve(n)
if n<=1 return 1
else if n>=5 return n*solve(n-2)
else return n*solve(n-1)
则调用 solve(7)得到的返回结果为( )。
solve(7)= 7 * solve(7 - 2)
solve(5)= 5 * solve(5 - 2)
solve(3)= 3 * solve(3 - 1)
solve(2)= 2 * solve(2 - 1)
solve(1)= 1
那么solve(7)=7*5*3*2*1 = 210。
设输入字符串长度为 n,decode 函数的时间复杂度为( )。

设有一个含有13个元素的Hash表(O~12),Hash函数是:H(key)=key % 13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、8、31、20、19、18、53、27),18应放在第几号格中( ) 。
若将 isPrime(i)函数种的条件改为 i<=n/2,输入“20”时,countPrimes(20)的输出将变为“6”。( )
精明与糊涂
有N个人,分为两类:①精明人:永远能正确判断其他人是精明还是糊涂;②糊涂人:判断不可靠,会给出随机的判断。已知精明人严格占据多数,即如果精明人有k个,则满足k>N/2
你只能通过函数query(;j)让第i个人判断第j个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。目标是通过互相判断,找出至少一个百分之百能确定的精明人(无需关心query(i,j)的内部实现)。
以下程序利用“精明人占多数”的优势,通过“消除”过程让人们互相判断并抵消.经过若干轮抵消后,最终留下的候选者必然属于多数派,即精明人。
例如,假设有三个人0、1、2。如果0说1是糊涂人,而1也说0是糊涂人,则O和1至少有一个是糊涂人。程序将同时淘汰0和1。由千三人里至少有两个精明人,我们确定2是精明人。试补全程序。
01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07 unsigned short x, y;
08 cin >> x >> y;
09 x = (x | x << 2) & 0x33;
10 x = (x | x << 1) & 0x55;
11 y = (y | y << 2) & 0x33;
12 y = (y | y << 1) & 0x55;
13 unsigned short z = x | y << 1;
14 cout << z << endl;
15 return 0;
16 }
假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题:
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14 if (m == 1) return n;
15 if (n == 0) return 0;
16
17 int ret = numeric_limits<int>::max();
18 for (int i = 1; i <= n; i++)
19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20 return ret;
21 }
22
23 int g(int n, int m)
24 {
25 for (int i = 1; i <= n; i++)
26 h[i][1] = i;
27 for (int j = 1; j <= m; j++)
28 h[0][j] = 0;
29
30 for (int i = 1; i <= n; i++) {
31 for (int j = 2; j <= m; j++) {
32 h[i][j] = numeric_limits<int>::max();
33 for (int k = 1; k <= i; k++)
34 h[i][j] = min(
35 h[i][j],
36 max(h[i - k][j], h[k - 1][j - 1]) + 1);
37 }
38 }
39
40 return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }
假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题:
