| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 801 人关注过本帖
标题:两道ACM题
只看楼主 加入收藏
fengsjack
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2010-6-9
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:6 
两道ACM题
深陷于二进制的zzz

Description
  二进制是计算机学习中最基础的部分了,但是zzz对二进制总是非常的不敏感,总是没办法深入的理解。为了对自己进行特训,加强对二进制的理解,zzz设计了一个有趣的游戏,给定一个十进制数字N,判断给定数字的二进制表示中,是否包含长度为K的连续的1。zzz玩的不亦乐乎,但很快就发现,自己并不能确定游戏的正确答案,所以他想请你帮忙给出游戏的正确结果。



Input
  输入由多组数据组成,第一行输入一个正整数C(1<=C<=1000),表示数据个数。
接下来C行,每行输入两个整数N(0<=N<231)、K(0<K<=31)。



Output
  输出C行,每行对应输入数据的答案。如果数字N的二进制表示中,包含长度为K的连续的1,则输出"Yes",否则输出"No"。(不包含引号)



Sample Input
2
6 2
6 3



Sample Output
Yes
No

天平
Description
索里嘎有一个天平和n个砝码,天平的两边都能放砝码。他想知道用他的天平和n个砝码能够准确称量的质量有几种。比如,n=2, 砝码的质量分别为1,3。则他能称的质量有1,2,3,4。


Input
第一行有一个正整数n,便是砝码的数量(1<=n<=100)。
接下来是n个正整数,分别表示砝码的质量,(不大于1000)。


Output
输出只有一个正整数,即能够称的质量有几种。


Sample Input
4
1 2 3 8


Sample Output
14

搜索更多相关主题的帖子: ACM 
2010-06-17 22:25
heartnheart
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:335
专家分:1096
注 册:2009-7-10
收藏
得分:4 
第一道:
#include<stdio.h>
#include<stdlib.h>

#include<string.h>


char str1[10];
char str2[35];
int  main()
{
   
    int c;
    scanf("%d",&c);
    while(c--){
               int n,k;
               scanf("%d%d",&n,&k);
               itoa(n,str1,2);
               for(int i = 0; i <k; i++)
                       str2[i] = '1';
               str2[k] = '\0';
               if(strstr(str1,str2)!=NULL)
                        printf("Yes\n");
               else
                        printf("No\n");
               
                                       
    }
  //system("pause ");
  
      
}
第二道有空再说

2010-06-17 23:20
ZeroFive
Rank: 1
来 自:hust
等 级:新手上路
帖 子:2
专家分:0
注 册:2010-6-16
收藏
得分:0 
很好玩
2010-06-17 23:53
dstone
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:20
专家分:125
注 册:2010-6-17
收藏
得分:2 
第一题如下,第二题比较复杂,暂时没思路!
程序代码:
#include <stdio.h>
#include <stdlib.h>

/*计算data的二进制表示中,是否有连续的num个1*/
bool calc(int data, int num)
{
    int i;

    /*用来对data中的连续的1计数*/
    int count = 0;

    for( i = 0; i < sizeof(int)*8; i++)
    {
        if( 1 == (data & 1))
        {
            count++;            

            /*连续的1的个数大于num,满足条件,返回true*/
            if(count >= num)
                return true;
        }
        else
            count = 0;

        data = data >> 1;
    }

    /*连续的1的个数没有num个,不满足条件,返回false*/
    return false;
}

/*存放一行的data中是否有num个连续的1*/
struct Node
{
    bool k;
    struct Node * next;
};

int main(void)
{
    int line,i;
    int data, num;

    /*构造一个链表,用来存放每行的数是否满足条件*/
    struct Node * head = (Node*)malloc(sizeof(struct Node));
    struct Node * p = head;
    struct Node * q = head;

    /*line行数据*/
    scanf("%d", &line);
    p = head;
       
    /*循环接收每行的data和num值,并计算结果存放在一个Node对象里*/
    for(i = 0; i < line; i++)
    {
        scanf("%d %d", &data, &num);

        p->k = calc(data, num);

        q = (Node*)malloc(sizeof(struct Node));
        p->next = q;       
       
        p = q;       
    }

    q->next = NULL;
    p = head;

    /*将最终结果打印在显示器中*/
    for(i = 0; i < line; i++)
    {
        if(p->k)
            printf("Yes\n");
        else
            printf("No\n");        

        /*循环释放每个申请的节点空间*/
        q = p;
        p = p->next;
        free(q);
    }

    return 0;
}
2010-06-18 16:09
ZQDragon
Rank: 2
等 级:论坛游民
帖 子:30
专家分:39
注 册:2010-6-8
收藏
得分:2 
由于没时间,下次给你个更快的。^.^
#include<stdio.h>
#include<windows.h>
#include<math.h>
#define N 10000
int tp=0;//指向Asn[]数组中下一个结果存储的位置

void sort(int a[] ,int n)
{
    int i , j;
    for(i=0;i<n;++i)
    for(j=0;j<n-1;++j)
    {
        if(a[j]>a[j+1])
        {
            int temp=a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
        }
    }
}


int exam(int a[],int m)
{
    for(int i=0;i<tp;++i)
    if(m==a[i])
    return 0;
    return 1;
}

void ans(int a[],int b[],int t)
{
    int i=0 , n , m ;
    int flag=0;
    if(tp==0)
    {
       a[i]=b[t];
       ++tp;
       return;
    }

    for(n=tp-1;n>-1;--n)
    {
       m=abs(b[t]-a[n]);
       if(m!=0&&exam(a,m))
       {
           a[tp+flag]=m;
           ++flag;
       }
    }
   
    for(i=0;i<tp;++i)
    {
       m=b[t]+a[i];
       if(exam(a,m))
       {
          a[tp+flag]=m;
          ++flag;
       }
    }
    tp+=flag;
    if(exam(a,b[t]))
    {
       a[tp]=b[t];
       sort(a,tp);
       ++tp;
    }
    sort(a,tp);
}
         
int main()
{
    int Ans[N] ;/*存储结果*/
    int n , a[100];
    printf("Input n:");
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    scanf("%d",a+i);
    sort(a,n);//对砝码进行排序
    for(int i=0;i<n;++i)
    ans(Ans,a,i);
    printf("\n共有%d种\n",tp);
    for(int i=0;i<tp;++i)
    printf("%d           ",Ans[i]);
    printf("\n");
    system("pause");
    return 0;
}
              
     
2010-06-18 17:57
ZQDragon
Rank: 2
等 级:论坛游民
帖 子:30
专家分:39
注 册:2010-6-8
收藏
得分:0 
其实第二题方法还是蛮简单的,因为我们可以采用递推的方法,先计算前两个的结果,在用第三个砝码与产生的结果在结合
以此类推,楼主自己试试。
2010-06-18 18:01
cracker134
Rank: 2
等 级:等待验证会员
帖 子:18
专家分:13
注 册:2010-6-15
收藏
得分:2 
程序代码:
#include<stdio.h>
void sum_n(int *pres,int *pfm,int n,int i);
void generate(int *pres,int *ptemp,int *pfm,int n,int i_n,int i);
int test(int *ptemp,int i_n);
void to_res(int *ptemp,int *pres,int i,int add_minus_n);
int main()
{
  int n,fm[100],res[95051],i,sum=0;
  int *pfm;
  for(i=0;i<95051;i++) {res[i]=0;}
  pfm=fm;
  printf("Input:\n");
  scanf(" %i",&n);
  if((n<1)||(n>100)) {puts("error!");}
  for(i=0;i<n;i++)
  {
   scanf(" %i",pfm+i);
   if((*(pfm+i)<1)||(*(pfm+i)>1000)) {puts("error!");}
  }
  if(n==1){printf("1\n");}
  else
  {
   for(i=2;i<=n;i++)
   {
    sum_n(res,pfm,n,i);
   }
   for(i=0;i<n;i++)
   {
    res[*(pfm+i)]+=1;
   }
   for(i=0;i<95051;i++)
   {
   if(res[i]!=0) {sum+=1;}
   }
   printf("Output:\n%i\n",sum);
  }
  return 0;
}
/////////////////////////////////////////////////////////////
void sum_n(int *pres,int *pfm,int n,int i)
{

 int temp[100];

 generate(pres,temp,pfm,n,0,i);
}
/////////////////////////////////////////////////////////////
void generate(int *pres,int *ptemp,int *pfm,int n,int i_n,int i)
{

 int ctr;

 for(ctr=0;ctr<n;ctr++)

 {
  *(ptemp+i_n)=*(pfm+ctr);
  if((i_n!=0)&&(test(ptemp,i_n)==0)){continue;}
  if(i_n<i-1) {generate(pres,ptemp,pfm,n,i_n+1,i);}
  if(i_n==i-1)
  {
   to_res(ptemp,pres,i,0,0);
  }

 }
}
/////////////////////////////////////////////////////////////
int test(int *ptemp,int i_n)
{

 int i,res=1;

 for(i=0;i<i_n;i++)

 {
  if(*(ptemp+i)==*(ptemp+i_n))
  {
   res=0;
   break;
  }

 }

 return res;
}

/////////////////////////////////////////////////////////////
void to_res(int *ptemp,int *pres,int i,int add_minus_n,int sum)
{

 int add_minus,ctr;

 for(add_minus=0;add_minus<2;add_minus++)

 {
  if(add_minus==1)
  {
   sum-=*(ptemp+add_minus_n);
  }
  else
  {
   sum+=*(ptemp+add_minus_n);
  }
  if(add_minus_n<i)
  {
   to_res(ptemp,pres,i,add_minus_n+1,sum);
  }
  if(add_minus_n==i-1)
  {
   if(sum>=0) {*(pres+sum)+=1;}
  }

 }
}

2010-06-18 19:27
快速回复:两道ACM题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022983 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved