这个题花了我一个多钟头，也是今天八道题里唯一会做的（......-_-||||）。还有一题比较简单，物理＋数学，我没做；也许还有几题可以下手，下个月再说。唉，又要开学了。

    题目还是很好理解，有很多不同的砝码，都是3的倍数，用他们称重，左码右码。然而数据bt的大，总共有19枚砝码：2^19可以让我的电脑死机好一会儿。

    第一次，用普通的dfs，放开手搜，可想而知的挂了，本机都通不过。

    第二次，终于考虑到累加之后减不下来的问题，在本机快乐地看到了出解。然而提交依然不行。一拍脑，对称的情况（减后加不上去）没有考虑。

    第三次，修正，双手合十，念叨着「小宇宙，AC吧」。绿色的TLE无情地嘲讽着我的虔诚。

    第四次，换了一种祈祷方式。

    …………

    …………

    …………

    终于绝望了。好吧，继续我的毛概。

    在解决了新民主主义革命的基本问题之后，我突然想到了。刚才的解决路线是对的，但第四步错了。累加之后除了减不下来，还有一种情况：加了以后还加不上去。这个才是大头。

    而一开始我犯的错误在于，根本加不上去的这种情况本来就包含了减下去加不上来。前者是一般，后者是特殊，后者能剪去的情况自然不如前者。反之亦然。

    所以保存当前数之后的数之和为s[19]。sum + a[k] + s[k] < N和sum - a[k] - s[k]时停止。

    程序如下

#include <cstdio>
#include <string>

#define MX 387420489;

int a[19], s[19], n, r0[19], r1[19], l0, l1, af;

void init()
{
 l0 = 0, l1 = 0;
 af = 1;
}

void print()
{
 int i;
 if(l0 == 0) printf("-1");
 for(i = l0 - 1; i >= 0; i --)
 {
  if(i != l0 - 1) printf(" ");
  printf("%d", r0[i]);
 }
 printf("\n");
 if(l1 == 0) printf("-1");
 for(i = l1 - 1; i >= 0; i --)
 {
  if(i != l1 - 1) printf(" ");
  printf("%d", r1[i]);
 }
 printf("\n");
 printf("\n");
}

void dfs(int sum, int i)
{
 int k;
 if(sum == n)
 {
  af = 0;
  print();
 }
 if(!af) return;
 else
 {
  for(k = i + 1; k < 19; k ++)
  {
   if(sum + a[k] + s[k] < n) break;
   if(sum + a[k] - s[k] <= n)
   {
    r1[l1 ++] = a[k];
    dfs(a[k] + sum, k);
    l1 --;
   }
   if(sum - a[k] - s[k] > n) break;
   if(sum - a[k] + s[k] >= n)
   {
    r0[l0 ++] = a[k];
    dfs(sum - a[k], k);
    l0 --;
   }
  }
 }
}

int main()
{
 //freopen("in.txt", "r", stdin);
 int i, t = MX;
 for(i = 0; i < 19; i ++)
 {
  a[i] = t;
  t /= 3;
 }
 t = 0;
 for(i = 18; i >= 0; i --)
 {
  t += a[i];
  s[i] = t;
 }
 //printf("%d\n", s[0]);
 while(scanf("%d", &n) != EOF)
 {
  init();
  dfs(0, -1);
 }
 return 0;
}

评论