2012-08-18 10:32:53Morris
[ZJ][BIT] a484. 美麗風景遞增之路
內容 ：
婷婷現在在地圖的左上角那格，她想要走到地圖的右下角
走的過程中只能向右或向下，這樣才能節省腳力
每一格都有一個風景美麗值
在婷婷走的過程中，可以選擇一些格子停下來欣賞風景
基於先苦後甘的原則，婷婷希望她停下來的格子的美麗值嚴格遞增
婷婷想問你，總共有多少種走法呢？
另外，婷婷至少要欣賞過風景一次，這樣才不虛此行
輸入說明
：
第一行是測資數T (T<=20)
接下來每筆測資有兩個數R、C代表地圖的大小
然後R列，每列有C個數字，代表這張地圖每格的美麗值
其中R，C，美麗值都是非負整數且不超過1000
輸出說明
：
輸出滿足婷婷要求的方法數k
因為k可能很大，所以請輸出k mod 1000000007的答案
範例輸入
：
2 2 2 1 2 3 4 2 1 2 1
範例輸出 ：
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;
}
先把方格內的數字由小排到大, 次排序 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;
}