头像

nuo0930




离线:3天前


最近来访(57)
用户头像
wiaxiamm
用户头像
ohmygod
用户头像
Little_Sealx
用户头像
大梦一场
用户头像
Tequila
用户头像
nqR
用户头像
维叶
用户头像
费米气泡
用户头像
InsaneFourier
用户头像
我和我的祖国
用户头像
白马金羁侠少年
用户头像
wlyhuat
用户头像
Albatross_3
用户头像
Eason_AC
用户头像
加油加油111222
用户头像
Takenzz
用户头像
liang_xi_
用户头像
我舅是太阳
用户头像
shewaitspatiently
用户头像
Barbed

新鲜事 原文

nuo0930
5个月前
再捞一把,求助 kmp:https://www.acwing.com/file_system/file/content/whole/index/content/2786292/


新鲜事 原文

nuo0930
5个月前
捞一把,求助 $kmp$:https://www.acwing.com/file_system/file/content/whole/index/content/2786292/



nuo0930
5个月前

请问 kmp 的时间复杂度是为什么是 $O(n+m)$?




nuo0930
7个月前

我用快速排序连卡常都没卡常,直接就过了。。。




nuo0930
7个月前

首先你需要会正常点的快排,然后我们会发现正常的快排干了很多没用的事情,和基准数相等的数也继续递归下去排序了,所以我们需要优化。

大致就是改成这样:

void quick_sort(int l, int r) {
    if(l >= r)
        return;
    int pivot = a[rand() % (r - l + 1) + l], i = l, j = l, k = r + 1;
    for(; i < k; ){
        if(a[i] < pivot)
            swap(a[i++], a[j++]);
        else if(pivot < a[i])
            swap(a[i], a[--k]);
        else
            ++i;
    }
    quick_sort(l, j);
    quick_sort(k, r);
}

然后我们发现这样复杂度仍然是期望 $O(n \log n)$,可我们要最坏 $O(n \log n)$ 的怎么办啊?

实际上可以限制一下递归层数,超过 $\left\lfloor \log n \right\rfloor$ 层就直接转堆排序。

这样复杂度就变成了最坏 $O(n \log n)$。

而且在只剩下很少的数的时候由于已经比较有序了,用插入排序会比快速排序还快。

代码:

#include <math.h>
#include <stdio.h>
#include <time.h>
const int maxn = 100010;
int a[ maxn ];
inline unsigned _rand( ) {
    static unsigned seed = time( 0 );
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}
inline void swap( int &a, int &b ) {
    int t = a;
    a = b;
    b = t;
}
void insert_sort( int l, int r ) {
    for ( int i = l + 1; i <= r; ++i )
        for ( int j = i; j > l && a[ j - 1 ] > a[ j ]; --j )
            swap( a[ j - 1 ], a[ j ] );
}
int *heap;
int heap_size;
void heapify( int x ) {
    for ( bool ch; ( x << 1 ) <= heap_size;
          swap( heap[ x << 1 | ch ], heap[ x ] ), x = x << 1 | ch ) {
        ch = ( x << 1 ) < heap_size
             && heap[ x << 1 ] <= heap[ x << 1 | 1 ];
        if ( heap[ x << 1 | ch ] <= heap[ x ] )
            return;
    }
}
void heap_sort( int l, int r ) {
    heap = a + l - 1;
    heap_size = r - l + 1;
    for ( int i = heap_size >> 1; i; )
        heapify( i-- );
    for ( ; heap_size; heapify( 1 ) )
        swap( heap[ 1 ], heap[ heap_size-- ] );
}
void quick_sort( int l, int r, int cnt ) {
    if ( r - l < 10 ) {
        insert_sort( l, r );
        return;
    }
    if ( !cnt ) {
        heap_sort( l, r );
        return;
    }
    int pivot = a[ _rand( ) % ( r - l + 1 ) + l ], i = l, j = l, k = r + 1;
    for ( ; i < k; ) {
        if ( a[ i ] < pivot )
            swap( a[ i++ ], a[ j++ ] );
        else if ( pivot < a[ i ] )
            swap( a[ i ], a[ --k ] );
        else
            ++i;
    }
    quick_sort( l, j, cnt - 1 );
    quick_sort( k, r, cnt - 1 );
}
void sort( int n ) {
    quick_sort( 1, n, log2( n ) );
}
int main( ) {
    int n;
    scanf( "%d", &n );
    for ( int i = 1; i <= n; i++ )
        scanf( "%d", &a[ i ] );
    sort( n );
    for ( int i = 1; i <= n; i++ )
        printf( "%d ", a[ i ] );
    return 0;
}



nuo0930
10个月前

题目链接 可持久化普通平衡树(洛谷)

连样例都没过

错误的代码:

#include <cstdio>
#include <cstdlib>
const int maxsize = 30001000;
int val[maxsize];
int key[maxsize];
int size[maxsize];
int lc[maxsize], rc[maxsize];
int nodecnt;
inline int newnode(int x) {
    key[++nodecnt] = std::rand();
    val[nodecnt] = x;
    lc[nodecnt] = rc[nodecnt] = 0;
    size[nodecnt] = 1;
    return nodecnt;
}
inline int copynode(int x) {
    key[++nodecnt] = key[x];
    val[nodecnt] = val[x];
    lc[nodecnt] = lc[x];
    rc[nodecnt] = rc[x];
    size[nodecnt] = size[x];
    return nodecnt;
}
inline void pushup(int rt) {
    size[rt] = size[lc[rt]] + size[rc[rt]] + 1;
}
void split(int rt, int x, int& a, int& b) {
    if (!rt)
        return (void)(a = b = 0);
    int t = copynode(rt);
    if (val[rt] <= x) {
        a = t;
        split(rc[a], x, rc[a], b);
    } else {
        b = t;
        split(lc[a], x, a, lc[a]);
    }
    pushup(t);
}
void _split(int rt, int x, int& a, int& b) {
    if (!rt)
        return (void)(a = b = 0);
    if (val[rt] <= x) {
        a = rt;
        _split(rc[rt], x, rc[rt], b);
    } else {
        b = rt;
        _split(lc[rt], x, a, lc[rt]);
    }
    pushup(rt);
}
void join(int& rt, int a, int b) {
    if (!a || !b)
        return (void)(rt = a ^ b);
    if (key[a] < key[b]) {
        rt = b;
        join(lc[rt], a, lc[b]);
    } else {
        rt = a;
        join(rc[rt], rc[rt], b);
    }
    pushup(rt);
}
void ins(int rt, int x) {
    int a, b;
    split(rt, x, a, b);
    join(a, a, newnode(x));
    join(rt, a, b);
}
void del(int& rt, int x) {
    int a, b, c;
    split(rt, x, a, b);
    split(a, x - 1, a, c);
    join(c, lc[c], rc[c]);
    join(a, a, c);
    join(rt, a, b);
}
int value(int rt, int x) {
    if (x <= size[lc[rt]])
        return value(lc[rt], x);
    if (x > size[lc[rt]] + 1)
        return value(rt, x - size[lc[rt]] - 1);
    return val[rt];
}
int rank(int rt, int x) {
    int a, b;
    _split(rt, x - 1, a, b);
    int ans = size[a] + 1;
    join(rt, a, b);
    return ans;
}
int max(int rt) {
    if (!rt)
        return -2147483648;
    if (rc[rt])
        return max(rc[rt]);
    return val[rt];
}
int pre(int& rt, int x) {
    int a, b;
    _split(rt, x - 1, a, b);
    int ans = max(a);
    join(rt, a, b);
    return ans;
}
int min(int rt) {
    if (!rt)
        return 2147483647;
    if (lc[rt])
        return min(lc[rt]);
    return val[rt];
}
int nxt(int& rt, int x) {
    int a, b;
    _split(rt, x, a, b);
    int ans = min(b);
    join(rt, a, b);
    return ans;
}
const int maxn = 500001;
int root[maxn];
int main() {
    int m;
    std::scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int v, op, x;
        std::scanf("%d%d%d", &v, &op, &x);
        root[i] = v;
        switch (op) {
            case 1:
                ins(root[i], x);
                break;
            case 2:
                del(root[i], x);
                break;
            case 3:
                std::printf("%d\n", rank(root[i], x));
                break;
            case 4:
                std::printf("%d\n", value(root[i], x));
                break;
            case 5:
                std::printf("%d\n", pre(root[i], x));
                break;
            case 6:
                std::printf("%d\n", nxt(root[i], x));
                break;
        }
    }
    return 0;
}



nuo0930
10个月前

题目链接 普通平衡树

代码如下:

#include<cstdio>
#include<cstdlib>
struct tree_node{
    short key;
    int val;
    int cnt;
    int size;
    int lc,rc;
    tree_node() {
        key=0;
        val=0;
        cnt=0;
        size=0;
        lc=rc=0;
    }
    tree_node(int a) {
        key=std::rand();
        val=a;
        cnt=1;
        size=1;
        lc=rc=0;
    }
}tree[100001];
int cnt;
inline int newnode(int a) {
    tree[++cnt]=tree_node(a);
    return cnt;
}
inline void pushup(int rt) {
    tree[rt].size=tree[tree[rt].lc].size+tree[tree[rt].rc].size+tree[rt].cnt;
}
void value_split(int rt,int x,int &a,int &b) {
    if(!rt) {
        a=b=0;
        return ;
    }
    if(tree[rt].val<=x) {
        a=rt;
        value_split(tree[rt].rc,x,tree[a].rc,b);
    }
    else {
        b=rt;
        value_split(tree[rt].lc,x,a,tree[b].lc);
    }
    pushup(rt);
}
void rank_split(int rt,int x,int &a,int &b) {
    if(!rt) {
        a=b=0;
        return ;
    }
    int tmp=tree[tree[rt].lc].size+tree[rt].cnt;
    if(tmp<=x) {
        a=rt;
        rank_split(tree[rt].rc,x-tmp,tree[a].rc,b);
    }
    else {
        b=rt;
        rank_split(tree[rt].lc,x,a,tree[b].lc);
    }
    pushup(rt);
}
void merge(int &rt,int a,int b) {
    if(!a||!b) {
        rt=a^b;
        return ;
    }
    if(tree[a].key>=tree[b].key) {
        rt=a;
        merge(tree[a].rc,tree[a].rc,b);
    }
    else {
        rt=b;
        merge(tree[b].lc,a,tree[b].lc);
    }
    pushup(rt);
}
void ins(int& rt,int x) {
    int a=0,b=0,c=0;
    value_split(rt,x,a,b);
    value_split(a,x-1,a,c);
    if(c) 
        tree[c].cnt=tree[c].size=tree[c].cnt+1;
    else
        c=newnode(x);
    merge(a,a,c);
    merge(rt,a,b);
}
bool del(int& rt,int x) {
    int a=0,b=0,c=0;
    bool flag=true;
    value_split(rt,x,a,b);
    value_split(a,x-1,a,c);
    if(!c)
        flag=false;
    else 
        if(!(tree[c].cnt=tree[c].size=tree[c].cnt-1))
            c=0;
    merge(a,a,c);
    merge(rt,a,b);
    return flag;
}
int the_min(int rt) {
    for(;tree[rt].lc;rt=tree[rt].lc);
    return tree[rt].val;
}
int the_max(int rt) {
    for(;tree[rt].rc;rt=tree[rt].rc);
    return tree[rt].val;
}
int rank(int &rt,int x) {
    int a=0,b=0;
    value_split(rt,x-1,a,b);
    int ans=tree[a].size+1;
    merge(rt,a,b);
    return ans;
}
int value(int &rt,int x) {
    int a=0,b=0;
    rank_split(rt,x,a,b);
    int ans=the_max(a);
    merge(rt,a,b);
    return ans;
}
int pre(int &rt,int x) {
    int a=0,b=0;
    value_split(rt,x-1,a,b);
    int ans=the_max(a);
    merge(rt,a,b);
    return ans;
}
int nxt(int &rt,int x) {
    int a=0,b=0;
    value_split(rt,x,a,b);
    int ans=the_min(b);
    merge(rt,a,b);
    return ans;
}
int main() {
    srand(2333*114*514);
    int m;
    int op,x;
    std::scanf("%d",&m);
    int root=0;
    while(m--) {
        scanf("%d%d",&op,&x);
        switch(op) {
            case 1: {
                ins(root,x);
                break;
            }
            case 2: {
                del(root,x);
                break;
            }
            case 3: {
                printf("%d\n",rank(root,x));
                break;
            }
            case 4: {
                printf("%d\n",value(root,x));
                break;
            }
            case 5: {
                printf("%d\n",pre(root,x));
                break;
            }
            case 6: {
                printf("%d\n",nxt(root,x));
                break;
            }
        }
    }
    return 0;
}