2077759 2006-09-23 21:04:50 Accepted 2759 C++ 00:00.11 440K Achilles     这个题花了我一个多钟头，也是今天八道题里唯一会做的（......-_-||||）。还有一题比较简单，物理＋数学，我没做；也许还有几题可以下手，下个月再说。唉，又要开学了。     题目还是很好理解，有很多不同的砝码，都是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;}

评论