信息学奥赛-提高级 题库
某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn,均为0或1。该系统每次随机生成 n 个数 a1,a2,…,an,均为 0 或 1,请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。
然而,事与愿违。例如,当 n=4 时,有人窃听了以下 5 次问答:

就破解出了密码 s1=_________,s2=_________,s3=_________,s4=_________。
s1 = 0,s2 = 1,s3 = 1,s4 = 1
现有一只青蛙,初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时,下一时刻将等概率随机跳到1,2,…,k 号荷叶之一上,直至跳到1号荷叶为止。当n=2 时,平均一共跳2次;当 n=3 时,平均一共跳 2.5 次。则当 n=5 时,平均一共跳_________次。
![]()
37/12
本题中,我们约定布尔表达式只能包含 p, q, r 三个布尔变量,以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p, q, r 如何取值,两个布尔表达式的值总是相同,则称它们等价。例如,(p∨q)∨r 和 p∨(q∨r)等价,p∨¬p 和 q∨¬q 也等价;而 p∨q 和 p∧q 不等价。那么,两两不等价的布尔表达式最多有 个。
256
生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是(ABD)。
定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字符串“BCA”可以将 A 移到 B 之前,变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。
4
(大整数开方) 输入一个正整数n(1≤n≤10100),试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中 len 表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数 a 和 b 的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
① +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
② ;
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数 a 和 b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= ③ ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数 a 和 b 的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=( ④ )*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数 a 加 2 之后的结果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
⑤ ;
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数 a>b 则返回 true,否则返回 false
{
int i;
if( ⑥ )
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]- ⑦ ;
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over( ⑧ ))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
① ans.num[i + j - 1]
② ans.num[i] %= 10(或 ans.num[i] = ans.num[i] % 10) ③ a.num[i] + b.num[i]
④ ans.num[i] % 2(或 ans.num[i] & 1)
⑤ ans.len++(或 ++ans.len 或 ans.len += 1 或 ans.len = ans.len + 1)
⑥ a.len < b.len
⑦ '0'(或 48)
⑧ times(middle, middle), target

假设输入的n, k和d[i]都是不超过10000的正整数,且k不超过n,并 假设rand()函数产生的是均匀的随机数,完成下面的判断题和单选题:

