[ZJ][BIT] a484. 美麗風景遞增之路＠Morris' Blog

2012-08-18 10:32:53| 人氣810| 回應0 | 上一篇 | 下一篇

[ZJ][BIT] a484. 美麗風景遞增之路

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

內容：

婷婷現在在地圖的左上角那格，她想要走到地圖的右下角

走的過程中只能向右或向下，這樣才能節省腳力

每一格都有一個風景美麗值

在婷婷走的過程中，可以選擇一些格子停下來欣賞風景

基於先苦後甘的原則，婷婷希望她停下來的格子的美麗值嚴格遞增

婷婷想問你，總共有多少種走法呢？

另外，婷婷至少要欣賞過風景一次，這樣才不虛此行

輸入說明：

第一行是測資數T (T<=20)

接下來每筆測資有兩個數R、C代表地圖的大小

然後R列，每列有C個數字，代表這張地圖每格的美麗值

其中R，C，美麗值都是非負整數且不超過1000

輸出說明：

輸出滿足婷婷要求的方法數k

因為k可能很大，所以請輸出k mod 1000000007的答案

範例輸入： help

範例輸出：

11
2

提示：

第一組測試資料共有下列11種走法：
1, 2, 3, 4, 12, 13, 14, 24, 34, 124 以及 134.

第二組測試資料共有下列2種走法：
2, 1

※婷婷不一定要在最左上角或最右下角的格子停下來

出處：

TCPC' 08 Increase (管理：david942j)

先把方格內的數字由小排到大, 次排序 x 由大到小, y 由大到小,
然後逐步放入, 查詢 C[1][1] ~ C[xi][yi] 的總合 sum,
並且更新 C[xi][yi] += sum

這裡有三個版本,

壓縮記憶體 ~

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int set;
} ele;
ele D[1000005];
int cmp(const void *i, const void *j) {
    static ele *a, *b;
    static int va, vb, xa, xb, ya, yb;
    a = (ele *)i, b = (ele *)j;
    va = (a->set>>20)&1023;
    vb = (b->set>>20)&1023;
    if(va != vb)
        return va - vb;
    xa = (a->set>>10)&1023;
    xb = (b->set>>10)&1023;
    if(xa != xb)
        return xb - xa;
    ya = a->set&1023;
    yb = b->set&1023;
    return yb - ya;
}
int BIT[1001][1001], lowbit[1001];
int t, R, C, i, j, v;
int query(int x, int y) {
    int sum = 0, i, j;
    for(i = x; i > 0; i -= lowbit[i]) {
        for(j = y; j > 0; j -= lowbit[j]) {
            sum += BIT[i][j];
            if(sum >= 1000000007)
                sum -= 1000000007;
        }
    }
    return sum;
}
void modify(int x, int y, int v) {
    int i, j;
    for(i = x; i <= R; i += lowbit[i]) {
        for(j = y; j <= C; j += lowbit[j]) {
            BIT[i][j] += v;
            if(BIT[i][j] >= 1000000007)
                BIT[i][j] -= 1000000007;
        }
    }
}
int main() {
    for(i = 0; i <= 1000; i++)
        lowbit[i] = i&(-i);
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &R, &C);
        int m = 0, x, y;
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                scanf("%d", &v);
                D[m].set = (v<<20)|(i<<10)|j;
                m++;
            }
        }
        qsort(D, m, sizeof(ele), cmp);
        for(i = 0; i <= R; i++)
            for(j = 0; j <= C; j++)
                BIT[i][j] = 0;
        for(i = 0; i < m; i++) {
            x = (D[i].set>>10)&1023, y = D[i].set&1023;
            int tmp = query(x+1, y+1);
            tmp++;
            modify(x+1, y+1, tmp);
        }
        printf("%d\n", query(R, C));
    }
    return 0;
}

基礎 bit

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    short x, y, v;
} ele;
ele D[1000005];
int cmp(const void *i, const void *j) {
    ele *a, *b;
    a = (ele *)i, b = (ele *)j;
    if(a->v != b->v)
        return a->v - b->v;
    if(a->x != b->x)
        return b->x - a->x;
    return b->y - a->y;
}
int BIT[1001][1001], lowbit[1001];
int t, R, C, i, j, v;
int query(int x, int y) {
    int sum = 0, i, j;
    for(i = x; i > 0; i -= lowbit[i]) {
        for(j = y; j > 0; j -= lowbit[j]) {
            sum += BIT[i][j];
            if(sum >= 1000000007)
                sum -= 1000000007;
        }
    }
    return sum;
}
void modify(int x, int y, int v) {
    int i, j;
    for(i = x; i <= R; i += lowbit[i]) {
        for(j = y; j <= C; j += lowbit[j]) {
            BIT[i][j] += v;
            if(BIT[i][j] >= 1000000007)
                BIT[i][j] -= 1000000007;
        }
    }
}
int main() {
    for(i = 0; i <= 1000; i++)
        lowbit[i] = i&(-i);
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &R, &C);
        int m = 0;
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                scanf("%d", &v);
                D[m].x = i, D[m].y = j, D[m].v = v;
                m++;
            }
        }
        qsort(D, m, sizeof(ele), cmp);
        for(i = 0; i <= R; i++)
            for(j = 0; j <= C; j++)
                BIT[i][j] = 0;
        for(i = 0; i < m; i++) {
            int tmp = query(D[i].x+1, D[i].y+1);
            tmp++;
            modify(D[i].x+1, D[i].y+1, tmp);
        }
        printf("%d\n", query(R, C));
    }
    return 0;
}

zkw 線段樹, 可惜因為常數關係, 效率剛好 TLE 去哩

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int x, y, v;
} ele;
ele D[1000005];
int cmp(const void *i, const void *j) {
    ele *a, *b;
    a = (ele *)i, b = (ele *)j;
    return a->v - b->v;
}
struct {
    int subtree[2050];
} mainTree[2050];
int Mmain, Msub;
void subbuild(int k) {
    int i;
    for(i = 2*Msub-1; i > 0; i--)
        mainTree[k].subtree[i] = 0;
}
void build() {
    int i;
    for(i = 2*Mmain; i > 0; i--)
        subbuild(i);
}
void modify(int x, int y, int v) {
    mainTree[x+Mmain].subtree[y+Msub] += v;
    static int s, t;
    for(t = (x+Mmain); t > 0; t >>= 1) {
        for(s = (y+Msub)>>1; s > 0; s >>= 1) {
            mainTree[t].subtree[s] = mainTree[t].subtree[s<<1] +
                    mainTree[t].subtree[s<<1|1];
        }
    }
}
int subquery(int k, int lc, int rc) {
    static int s, t, sum;
    sum = 0;
    for(s = lc+Msub-1, t = rc+Msub+1; (s^t) != 1;) {
        if(~s&1)
            sum += mainTree[k].subtree[s^1];
        if(t&1)
            sum += mainTree[k].subtree[t^1];
        s >>= 1, t >>= 1;
    }
    return sum;
}
int query(int lr, int rr, int lc, int rc) {
    static int s, t, sum;
    sum = 0;
    for(s = lr+Mmain-1, t = rr+Mmain+1; (s^t) != 1;) {
        if(~s&1)
            sum += subquery(s^1, lc, rc);
        if(t&1)
            sum += subquery(t^1, lc, rc);
        s >>= 1, t >>= 1;
    }
    return sum;
}
int main() {
    int t, R, C, i, j, v;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &R, &C);
        int m = 0;
        for(i = 0; i < R; i++) {
            for(j = 0; j < C; j++) {
                scanf("%d", &v);
                D[m].x = i, D[m].y = j, D[m].v = v;
                m++;
            }
        }
        qsort(D, m, sizeof(ele), cmp);
        for(Mmain = 1; Mmain < R+2; Mmain <<= 1);
        for(Msub = 1; Msub < C+2; Msub <<= 1);
        build();
        for(i = 0; i < m; i++) {
            int tmp = query(1, D[i].x+1, 1, D[i].y+1);
            tmp++;
            modify(D[i].x+1, D[i].y+1, tmp);
        }
        printf("%d\n", query(1, R, 1, C));
    }
    return 0;
}

我要檢舉

#a484#美麗風景遞增之路

台長： Morris

您可能對以下文章有興趣

d915. 3. 洗街車路線問題

[ZJ] d537. 第四題：染色遊戲

[ZJ][BFS] d373. 5. 乳酪的誘惑

d908. 4. 最佳路徑

人氣(810) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][Math] a348. 1. 貪食蛇
此分類上一篇:[ZJ][DP] a365. 3. 新井字遊戲

回應(0)