#UVa:11645-Bits

算出每兩位數為11在小於等於N的所有可能性,即先加上高位經過此兩位數多少次11,再判斷如果目前該兩位正好為11則低位的個數也要加上去。底下舉例:11011011。

  • 110110[11]: (110110)2 * 2^0 + 1 = (110111)2
  • 11011[01]1: (11011)2 * 2^1 = (110110)2
  • 1101[10]11: (1101)2 * 2^2 = (110100)2
  • 110[11]011: (110)2 * 2^3 + ((011)2 + 1) = (110100)2
  • 11[01]1011: (11)2 * 2^4 = (110000)2
  • 1[10]11011: (1)2 * 2^5 = (100000)2
  • [11]011011: ((011011)2 + 1) = (11100)2
  • 總和即可得解。

如果上述覺得很困難去思考,你可以換成十位數去做思考,接著再改回二位數即可。

但是本題答案會超過long long範圍,所以在做加總的時候你可以利用兩個long long去做拼裝即可得解。

C++(0.012)

/*******************************************************/
/* UVa 11645 Bits                                      */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2015/05/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

const long long int DIGITS = 1e17;

int main(){
  int testcase = 0;
  long long int N;
  while( scanf("%lld", &N) != EOF && N >= 0 ){

    long long int countH = 0, countL = 0;
    long long int digit = 1;
    long long int originalN = N;

    while( N > 1 ){
      countL += digit * (N >> 2);
      countH += countL / DIGITS;
      countL %= DIGITS;
      if( (N & 3) == 3 ){
        countL += ((digit-1) & originalN) + 1;
        countH += countL / DIGITS;
        countL %= DIGITS;
      }
      digit <<= 1;
      N >>= 1;
    }

    printf("Case %d: ", ++testcase);
    if( countH > 0 ){
      printf("%lld", countH);
      printf("%017lld\n", countL);
    }
    else{
      printf("%lld\n", countL);
    }
  }


  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料