主题：第54次编程比赛
yxs0001 [专家分：9560] 发布于 2007-05-27 17:06:00
题目1（60分）：对于一个自然数n，可以把它转换成对应的二进制数a[k] a[k-1] ..... a[1] a[0]，其
中：n= ∑a[i] * 2^i 而且 a[i]=0 或1 （0=< i < k) , a[k]=1。如：10 转换为1010；5 转换为 101。
我们统计一下a[0]......a[k]这k+1 个数中的0 的个数和1 的个数。如果在这k+1 个数中，0 的个数比1
个数多，就称n为A类数。给定m，求1~m (包含1,m)中A类数的个数。
函数接口：int solve(int m)
例如：m=3 return 0
题目2（40分）：已知n∈Q，则2n+1∈Q，4n+5∈Q；且 1∈Q，求Q中第k小元素。
函数接口：int Q(int k)
判分要求：
1、结果正确得分，错误该题0分。
2、结果正确者，计分方法：该题用时最少者满分，其他按与满分者用时比计算。（例如，第一题最佳时
间1s,某人用时2s,则 1/2*60 = 30）
3、二题得分之和最大者胜出。
格式要求：所有代码包含在参赛者名字的名字空间中。例如：
//名字空间
namespace yxs0001
{
//以下为参赛代码
int solve(int m)
{
return 0;
}
int Q(int k)
{
return 0;
}
}
或
namespace yxs0001
{
int solve(int m)
{
return 0;
}
}
namespace yxs0001
{
int Q(int k)
{
return 0;
}
}
回复列表 （共34个回复）
31 楼
latalata [专家分：60] 发布于 2007-05-30 15:11:00
namespace yxs0001
{
int solve(int m)
{
int count=0;
int i,j,k,temp,C_0,C_1;;
long temp1,temp2;
int Label[33];
int Wei_Num=0,Lef_Num;
while(m)
{
Label[Wei_Num++]=m%2;
m/=2;
}
for(i=0;i<Wei_Num/2;i++)
{
temp=Label[i];
Label[i]=Label[Wei_Num-1-i];
Label[Wei_Num-1-i]=temp;
}
for(i=3;i<Wei_Num;i++)
{
Lef_Num=i-1;
for(j=i/2+1;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0=0;
C_1=0;
for(i=0;i<Wei_Num;i++)
{
if(Label[i]==0)C_0++;
else C_1++;
}
if(C_0>C_1)count++;
C_0=0;
C_1=1;
i=1;
while(i<Wei_Num)
{
if(Label[i]==0)C_0++;
else if(Label[i]==1)
{
Lef_Num=Wei_Num-i-1;
C_0++;
if(C_0>=Wei_Num/2+1)
{
temp1=1;
for(j=1;j<=Lef_Num;j++)
temp1*=2;
count+=temp1;
}
else
{
for(j=Wei_Num/2+1-C_0;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0--;
C_1++;
}
i++;
}
return count;
}
}
32 楼
latalata [专家分：60] 发布于 2007-05-30 17:00:00
刚才好像没按要求的名字空间格式，麻烦yxs0001帮忙改一下，谢谢。
33 楼
System64 [专家分：10] 发布于 2007-05-30 17:17:00
[code=c]
namespace System64{
// subject 1
#define _INT (8*sizeof(int)-1)
int value(unsigned n){
int k = _INT+1;
unsigned i = 1<<_INT;
while( !(n&i) ){
n <<= 1;
k--;
}
int j = 0,l = 0;
while( k ){
if( n&i ) j++;
else l++;
n <<= 1;
k--;
}
return j < l ? 1:0;
}
int solve(int m){
if( m <= 3 ) return 0;
int sum = 0;
for(int i=3;i<=m;i++)
sum += value( unsigned(i) );
return sum;
}
// subject 2
void ShellSort(int s[],int n){
int d = n;
while(d>=1){
d /= 2;
int flag;
do{
flag = 0;
for(int i=0;i<n-d;i++){
int j = i+d;
if( s[j] < s[i] ){
int temp = s[j];
s[j] = s[i];
s[i] = temp;
flag = 1;
}
}
}while( flag );
}
}
int Q(int k){
int *s = new int[2*k+1];
int i = 0;
s[i] = 1;
int j = i;
i++;
while( i<=(2*k) ){
s[i++] = 2*s[j]+1;
if(i > (2*k)) break;
s[i++] = 4*s[j]+5;
j++;
}
ShellSort(s,(2*k+1));
return s[k-1];
}
}
[/code]
34 楼
latalata [专家分：60] 发布于 2007-05-30 19:17:00
第二题:
namespace latalata
{
int Q(int k)
{
int num,Length,Cur_Min;
int *p=new int[k];
int *q=new int[k];
for(int i=0;i<k;i++)
{
*(p+i)=-1;
*(q+i)=0;
}
*p=1;
num=1;
Length=1;
Cur_Min=1;
while(Length<k)
{
for(int i=0;i<Length;i++)
{
if(*(q+i)==0)
{//未加2n+1
*(p+Length)=2*(*(p+i))+1;
(*(q+i))++;
Length++;
break;
}
else if(*(q+i)==1)
{//未加4n+5
int Label=i;
Cur_Min=4*(*(p+i))+5;
for(int j=i+1;j<Length;j++)
{
if(*(q+j)==0){
int temp=2*(*(p+j))+1;
if(temp<Cur_Min){
Label=j;
Cur_Min=temp;
j=Length;
}
}
}
*(p+Length)=Cur_Min;
(*(q+Label))++;
Length++;
break;
}
}
}
num=*(p+Length-1);
delete []p;
delete []q;
return num;
}
}
我来回复
您所在位置：