作者按：这是去年11月份在修bug时遇到的一个问题。由于各种各样的原因，导致问题不能通过一种常规的方式来解决，只好通过这种非常规的方式来实现。当时在网上找了很多资料，看到的都是再问如何解决，或有解答也未能完全解决。东查西找加实践，总算是搞定了此问题。
    如果不是即将离开驱动领域，还真不知道什么时候会动手写它。以后也许不会再做驱动了，想想这两年，也就这点东西能对其他人有所帮助了。谨以此文献给我那惨淡的2年。

所谓ACPI meth...

Tags： 多收了三五斗

从最早因为游戏而接触的DOS到现今因为工作而用的Win7，M$的OS一用就是十几年。无论公司的开发环境还是家里的个人电脑，都是WinXP。对于那个桌面，实在有些忍无可忍了！

Tags： 码字

关于技术的东东，放下将近2年都没更新了。这里暂时不打算更新相关方面的东西了，临时转移到Dust@CNBlogs。先试用cnblogs一段时间再说。

Tags：

接二连三的骚扰我，上次害的我重装机器，一上午什么事都没做。太气愤了

哼哼，这次又害我中招。杀之～～～

http://www7.blog.163.com/article/-hAUi06S-IpC.html

Tags： 碎碎念

From USACO：

Flood fill can be performed three basic ways: depth-first, breadth-first, and breadth-first scanning. The basic idea is to find some node which has not been assigned to a component and to calculate the component which contains. The question is how to calculate the component.

In the depth-first formulation, the algorithm looks at each step through all of the neighbors of the current node, and, for those that have not been assigned to a component yet, assigns them to this component and recurses on them.

In the breadth-first formulation, instead of recursing on the newly assigned nodes, they are added to a queue.

In the breadth-first scanning formulation, every node has two values: component and visited. When calculating the component, the algorithm goes through all of the nodes that have been assigned to that component but not visited yet, and assigns their neighbors to the current component.

The depth-first formulation is the easiest to code and debug, but can require a stack as big as the original graph. For explicit graphs, this is not so bad, but for implicit graphs, such as the problem presented has, the numbers of nodes can be very large.

The breadth-formulation does a little better, as the queue is much more efficient than the run-time stack is, but can still run into the same problem. Both the depth-first and breadth-first formulations run in N + M time, where N is the number of vertices and M is the number of edges.

The breadth-first scanning formulation, however, requires very little extra space. In fact, being a little tricky, it requires no extra space. However, it is slower, requiring up to N*N + M time, where N is the number of vertices in the graph.

Pseudocode for Breadth-First Scanning

This code uses a trick to not use extra space, marking nodes to be visited as in component -2 and actually assigning them to the current component when they are actually visited.

# component(i) denotes the
# component that node i is in
 1 function flood_fill(new_component) 

 2 do
 3   num_visited = 0
 4   for all nodes i
 5     if component(i) = -2
 6       num_visited = num_visited + 1
 7       component(i) = new_component
 8       for all neighbors j of node i
 9         if component(j) = nil
10           component(j) = -2
11 until num_visited = 0 

12 function find_components 

13  num_components = 0
14  for all nodes i
15    component(node i) = nil
16  for all nodes i
17    if component(node i) is nil
18      num_components =
                 num_components + 1
19      component(i) = -2
20      flood_fill(component
                        num_components)

Running time of this algorithm is O(N ²), where N is the numbers of nodes. Every edge is traversed twice (once for each end-point), and each node is only marked once.

Tags： 算法

应该是多用于嵌入式开发中。ms linux内核中也有类似的地方用到。可惜的是这些都没接触过。笔试挂掉也是必然了。

解法：

#define OFFSET( type, field ) \

         ( ( dword ) &( ( type * ) 0 ) -> field )

Tags： 多收了三五斗

设整数i的二进制位长为n，1的个数为m：

1.很直观的一种解法：i依次& 2^0 ~ 2^(n-1), 然后判断每次的结果。依此计1的个数。其时间复杂度为O(n)

2.循环：对i做逻辑右移，判断右移后是否为0，0则停止。判断 & 1的结果；计数。该方法的时间复杂度介于O(n)～O(m)之间。目前看到的，最好的是3.中所用的方法：

3.循环： x = x & ( x - 1 ); count++; 直到x为0为止。该方法的时间复杂度是O(m)

Tags： 算法

一个很简单的办法：

int fraccompare( fraction *p, fraction *q ) {

    return p->numinator * q->denominator - p->denominator * q->numinator;

}

Tags： 算法

昨晚，微软开始发笔试通知了。如果第二天中午没有回信确认，那么将会短信或电话通知。

哎，偶到现在都还没有收到通知。估计又被bs了。

被bs并不可怕，可怕的是竟然都不给笔试机会。太不甘心了！！！

Tags： 碎碎念

基本想法：
    1  2  3  4                                 北
   ---------------> y(column)         西 ＋ 东
 1 |                                             南
 2 |
 3 |
 4 |
  x(row)
 给棋盘设定坐标系如上图所示。
     在坐标系的基础上，可以将判断每个格子是否能放置所需的时间变为O(1)。
        1。判断某一列是否被占据： columnTag[ 1...n]; 1~n分别代表第1..n列。
        2。判断"\"方向的对角线是否被占据：
           根据坐标系可以推出：
               y = x ................  (过原点那条)
               y = x +/- 1 ..........  (与上面那条相邻的两条)
               ...
               y = x +/- (n-1) ......  (过东北角、西南角的两条)
           令 a = y - x。
           则有以上各个直线方程可知：
              a 属于 [ -( n - 1 ), ( n - 1 ) ]。
           再令 a = a + n，则有 a 属于 [ 1, ( 2n - 1 ) ]。
           由此：可用数组 seTonwTag[ n * 2 + 1 ] 表示"\"方向是否被占据;
           数组下标： index = column - row + n;
       3。判断"/"方向的对角线是否被占据：
           根据坐标系可以推出：
              y = -x + (n+1)........... (过东北角和西南角的那条)
              y = -x + ((n+1) +/- 1) . (与上面那条相邻的两条)
              ...
              y = x + ((n+1) +/- (n-1)).. (过东南角、西北角的两条)
           同2。可以推导出：
              a = y + x  属于 [ 2, 2n ]
           同样可由数组 swToneTag[ maxSize * 2 + 1 ] 表示"/"方向是否被占据
           数组下标： index = column + row;
 
    在计算过程中，可以考虑对称性。从而减少一半的计算量。
 
Analysis：
  usaco上给出的判断方法一样。只是在 我用put() 和 remove()的地方代之以 ++,-- 时间上能更快一些
  另外还有一个解法用到bitmask。 不过，没仔细看

需要注意的是：在每次判断当前位置是否可以放置时，最好用上面提到的三个数组直接判断。如果把这三个数组放到一个函数中，则代价太大了。(一开始没注意，提交的时候总是超时：N＝13时，前一个用时0.808 secs，后一个用时1.344 secs)

 附原题：

……

Tags： 算法

/*
 n and m: C(n, m)
 position: 组合中的第几位
 
 取 1~n 个数中 m个数的组合：
 思路：将所有组合按照升序排列，则每个组合的各个元素满足：
    Ci <= n - m + i ( i = 1, 2, ... m )
  且每个位置元素的起始值为前一个起始值+1。
*/

void combination1( int n, int m, int position, int start, int *rst ) {
 if( position == m ) { // 最后一位
  for( int i = start; i <= n; i++ ) {
   rst[position - 1] = i;
   print( n, m, rst);
  }
  return;
 }

 for( int i = start; i <= n - m + position; i++ ) {
  rst[position - 1] = i;
  combination1( n, m, position + 1, i + 1, rst );
 }
}

……

Tags： 算法

之前一个帖子写过2种全排列的生成算法，这里再加上实现的组合数学中提到的3种生成排列的方法：

/*
 version 0.1 利用递归
*/
const int maxSize = 10;
int tag[ maxSize + 1 ] = { 0 };
int rst[ maxSize + 1 ] = { 0 };
void permute1( int index, int n ) {
 if( index == n ) {
  for( int i = 1; i <= n; i++ ) {
   if( !tag[ i ] ) {
    rst[ index ] = i;
    print();
   }
  }
  return ;
 }

 for( int i = 1; i <= n; i++ ) {
  if( !tag[ i ] ) {
   tag[ i ] = 1;
   rst[ index ] = i;
   permute1( index + 1, n );
   tag[ i ] = 0;
  }
 }
}

void print() {
 for( int i = 1; i < maxSize; i++ )
  cout << rst[i] << " ";
 cout << rst[ maxSize ] << endl;
}

/*
 version 0.2 序数法
  m = a[n-1]*(n-1)! + a[n-2]*(n-2)! + ... + a[2]*2! + a[1]*1!
 m 属于: 0 -- (n! - 1)
 m 与 (a[n-1], a[n-2], ... , a[2], a[1]) 一一对应
 用“j的右边比j小的数有a[j-1]个”来表示，则(a[n-1], a[n-2], ... , a[2], a[1])与n个元素的排列一一对应
*/

……

Tags： 算法

前两天在USACO上碰到一个求序列中算术级数的题目。因题目出在Search一章，想来应该用dfs，bfs等算法解决。但想来想去都想不出来到底该如何应用dfs and bfs。无奈只能用两个循环嵌套解决。

一开始用的是一个小循环嵌套着一个大循环，结果时间复杂度过大，超时。下面是执行结果：

Executing...
      Test 1: TEST OK [0.004 secs]
      Test 2: TEST OK [0.004 secs]
      Test 3: TEST OK [0.004 secs]
      Test 4: TEST OK [0.004 secs]
      Test 5: TEST OK [0.028 secs]
      Test 6: TEST OK [0.196 secs]
      Test 7: TEST OK [3.264 secs]

  > Run 8: Execution error: Your program (`ariprog') used more than
the allotted runtime of 5 seconds (it ended or was stopped at 6
seconds) when presented with test case 8.

      ------ Data for Run 8 ------
      22
      250
      ----------------------------

换成大循环嵌套小循环后，再次提交，哈哈，没想到竟然过了：

Executing...
      Test 1: TEST OK [0.004 secs]
      Test 2: TEST OK [0.004 secs]
      Test 3: TEST OK [0.008 secs]
      Test 4: TEST OK [0.008 secs]
      Test 5: TEST OK [0.016 secs]
      Test 6: TEST OK [0.1 secs]
      Test 7: TEST OK [1.124 secs]
      Test 8: TEST OK [2.54 secs]
      Test 9: TEST OK [2.224 secs]

从时间上看，后者比前者用的时间要少很多。改变嵌套方式前后的计算量是一致的，但后者所用的时间却相对较小。原因……

以后写代码要注意了

Tags： 算法

From usaco:

void numbconv(char *s, int n, int b)
{
    int len;

    if(n == 0) {
        strcpy(s, "");
        return;
    }

    /* figure out first n-1 digits */
    numbconv(s, n/b, b);

    /* add last digit */
    len = strlen(s);
    s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
    s[len+1] = '\0';
}

偶的解法：（嘿，比较而言，有点丑）

void tenToN(int base, int number, char rst[], int &rstLength) {
    int remainder;
    int quotient = number;
    rstLength = 0;
 
    while( quotient != 0 ) {
        quotient = number / base;
        remainder = number % base;
        number = quotient;
        rst[rstLength++] = remainder >= 10 ? ('A' + remainder - 10) : (remainder + '0');
    }
    for( int i = 0; i < rstLength / 2; i++){
        char ch = rst[i];
        rst[i] = rst[rstLength - i - 1];
        rst[rstLength - i - 1] = ch; 
    }  
    rst[rstLength] = '\0';
}

Tags： 算法

今天在USACO上做题，又看到了一种求全排列的方法(肯定是比较old的的，不过偶是新人，自己SP一下自己。^^)

void permute( int *s, int depth, int n) {

  if( depth == n ) {
    for( int i = 0; i < n; i++ )
      cout << s[i] << " ";
    cout << endl;
  }

  for( int i = depth; i < n; i++ ) {
    int t = s[i]; s[i] = s[depth]; s[depth] = t;
    permute(s, depth + 1, n);
    t = s[i]; s[i] = s[depth]; s[depth] = t;
  }
}

之前屡试不爽的求排列的方法：

int src[4] = { 1, 2, 3, 4 };
int tag[4] = { 0 };
int rst[4];

void permute( int depth, int n ){
  if( depth == n - 1 ) {
    for( int i = 0; i < n; i++ ) {
      if( !tag[i] ) {
        rst[depth] = src[i];
        for( int j = 0; j < n; j++ )
          cout << rst[j] << " ";
        cout << endl;
      }
    }
  }

  for( int i = 0; i < n; i++ ) {
    if( !tag[i] ) {
      tag[i] = 1;
      rst[depth] = src[i];
      permute( depth + 1, n );
      tag[i] = 0;
    }
  }
}

Tags： 算法