头像

烛之武

九歌粉丝团


访客:22262

离线:4天前


新鲜事 原文

烛之武
10天前
今天又是通宵的节奏呀呀呀。。。


新鲜事 原文

烛之武
1个月前
为什么总有一些事让人糟心,比如早上一觉起来,衣服不见了!我一脸问号❓❓❓❓❓❓❓❓❓❓❓


活动打卡代码 AcWing 255. 第K小数

烛之武
1个月前

可持久化线段树(主席树)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std ;

const int N = 100010 ;

vector<int> vt ;
struct node{  //维护离散化之后的值
    int l,r ;
    int cnt ;
}tr[N*4+N*17] ;

int root[N],idx ;
int seq[N] ;
int n,m ;

int find(int x){
    return lower_bound(vt.begin(),vt.end(),x) - vt.begin() ;
}

int build(int l,int r){
    int p = ++ idx ;
    if(l>=r) return p ;
    int mid = l + r >> 1 ;
    tr[p].l = build(l,mid), tr[p].r = build(mid+1,r) ;
    return p ;
} 

int insert(int p,int l,int r,int x){
    int q = ++ idx ;
    if(l == r){
        tr[q].cnt ++ ;
        return q ;
    }
    tr[q] = tr[p] ;
    int mid = l + r >> 1 ;
    if(x<=mid) tr[q].l = insert(tr[p].l,l,mid,x) ;
    else tr[q].r = insert(tr[p].r,mid+1,r,x) ;
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt ;

    return q ;
}

int query(int q,int p,int l,int r,int k){
    if(l == r){
        return l ;
    }
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt ;
    int mid = l + r >> 1 ;
    if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k) ;
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt) ;
}

int main(){
    scanf("%d%d",&n,&m) ;

    for(int i=1;i<=n;i++){
        scanf("%d",&seq[i]) ;
        vt.push_back(seq[i]) ;
    }

    sort(vt.begin(),vt.end()) ;
    vt.erase(unique(vt.begin(),vt.end()),vt.end()) ;

    root[0] = build(0,vt.size()-1) ;

    for(int i=1;i<=n;i++){
        root[i] = insert(root[i-1],0,vt.size()-1,find(seq[i])) ;
    }

    while(m --){
        int a,b,c ;
        scanf("%d%d%d",&a,&b,&c) ;
        printf("%d\n",vt[query(root[b],root[a-1],0,vt.size()-1,c)]) ;
    }

    return 0 ;
}


活动打卡代码 AcWing 256. 最大异或和

烛之武
1个月前

可持久化trie

是最大异或对那题的扩展

#include <iostream>

using namespace std ;

const int N = 600010, M = 24 * N ;

int tr[M][2],idx ;
int max_id[M],root[N],s[N] ;
int n, m ;

void insert(int u,int cnt,int p,int q){
    if(cnt<0){
        max_id[q] = u ;    
        return ;
    }
    int x = s[u] >> cnt & 1 ;
    if(p) tr[q][x^1] = tr[p][x^1] ;
    tr[q][x] = ++ idx ;
    insert(u,cnt-1,tr[p][x],tr[q][x]) ;
    max_id[q] = max(max_id[tr[q][0]],max_id[tr[q][1]]) ;
}

int query(int root,int x,int l){
    int p = root ;
    for(int i=23;i>=0;i--){
        int id = x >> i & 1 ;
        if(max_id[tr[p][id^1]]>=l) p = tr[p][id^1] ;
        else p = tr[p][id] ;
    }
    return x ^ s[max_id[p]] ;
}

int main(){
    scanf("%d%d",&n,&m) ;

    root[0] = ++ idx ;
    max_id[0] = -1 ;
    insert(0,23,0,root[0]) ;
    for(int i=1;i<=n;i++){
        int x ;
        scanf("%d",&x) ;
        root[i] = ++ idx ;
        s[i] = s[i-1] ^ x ;
        insert(i,23,root[i-1],root[i]) ;
    }

    while(m --){
        char op[2] ;
        scanf("%s",op) ;
        if(op[0] == 'A'){
            int x ;
            scanf("%d",&x) ;
            n ++ ;
            s[n] = s[n-1] ^ x ;
            root[n] = ++ idx ;
            insert(n,23,root[n-1],root[n]) ;
        }else{
            int l,r,x ;
            scanf("%d%d%d",&l,&r,&x) ;
            printf("%d\n",query(root[r-1],s[n]^x,l-1)) ;
        }
    }
    return 0 ;

}


活动打卡代码 AcWing 239. 奇偶游戏

烛之武
1个月前

边带权

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <unordered_map>

using namespace std ;

const int N = 20010 ;

int p[N],d[N] ;
int n, m ;
unordered_map<int,int> mp ;

int get(int x){
    if(mp.count(x) == 0) mp[x] = ++ n ;
    return mp[x] ;
}

int find(int x){
    if(x != p[x]){
        int root = find(p[x]) ;
        d[x] ^= d[p[x]] ;
        p[x] = root ;
    }
    return p[x] ;
}

int main(){
    cin >> n >> m ;
    n = 0 ;

    for(int i=0;i<N;i++) p[i] = i ;

    int res = m ;
    for(int i=1;i<=m;i++){
        int a,b ;
        string c ;
        cin >> a >> b >> c ;
        a = get(a-1), b = get(b) ;  //类似于前缀和
        int fa = find(a), fb = find(b) ;
        int t = 0 ;
        if(c == "odd") t = 1 ;
        if(fa == fb){
            if(d[a]^d[b] != t){
                res = i - 1 ;
                break ;
            }
        }else{
            p[fa] = fb ;
            d[fa] = d[a] ^ d[b] ^ t ;
        }
    }
    cout << res << endl ;

    return 0 ;

}

扩展域

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std ;

const int N = 40010,M = N/2 ;

unordered_map<int,int> mp ;
int p[N] ;
int n, m ;

int get(int x){
    if(mp.count(x) == 0) mp[x] = ++ n ;
    return mp[x] ;
}

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;
}

int main(){
    cin >> n >> m ;
    n = 0 ;

    for(int i=0;i<N;i++) p[i] = i ;

    int res = m ;
    for(int i=1;i<=m;i++){
        int a, b ;
        string c ;
        cin >> a >> b >> c ;

        a = get(a-1), b = get(b) ;
        if(c == "even"){
            if(find(a) == find(b+M)){
                res = i-1 ;
                break ;
            }else{
                p[find(a)] = find(b) ;
                p[find(a+M)] = find(b+M) ;
            }
        }else{
            if(find(a) == find(b)){
                res = i-1 ;
                break ;
            }else{
                p[find(a)] = find(b+M) ;
                p[find(a+M)] = find(b) ;
            }
        }
    }

    cout << res << endl ;

    return 0 ;

}


活动打卡代码 AcWing 238. 银河英雄传说

烛之武
1个月前

边带权并查集

#include <iostream>

using namespace std ;

const int N = 30010 ;

int p[N],d[N],s[N] ;
int n ;

int find(int x){
    if(x != p[x]){
        int root = find(p[x]) ;
        d[x] += d[p[x]] ;
        p[x] = root ;
    }
    return p[x] ;
}

int main(){
    scanf("%d",&n) ;

    for(int i=1;i<N;i++){
        p[i] = i ;
        s[i] = 1 ;
    }

    for(int i=1;i<=n;i++){
        char op[2] ;
        int x,y ;
        scanf("%s%d%d",op,&x,&y) ;
        if(op[0] == 'M'){
            int fx = find(x),fy = find(y) ;
            if(fx != fy){
                d[fy] = s[fx] ;
                s[fx] += s[fy] ;
                p[fy] = p[fx] ;
            }
        }else{
            int fx = find(x),fy = find(y) ;
            if(fx != fy) puts("-1") ;
            else{
                printf("%d\n",abs(d[x]-d[y])-1) ;
            }
        }
    }
    return 0 ;
}


活动打卡代码 AcWing 237. 程序自动分析

烛之武
1个月前

并查集

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>

#define x first 
#define y second 

using namespace std ;

typedef pair<int,int> PII ;
const int N = 2000010 ;

int p[N] ;
int n, cnt ;

int find(int a){
    if(a != p[a]){
        p[a] = find(p[a]) ;
    }
    return p[a] ;
}

int main(){
    int t ;
    scanf("%d",&t) ;
    while(t --){
        scanf("%d",&n) ;
        cnt = 1 ;
        vector<PII> vt ;
        for(int i=1;i<=N-1;i++) p[i] = i ;
        unordered_map<int,int> um ;
        for(int i=1;i<=n;i++){
            int a,b,c ;
            scanf("%d%d%d",&a,&b,&c) ;
            if(!um.count(a)){
                um[a] = cnt ;
                cnt ++ ;
            }
            if(!um.count(b)){
                um[b] = cnt ;
                cnt ++ ;
            }
            if(c){
                int fa = find(um[a]), fb = find(um[b]) ;
                if(fa != fb){
                    p[fa] = fb ;
                }
            }else{
                vt.push_back({um[a],um[b]}) ;
            }
        }
        bool flag = true ;
        for(int i=0;i<vt.size();i++){
            int x = vt[i].x, y = vt[i].y ;
            if(find(x) == find(y)){
                flag = false ;
                break ;
            }
        }
        if(flag){
            puts("YES") ;
        }else{
            puts("NO") ;
        }
    }
    return 0 ;
}


活动打卡代码 AcWing 238. 银河英雄传说

烛之武
1个月前

边带权并查集

#include <iostream>

using namespace std ;

const int N = 30010 ;

int p[N],d[N],s[N] ;
int n ;

int find(int x){
    if(x != p[x]){
        int root = find(p[x]) ;
        d[x] += d[p[x]] ;
        p[x] = root ;
    }
    return p[x] ;
}

int main(){
    cin >> n ;

    for(int i=1;i<N;i++){
        p[i] = i ;
        s[i] = 1 ;
    }

    for(int i=1;i<=n;i++){
        char op[2] ;
        int x,y ;
        cin >> op >> x >> y ;
        if(op[0] == 'M'){
            int fx = find(x),fy = find(y) ;
            if(fx != fy){
                d[fy] = s[fx] ;
                s[fx] += s[fy] ;
                p[fy] = p[fx] ;
            }
        }else{
            int fx = find(x),fy = find(y) ;
            if(fx != fy) puts("-1") ;
            else{
                printf("%d\n",abs(d[x]-d[y])-1) ;
            }
        }
    }
    return 0 ;
}


活动打卡代码 AcWing 237. 程序自动分析

烛之武
1个月前

并查集

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <vector>

#define x first 
#define y second 

using namespace std ;

typedef pair<int,int> PII ;
const int N = 2000010 ;

int p[N] ;
int n, cnt ;

int find(int a){
    if(a != p[a]){
        p[a] = find(p[a]) ;
    }
    return p[a] ;
}

int main(){
    int t ;
    scanf("%d",&t) ;
    while(t --){
        scanf("%d",&n) ;
        cnt = 1 ;
        vector<PII> vt ;
        for(int i=1;i<=N-1;i++) p[i] = i ;
        unordered_map<int,int> um ;
        for(int i=1;i<=n;i++){
            int a,b,c ;
            scanf("%d%d%d",&a,&b,&c) ;
            if(!um.count(a)){
                um[a] = cnt ;
                cnt ++ ;
            }
            if(!um.count(b)){
                um[b] = cnt ;
                cnt ++ ;
            }
            if(c){
                int fa = find(um[a]), fb = find(um[b]) ;
                if(fa != fb){
                    p[fa] = fb ;
                }
            }else{
                vt.push_back({um[a],um[b]}) ;
            }
        }
        bool flag = true ;
        for(int i=0;i<vt.size();i++){
            int x = vt[i].x, y = vt[i].y ;
            if(find(x) == find(y)){
                flag = false ;
                break ;
            }
        }
        if(flag){
            puts("YES") ;
        }else{
            puts("NO") ;
        }
    }
    return 0 ;
}


活动打卡代码 AcWing 1252. 搭配购买

烛之武
1个月前

01背包 + 并查集

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first 
#define y second

using namespace std ;

typedef pair<int,int> PII ;
const int N = 10010 ;

int p[N],v[N],w[N] ;
int f[N] ;
PII cnt[N] ;
int n,k,m ;

int find(int a){
    if(p[a] != a) p[a] = find(p[a]) ;
    return p[a] ;
}

int main(){
    scanf("%d%d%d",&n,&k,&m) ;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v[i],&w[i]) ;
    }

    for(int i=1;i<=n;i++){
        p[i] = i ;
        cnt[i] = {v[i],w[i]} ;
    }

    while(k --){
        int x,y ;
        scanf("%d%d",&x,&y) ;
        int fx = find(x), fy = find(y) ;
        if(fx != fy){
            p[fy] = fx ;
            cnt[fx].x += cnt[fy].x ;
            cnt[fx].y += cnt[fy].y ;
        }
    }

    for(int i=1;i<=n;i++){
        if(p[i] == i){ // 只有p[i] == i才表示这是一整个新物品
            int vv = cnt[find(i)].x, ww = cnt[find(i)].y ;
            for(int j=m;j>=vv;j--){
                f[j] = max(f[j],f[j-vv] + ww) ;
            }
        }
    }
    printf("%d\n",f[m]) ;

    return 0 ;
}