这题原来如此简单````根本用不到搜索,更谈不上剪枝..可在那时,却害的我肝肠寸断,为伊消得人憔悴.....可叹一位如花似玉的少年,就这样被zoj的Monthly吓的花容失色,颤抖抖,惊颤颤...

    (正色道)此题(参见前文)只需把数改成三进制,不断的「借位」进位即可.

    如6,即为2,0 == 1,-1,0;

    35,即是1,0,2,2 == 1,1,0,-1;

    如此这般,这般如此,1处取加,-1处取减,可爱的ac就在你的眼前.

#include <cstdio>
#include <string>

int b[19], n, l;

void pt()
{
 int af = 0, bf = 0, i, x = 1;
 for(i = 0; i <= l; i ++)
 {
  if(b[i] == -1)
  {
   af = 1;
   if(bf)
    printf(" ");
   printf("%d", x);
   bf = 1;
  }
  x *= 3;
 }
 if(!af)
  printf("-1");
 printf("\n");
 af = 0, bf = 0, x = 1;
 for(i = 0; i <= l; i ++)
 {
  if(b[i] == 1)
  {
   af = 1;
   if(bf)
    printf(" ");
   printf("%d", x);
   bf = 1;
  }
  x *= 3;
 }
 if(!af)
  printf("-1");
 printf("\n");
}

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) != EOF)
 {
  memset(b, 0, sizeof(b));
  
  int t = n, i;
  l = 0;
  while(t)
  {
   b[l ++] = t % 3;
   t /= 3;
  }
  //pb();
  for(i = 0; i < l; i ++)
  {
   if(b[i] == 3)
   {
    b[i] = 0;
    b[i + 1] ++;
   }
   if(b[i] == 2)
   {
    b[i] = -1;
    b[i + 1] ++;
   }
  }
  //pb();
  pt();
  printf("\n");
 }
 return 0;
}

评论