#UVa：11038－How Many O’s?

令f(x)為求0~x之間0的個數有多少，即可將題目換化成[m,n]之間0的個數=f(n)-f(m-1)。接著就來思考該如何解決0~x之間0的個數的問題，我們將x分為各個位數去用排列組合的方式算其出現0的個數，並假設x的第k位數為xk。若xk不等於0的話，x的第k位數出現0的情況就會是(比xk高位的數字)*10^k。而xk等於0的話，x的第k位數出現0的情況就會是(比xk高位的數字-1)*10^k + (比xk低位的數字+1)。把每個位數依照上述公式算出並加總，再加上會忽略掉的0即是f(x)的答案。這樣即可得解。

Ex.32053

• 個位數會出現0的情況(不包含0)=3205*10^0=3205 (Ex. 10、20、30、……、32040、32050)
• 十位數會出現0的情況=320*10^1=3200 (Ex. 100~109、200~209、300~309、……、31900~31909、32000~32009)
• 百位數會出現0的情況=(32-1)*10^2+(53+1)=3100+54=3154 (Ex. 1000~1099、2000~2099、3000~3099、……、31000~31099、32000~32053)
• 千位數會出現0的情況=3*10^3=3000 (Ex. 10000~10999、20000~20999、30000~30999)

總和=個位數會出現0的情況(不包含0)+十位數會出現0的情況+百位數會出現0的情況+千位數會出現0的情況+是0的情況=3205+3200+3154+3000+1=12560

C++(0.012)

/*******************************************************/
/* UVa 750 8 Queens Chess Problem                      */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/01/18                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int n;
void backtracking( int, int*, int*, int*, int*, int* );
int main(){
  int N;
  int row, col, array[8];
  bool blank_line;
  while( scanf( "%d", &N ) != EOF ){
    blank_line = 0;
    for( int i = 0 ; i < N ; i++ ){
      scanf( "%d%d", &row, &col );
      row--, col--;
      if( blank_line ) printf( "\n" );
      printf( "SOLN COLUMN\n" );
      printf( " # 1 2 3 4 5 6 7 8\n" );
      printf( "\n" );
      blank_line = 1;
      int rowput[8] = {0}, colput[8] = {0}, leftslash[15] = {0}, rightslash[15] = {0};
      rowput[row] = 1;
      colput[col] = 1;
      leftslash[row+col] = 1;
      rightslash[row-col+7] = 1;
      n = 0;
      array[col] = row;
      backtracking( 0, array, rowput, colput, leftslash, rightslash );
    }
  }
  return 0;
}

void backtracking( int i, int array[], int rowput[], int colput[], int leftslash[] , int rightslash[] ){
  if( i == 8 ){
    printf( "%2d ", ++n );
    for( int j = 0 ; j < 8 ; j++ ){
      if( j ) printf( " " );
      printf( "%d", array[j]+1 );
    }
    printf( "\n" );
    return;
  }
  if( colput[i] ){
    backtracking( i+1, array, rowput, colput, leftslash, rightslash );
    return;
  }
  for( int j = 0 ; j < 8 ; j++ ){
    if( rowput[j] || leftslash[j+i] || rightslash[j-i+7] )
      continue;
    rowput[j] = 1;
    leftslash[i+j] = 1;
    rightslash[j-i+7] = 1;
    array[i] = j;
    backtracking( i+1, array, rowput, colput, leftslash, rightslash );
    rowput[j] = 0;
    leftslash[i+j] = 0;
    rightslash[j-i+7] = 0;
  }
}