Loading...

2018/5/5 数据结构测试

check评论:3 条 remove_red_eye浏览量:851 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-06

数据和题目最后发
T1:(matsum)
正解1:二维线段树
由于博主太菜了,不会,于是就有了下列方法
正解2:二维树状数组
这个就好写很多了,由于评测机太差这次考试卡内存,所以博主的代码只拿了70
直接放100分代码:

#include <cstdio>

int n, m, q;

struct Case1 {
    int bit[100010];
    void modify( int p, int d ) {
        for( int i = p; i <= m; i += i & -i )
            bit[i] += d;
    }
    int query( int r ) {
        int rt = 0;
        for( int i = r; i; i -= i & -i ) 
            rt += bit[i];
        return rt;
    }
    int query( int l, int r ) {
        return query(r) - query(l-1);
    }
    void solve() {
        while (q--) {
            char ss[100];
            scanf( "%s", ss );
            if( ss[0] == 'm' ) {
                int x, y, d;
                scanf( "%d%d%d", &x, &y, &d );
                modify( y, d );
            } else {
                int x1, y1, x2, y2;
                scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
                printf( "%d\n", query(y1,y2) );
            }
        }
    }
}case1;
struct Case2 {
    int bit[1100][1100];
    void modify( int x, int y, int d ) {
        for( int i = x; i <= n; i += i & -i )
            for( int j = y; j <= m; j += j & -j )
                bit[i][j] += d;
    }
    int query( int x, int y ) {
        int rt = 0;
        for( int i = x; i; i -= i & -i )
            for( int j = y; j; j -= j & -j )
                rt += bit[i][j];
        return rt;
    }
    int query( int x1, int y1, int x2, int y2 ) {
        return query(x2,y2) - query(x1-1,y2) - query(x2,y1-1) + query(x1-1,y1-1);
    }
    void solve() {
        while(q--) {
            char ss[100];
            scanf( "%s", ss );
            if( ss[0] == 'm' ) {
                int x, y, d;
                scanf( "%d%d%d", &x, &y, &d );
                modify( x, y, d );
            } else {
                int x1, y1, x2, y2;
                scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
                printf( "%d\n", query(x1,y1,x2,y2) );
            }
        }
    }
}case2;

int main() {
    freopen ( "matsum.in", "r", stdin ) ;
    freopen ( "matsum.out", "w", stdout ) ;
    scanf( "%d%d%d", &n, &m, &q );
    if( n == 1 )
        case1.solve();
    else
        case2.solve();
}

T2:(segsum)
正解:建线段树,用结构体,一棵抵三棵
累断手的解法:建三棵线段树
还是发正解

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;

struct Info {
    int vmin, vmax; 
    long long vsum;
    Info(){}
    Info( int vmin, int vmax, long long vsum ):vmin(vmin),vmax(vmax),vsum(vsum){}
};
Info merge( const Info &r, const Info &s ) {
    return Info( min(r.vmin,s.vmin), max(r.vmax,s.vmax), r.vsum + s.vsum );
}
struct Node {
    Info info;
    int delta;
    Node *ls, *rs;
    void pushdown( int lf, int rg ) {
        if( delta ) {
            int mid = (lf + rg) >> 1;
            ls->delta += delta;
            ls->info.vmin += delta;
            ls->info.vmax += delta;
            ls->info.vsum += 1LL * (mid - lf + 1) * delta;
            rs->delta += delta;
            rs->info.vmin += delta;
            rs->info.vmax += delta;
            rs->info.vsum += 1LL * (rg - mid) * delta;
            delta = 0;
        }
    }
    void update() {
        info = merge( ls->info, rs->info );
    }
}pool[N * 3], *tail=pool, *root;

int n, q;
int aa[N];

Node *build( int lf, int rg ) {
    Node *nd = ++tail;
    if( lf == rg ) {
        nd->info = Info(aa[lf],aa[lf],aa[lf]);
        nd->delta = 0;
    } else {
        int mid = (lf + rg) >> 1;
        nd->delta = 0;
        nd->ls = build( lf, mid );
        nd->rs = build( mid+1, rg );
        nd->update();
    }
    return nd;
}
void modify( Node *nd, int lf, int rg, int L, int R, int d ) {
    if( L <= lf && rg <= R ) {
        nd->delta += d;
        nd->info.vmax += d;
        nd->info.vmin += d;
        nd->info.vsum += d * (rg - lf + 1);
        return;
    }
    int mid = (lf + rg) >> 1;
    nd->pushdown(lf,rg);
    if( L <= mid )
        modify( nd->ls, lf, mid, L, R, d );
    if( R > mid )
        modify( nd->rs, mid+1, rg, L, R, d );
    nd->update();
}
Info query( Node *nd, int lf, int rg, int L, int R ) {
    if( L <= lf && rg <= R ) 
        return nd->info;
    int mid = (lf + rg) >> 1;
    nd->pushdown(lf,rg);
    if( R <= mid ) {
        return query( nd->ls, lf, mid, L, R );
    } else if( L > mid ) {
        return query( nd->rs, mid+1, rg, L, R );
    } else {
        return merge(
            query( nd->ls, lf, mid, L, R ),
            query( nd->rs, mid+1, rg, L, R ) );
    }
}
int main() {
    freopen ( "segsum.in", "r", stdin ) ;
    freopen ( "segsum.out", "w", stdout ) ;
    
    scanf( "%d%d", &n, &q );
    for( int i = 1; i <= n; i++ )
        scanf( "%d", aa + i );
    root = build( 1, n );
    while( q-- ) {
        char ss[100];
        int l, r, d;
        scanf( "%s", ss );
        if( ss[0] == 'q' ) {
            scanf( "%d%d", &l, &r );
            Info info = query( root, 1, n, l, r );
            std :: cout << info.vmin << ' ' << info.vmax << ' ' << info.vsum  << '\n';
        } else {
            scanf( "%d%d%d", &l, &r, &d );
            modify( root, 1, n, l, r, d );
        }
    }
}

T3:(matgcd)
正解1:还是二维线段树还是不会
正解2:一看静态区间就知道是倍增啦qwq
倍增100分:

#include <cstdio>
#define RG register

const int N = 510;[matsum.zip][1]
const int P = 9;

int n, m, q;
int st[N][N][P+1][P+1];
int logb[N];

inline int gcd( int a, int b ) {
    return b == 0 ? a : gcd(b,a%b);
}
void init() {
    for( RG int pi = 0; pi <= P; pi++ )
        for( RG int pj = 0; pj <= P; pj++ ) {
            if( pi == 0 && pj == 0 ) continue;
            for( RG int i = 1; i + (1<<pi) - 1 <= n; i++ )
                for( RG int j = 1; j + (1<<pj) - 1 <= m; j++ ) {
                    if( pi == 0 ) {
                        st[i][j][pi][pj] = gcd( st[i][j][pi][pj-1], st[i][j + (1<<(pj-1))][pi][pj-1] );
                    } else {
                        st[i][j][pi][pj] = gcd( st[i][j][pi-1][pj], st[i + (1<<(pi-1))][j][pi-1][pj] );
                    }
                }
        }
}
inline int query( int x1, int y1, int x2, int y2 ) {
    int dx = x2 - x1 + 1;
    int dy = y2 - y1 + 1;
    int px = logb[dx], py = logb[dy];
    int ans1, ans2;
    ans1 = gcd( st[x1][y1][px][py], st[x2 - (1<<px) + 1][y1][px][py] );
    ans2 = gcd( st[x1][y2 - (1<<py) + 1][px][py], st[x2 - (1<<px) + 1][y2 - (1<<py) + 1][px][py] );
    return gcd ( ans1, ans2 );
}
int main() {
    
    freopen ( "matgcd.in", "r", stdin ) ;
    freopen ( "matgcd.out", "w", stdout ) ;
    
    logb[0] = -1;
    for( RG int i = 1; i < N; i++ )
        logb[i] = logb[i/2] + 1;
    scanf( "%d%d%d", &n, &m, &q );
    for( RG int i = 1; i <= n; i++ )
        for( RG int j = 1; j <= m; j++ ) 
            scanf( "%d", &st[i][j][0][0] );
    init();
    while( q-- ) {
        int x1, y1, x2, y2;
        char ss[100];
        scanf( "%s%d%d%d%d", ss, &x1, &y1, &x2, &y2 );
        printf( "%d\n", query(x1,y1,x2,y2) );
    }
}

matgcd.zip
segsum.zip
matsum.zip
测试一.docx

已有 3 条评论

正在回复给  
去登陆?

   点击刷新验证码

    decoration
    decoration
    2018 - 05 - 06 14 : 35

    强啊

    434480390
    434480390
    2018 - 05 - 06 14 : 35

    此人乃大佬是也
    (其实他被清华少年班提前录取了√

      可爱的诗和远方qwq
      2018 - 05 - 06 20 : 18

      fake

标签云

文章留名

decoration
decoration
434480390
434480390