在结点1处放一个小球,它会往下落。每个内结点上都会有一个开关,初始全部关闭,当每次有小球落到一个开关上时,状态都会改变。当小球到达一个结点是,如果结点上的开关关闭,则往左走,否则往右走,直到走到叶子的结点,如图。
Sample Input
54 23 410 12 28 128-1
Sample Output
1275123255
【分析】
对于一个结点K,其左结点和右结点分别为2k和2k+1。
小球落到结点处,先改变,后选择。
【代码】
1 #include2 #include 3 const int maxd = 20; 4 int s[1< < I;i++ ){12 k = 1;13 while(true){14 s[k] = !s[k];15 k = s[k] ? k*2 : (k*2+1);16 if(k > n) break;17 }18 }19 printf("%d\n",k/2);20 }21 return 0;22 }
【总结】
"<<" 用法:
1.重载输出流运算符
2.数据移位运算符:x = i << 4 ; //将 i 的值左移4位放大2的4次方
memset(s,0,sizeof(s));
//一般用在对定义的字符串进行初始化
memst( "初始化字符串","初始化字符" ,"初始化字符串的内存空间长度" );
sizeof():计算字符串数组的长度
sizeof 与 strlen区别:
1 har str[11]="0123456789";//注意这里str大小因该大于等于11,应考虑'\0'在内,否则编译器会报错2 int a=strlen(str); //a=10; >>>> strlen 计算字符串的长度,以结束符 0x00 为字符串结束。3 int b=sizeof(str); //而b=11; >>>> sizeof 计算的则是分配的数组 str[11] 所占的内存空间的大小,不受里面存储的内容改变。
1 //解法二: (目前还没领悟 = =) 2 // I,当I是奇数时,它是往左走的第(I+1)/2个小球; 3 // 当I是偶数时,它是往右走的第I/2个小球 4 5 #include6 int main(){ 7 int D,I; 8 while((scanf("%d%d",&D,&I)==2) && D+I != 0){ 9 int k = 1;10 for(int i = 0;i < D-1;i++)11 if(I%2) {k*=2; I = (I+1)/2;}12 else {k = k*2+1; I /= 2; }13 printf("%d\n",k);14 }15 return 0;16 }