Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

In Jollybee Chess Championship 2008, there are a number of players who have withdrawn themselves from the championship of 64 players (in this problem, we generalized it into 2^N players). Due to the nature of the competition, which is a regular knock-out tournament, and also the short notice of the withdrawals, some matches had been walkover matches (also known as a w/o, a victory due to the absent of the opponent).

If both players are available then there will be a normal match, one of them will advance to the next phase. If only one player is available then there will be a walkover match, and he/she will automatically advance. If no player is available then there will be no match.

In the left figure, the player #3 and #4 are withdrawn from the tournament, leaving a total of one w/o match (at match #3).

Given the list of players who withdraw right before the tournament start, calculate how many w/o matches to happen in the whole tournament, assuming that all of the remaining players play until the end of the tournament (winning or knocked-out).

Input 

The first line of input contains an integer T , the number of test cases to follow. Each case begins with two integers, N (1N10) and M (0M2^N) . The next line contains M integers, denoting the players who have withdrawn themselves right before the tournament. The players are numbered from 1 to 2^N , ordered by their position in the tournament draw.

Output 

For each case, print in a single line containing the number of walkover matches.

Sample Input 

3 
2 2 
3 4 
3 5 
1 2 3 4 5 
2 1
2

Sample Output 

1 
2 
1

---

題目描述：
有些玩家一開始就投降了，在有 2^n 個玩家的互相對打的樹狀圖中，
有幾場是完整的比賽(雙方都沒有投降)

一共會比 2^n - 1 場。

題目解法：
直接模擬即可。

#include <stdio.h>
#include <string.h>

int main() {
    int testcase;
    int n, m, i, x;
    int tree[8192];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        int M = 1<<n;
        memset(tree, 0, sizeof(tree));
        for(i = 0; i < m; i++) {
            scanf("%d", &x), x--;
            tree[M+x] = -1;
        }
        int wo = 0;
        for(i = M-1; i >= 1; i--) {
            int l = tree[i<<1], r = tree[i<<1|1];
            if(l == -1 && r == -1)
                tree[i] = -1;
            else if(l == 0 && r == 0) {}
            else {
                wo++;
            }
        }
        printf("%d\n", wo);
    }
    return 0;
}