IAML's Blog

Find passion in coding
poj3411 Paid Roads

poj3373 Changing Digits

IAmL posted @ 2009年5月02日 07:22 in 解题报告 with tags poj3373 Changing Digits BFS 解题报告 , 3681 阅读

经过几天不屈不挠地思考这一题，最后还是不会，主要是想不到判重的方法。看了解题报告，正确来说，是代码。然后发现一直想不通的问题竟然是那么简单地被解决（用余数判重）。这个涉及到模n同余的特性。另外的两点就是搜索的顺序和高精度。搜索的话要按照以下规则：

1.从最高位开始，逐渐往低位搜；

2.先搜小于原来的数的，然后搜大于原来的数的；

3.先搜一位，然后两位，如此类推。

这样一来就可以保证第一个搜到的答案就是要求的答案。但是就这样直接算的话，还是会超时。所以需要优化一下。主要优化的地方就是求大数的余数的方法。

 

后记：

1.以后涉及大数的搜索，可以考虑用余数来表示状态。

＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

 

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. #define len 101
  6. #define Max 10001
  7. /*
  8. remainder和q组成一个队列，表示当前的余数和数；
  9. w[i][j]表示数字i在第j位上是对应k的余数
  10. */
  11. int k, head, tail, l, w[11][len];
  12. bool found, hash[Max];
  13.  
  14. struct longlong
  15. {
  16.         int p[len], sp;
  17.         void convert(char *n);
  18.         int operator%(int d);
  19.         int& operator[](int i){return p[i];}
  20.         void clear();
  21.         void print() const;
  22. }in, ans, tmp;
  23.  
  24. struct Qnode
  25. {
  26.         longlong num;
  27.         int t, l;
  28.         int& operator[](int i){return num[i];}
  29. }q[Max];
  30.  
  31. void longlong::convert(char *n)
  32. {
  33.         int i, size;
  34.  
  35.         size = strlen(n);
  36.  
  37.         for (i = size - 1, sp = len - 1; i >= 0; i--, sp--)     p[sp] = n[i] - '0';
  38.        
  39.         sp++;
  40. }
  41.  
  42. int longlong::operator %(int d)
  43. {
  44.         int remainder = 0, sum, now = sp;
  45.  
  46.         while (now < len)
  47.         {
  48.                 sum = remainder;
  49.                 do
  50.                 {
  51.                         sum = 10 * sum + p[now++];
  52.                 }while (sum < d && now < len);
  53.  
  54.                 remainder = sum % d;
  55.         }
  56.  
  57.         return remainder;
  58. }
  59.  
  60. void longlong::clear()
  61. {
  62.         memset(p, 0, sizeof(p));
  63.         sp = len - 1;
  64. }
  65.  
  66. void longlong::print() const
  67. {
  68.         int i;
  69.  
  70.         for (i = sp; i < len; i++) cout << p[i];
  71.  
  72.         cout << endl;
  73. }
  74.  
  75. //通过递归有顺序地搜索,一次回溯只改变一位，从而保证第一个解为最优解
  76. //用余数来判重
  77. void backtrack(int i)
  78. {
  79.         if (found)      return;
  80.  
  81.         int t; 
  82.         for (tmp[i] = 0; tmp[i] < 10; tmp[i]++)
  83.         {
  84.                 //no leading zero
  85.                 if (!tmp[i] && i == tmp.sp) continue;
  86.  
  87.                 if (tmp[i] == q[head][i])
  88.                 {
  89.                         if (i < len - 1) backtrack(i + 1);
  90.                         continue;
  91.                 }       
  92.  
  93.                 t = (q[head].t + w[tmp[i]][i] - w[q[head][i]][i] + k) % k;
  94.  
  95.                 if (!t && !found)
  96.                 {
  97.                         found = true;
  98.                         ans = tmp;
  99.  
  100.                         return;
  101.                 }
  102.                 else
  103.                 {
  104.                         if (t && !hash[t])
  105.                         {
  106.                                 hash[t] = true;
  107.                                 q[tail].t = t;
  108.                                 q[tail++].num = tmp;
  109.                         }
  110.                 }
  111.         }
  112.  
  113.         tmp[i] = q[head][i];
  114. }
  115.  
  116. void BFS()
  117. {
  118.         //initialize
  119.         int i, j;
  120.         for (i = 0; i < 10; i++)
  121.         {
  122.                 w[i][len - 1] = i % k;
  123.                 for (j = len - 2; j >= in.sp; j--) w[i][j] = w[i][j + 1] * 10 % k;
  124.         }
  125.                
  126.         memset(hash, 0, sizeof(hash));
  127.         found = false;
  128.         head = tail = l = 0;
  129.        
  130.         //solve
  131.         int t, sp = in.sp;
  132.  
  133.         t = in % k;
  134.        
  135.         if (!t)
  136.         {
  137.                 ans = in;
  138.                 return;
  139.         }
  140.         else if (in.sp == len - 1)
  141.         {
  142.                 ans.sp = in.sp;
  143.                 ans[ans.sp] = 0;
  144.                 return;
  145.         }
  146.  
  147.         q[tail].num = in;
  148.         q[tail].l = 0;
  149.         q[tail++].t = t;
  150.         hash[t] = true;
  151.  
  152.         while (head < tail)
  153.         {
  154.                 tmp = q[head].num;
  155.                 q[head].l++;
  156.  
  157.                 if (q[head].l < 6) backtrack(sp);             
  158.                 if (found) return;
  159.  
  160.                 head++;
  161.         }                     
  162. }
  163.  
  164. int main()
  165. {
  166.         char n[101];
  167.                
  168.         while (scanf("%s", n) != EOF)
  169.         {
  170.                 scanf("%d", &k);
  171.  
  172.                 in.convert(n);
  173.                 BFS();
  174.                 ans.print();
  175.                 ans.clear();
  176.                 tmp.clear();
  177.         }
  178.  
  179.         return 0;
  180. }
  181.  
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter