[NPSC][BIT] a641. B. 蚯蚓疊積木＠Morris' Blog

2013-04-14 09:29:39| 人氣617| 回應0 | 上一篇 | 下一篇

[NPSC][BIT] a641. B. 蚯蚓疊積木

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

還記得老蚯的那些寶物嗎？隨著蚯蚓們挖到的寶物越來越多，蚯蚓的公用倉庫越疊越高，老蚯發現自己竟愛上了疊東西。為了滿足自己疊東西的欲望，老蚯從寶物堆中找出了許多大小不一的積木，不停的疊來疊去。

然而，在疊了七七四十九年後，單純的疊積木再也無法滿足老蚯了。為了讓疊積木變得更有趣，老蚯決定出個考題考考自己：依照某個順序每次拿起一個積木，一一決定是否將這個積木疊到積木塔上，並使得最後積木塔上疊的積木最多。當然，為了要疊出一個穩固的積木塔，任何一個積木都只能疊在一個比他自己大的積木上。

幸運，也不幸的，因為老蚯天生對積木的直覺，這個問題在老蚯嘗試玩了三次以後就變得簡單無聊。所以老蚯決定問問自己一個更有挑戰性的問題：有哪些積木如果被規定了不准疊到積木塔上，會使得能疊到積木塔上的最多積木數量減少？

輸入說明：

輸入檔的第一行有一個正整數T (T<=6000)，表示接下來總共有幾筆測試資料。

每組測試資料的第一行的開頭有一個正整數N (1<=N<=200000) 代表蚯蚓打算依序拿起N 個積木，同一行接著有N 個整數S_i (1<=S_i<=N)，代表那N 個積木的大小，所有積木的大小都是不同的。我們保證有99% 的測試資料N<=1000 。

輸出說明：

為了輸出方便，我們先定義一個雜湊函數hash，能夠將一個長度為size 的整數序列轉換成一個整數。

int hash(int numbers[], int size){

int value = 0, i;

for(i = 0; i < size; i++){

value ^= (numbers[i] + i + 1);

}

return value;

}

對於每一筆測試資料，請輸出中間用一個空白分隔的兩個整數A,B。A 代表有幾個積木若被規定不准放到積木塔上，會使得能疊到積木塔上的最多積木數量減少。B代表將那A 個積木的索引值(依據輸入順序從1 開始編號到N) 從小排到大後雜湊的結果。

範例輸入：

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

範例輸出：

0 0
4 4
3 14

提示：

出處：

NPSC 2012 高中組決賽 (管理：xavier13540)

題目要求最長遞增子序列，而哪些剃除掉後，會使得最長遞增子序列。
意即將所有最長遞增子序列列出後，該數值出現在所有最長遞增子序列的所有相同位置。

利用 BIT 可以找到遞增序列。
if (A[i] < A[j]) dp[j] = max(dp[j], dp[i]+1);
等價在 [0, A[j]-1] 中查找最大值，利用掃描線的做法。

最後會得到 ____L____O____R____
O是該元素所在位置，L是可以接到 O 的最大 LIS，R是從 O開始的最大 LIS。
只要 L.length+R.length+1 == all.LIS 就是在 LIS 中，
記錄該元素所在的位置，最後再掃描在位置是不是唯一。

#include <stdio.h>
#include <string.h>
#define max(x,y) ((x)>(y)?(x):(y))
void modify(int idx, int l, int val, int T[]) {
    while(idx <= l) {
        T[idx] = max(T[idx], val);
        idx += idx&(-idx);
    }
}
int query(int idx, int T[]) {
    int r = 0;
    while(idx) {
        r = max(r, T[idx]);
        idx -= idx&(-idx);
    }
    return r;
}
int l[200005], r[200005], bit[200005];
int A[200005], pos[200005];
int main() {
    int t, n, i, x, y;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = n-1; i >= 0; i--) {
            scanf("%d", &A[i]);
            bit[i+1] = 0;
            pos[i] = 0;
        }
        for(i = 0; i < n; i++) {
            x = n-A[i]+1;
            y = query(x, bit);
            l[i] = y;
            modify(x, n, y+1, bit);
        }
        int lis = query(n, bit);
        for(i = 0; i <= n; i++)
            bit[i] = 0;
        for(i = n-1; i >= 0; i--) {
            x = A[i];
            y = query(x, bit);
            r[i] = y;
            modify(x, n, y+1, bit);
        }
        for(i = 0; i < n; i++) {
            if(l[i]+r[i]+1 == lis) {
                pos[l[i]]++;
            }
        }
        int cnt = 0, ans = 0;
        for(i = n-1; i >= 0; i--) {
            if(l[i]+r[i]+1 == lis) {
                if(pos[l[i]] == 1) {
                    //printf("%d %d +\n", n-i, cnt+1);
                    cnt++;
                    ans ^= n-i+cnt;
                }
            }
        }
        printf("%d %d\n", cnt, ans);
        //printf("%d\n", lis);
    }
    return 0;
}

我要檢舉

#BIT#a641#B. 蚯蚓疊積木

台長： Morris

您可能對以下文章有興趣

b207. F. 世界盃

[ZJ][KM算法] d210. 老問題

[NPSC][方格法] b256. E. 大風吹

b043. B. 踩地雷回來了

人氣(617) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類上一篇:[NPSC][AC自動機DP] a640. A. 曉涵的紙牌遊戲

回應(0)