285484026

川大暑假集训——数据结构
川大暑假集训——数据结构PS:虽然是川大集训但是用的是电科的OJ,感谢电科大佬题目索引:[TOC]1.吞吐量题解:...
扫描右侧二维码阅读全文
02
2019/07

川大暑假集训——数据结构

川大暑假集训——数据结构
PS:虽然是川大集训但是用的是电科的OJ,感谢电科大佬

题目索引:

[TOC]

1.吞吐量

题解:最小瓶颈路,用倍增维护一下就好了

#include <bits/stdc++.h> 
using namespace std;

const int MAXN = 200005,MAXD = 20;

int Fa[MAXN],deep[MAXN],Min[MAXN][23],anc[MAXN][23];
int T,N,M,e = 1,sum;

int dist;

vector<pair<int,int> >E[MAXN];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

void dfs(int u,int h){
    deep[u] = h;
    
    for(int i = 1;i <= MAXD;i++){
        anc[u][i] = anc[ anc[u][i-1] ][i-1];
        Min[u][i] = min( Min[ anc[u][i-1] ][i-1] , Min[u][i-1] );
    }
    
    for(auto tmp : E[u]){
        int v = tmp.first;
        int c = tmp.second;
        if(!deep[v]){
            anc[v][0] = u;
            Min[v][0] = c;
            dfs(v,h+1);
        }
    }  
}

inline int swim(int &u,int v){
    dist = 2147483647;
    for(int i = MAXD;i >= 0;i--)
        if(deep[anc[u][i]] > deep[v]){
        dist = min(dist,Min[u][i]);
        u = anc[u][i];
        }
    if(deep[u] != deep[v]){
        dist = min(dist,Min[u][0]);
        u = anc[u][0];
    }
    return dist;
}

inline void query(int x,int y){
    dist = 2147483647;
    
    if(deep[x] < deep[y]) swap(x,y);
    
    dist = min(dist,swim(x,y));
    
    if(x == y) return;
    
    for(int i = MAXD;i >= 0;i--)
        if(anc[x][i] != anc[y][i]){
            dist = min(Min[x][i],dist);
            dist = min(Min[y][i],dist);
            x = anc[x][i];
            y = anc[y][i];
        }
        
    if(x != y)  dist =  min( dist , min( Min[x][0] , Min[y][0] ) );
}

inline void init()
{
    N = read();M = read();
    
    int u,v,c;
    for(int i = 1;i < N;i++){
        u = read();v = read();c = read();
        E[u].push_back(make_pair(v,c));
        E[v].push_back(make_pair(u,c));
    }
        
}

int main()
{
    init();
    dfs(1,1);
    int u,v;
    while(M--){
        scanf("%d %d",&u,&v);
        dist = 2147483647;
        query(u,v);
        printf("%d\n",dist);
    }
    
    return 0;
}

2.拍照

题解:维护一个前缀和以后问题就变成了,查询最大值,我用的线段树用优先队列什么的都是差不多的。

#include <bits/stdc++.h>

const int MAXN = 2000005;

using namespace std;

int n,m,l,r,qL,qR,ql,qr;
long long sum[MAXN],ans; 

pair<long long,int>Max[MAXN],tmp; 

struct node{
    int L,qL,qR,R;
    long long ans;
    friend bool operator < (const node &A,const node &B){
        return A.ans < B.ans;
    }
    
}A,AL,AR;

priority_queue<node>Q;

inline int read()
{
    int x = 0,f = 1;char ch = getchar();
    while(ch < '0' || '9' < ch){if(ch == '-') f = -1;ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}    
    return x*f;
}    

void update(int o,int L,int R){
    if(L == R){
        Max[o].first = sum[L];
        Max[o].second = L;
        return;
    }
    int M = L + R >> 1;
    update(o<<1,L,M);
    update(o<<1|1,M+1,R);
    Max[o] = max(Max[o<<1],Max[o<<1|1]);
}

void query(int o,int L,int R){
    if(ql <= L && R <= qr){
        tmp = max(tmp,Max[o]);
        return;
    }
    int M = L + R >> 1;
    if(ql <= M) query(o<<1,L,M);
    if(M < qr) query(o<<1|1,M+1,R);
}

inline void init()
{
    n = read();m = read();
    
    for(int i = 1;i <= n;i++) scanf("%lld",&sum[i]);
    ans = sum[1];
    for(int i = 1;i <= n;i++)
        sum[i] += sum[i-1];
    update(1,1,n);
    
}

int main()
{
    init();
    
    for(int i = 1;i <= n;i++)
    {
        ql = i;qr = i + m - 1;
        tmp.first = -8446744073709551614ll;
        tmp.second = -2147483647;
        query(1,1,n);
        ans = max(ans,tmp.first - sum[i-1]);
    }
    printf("%lld\n",ans);
    return 0;
}

3.密码

题解:维护一个单调队列

#include <bits/stdc++.h>

const int MAXN = 1000000;

using namespace std;

int n,k;
char s[MAXN],T[MAXN];
deque<char>Q;


int main()
{
    while(scanf("%d %d",&n,&k) != EOF)
    {
        for(int i = 1;i <= n;i++)
            scanf("%s",s+i);
        while(!Q.empty()) Q.pop_back();
        for(int i = 1;i <= n - k + 1;i++){
            while(!Q.empty() && s[i] > Q.front()) Q.pop_front();
            Q.push_front(s[i]);
        }
        int cnt = 0;
        T[++cnt] = Q.back();
        Q.pop_back();
        for(int i = n - k + 2;i <= n;i++){
            while(!Q.empty() && s[i] > Q.front()) Q.pop_front();
            Q.push_front(s[i]);
            T[++cnt] = Q.back();Q.pop_back();
        }
        for(int i = 1;i <= k;i++)    printf("%c",T[i]);
        printf("\n");
    }
    
    return 0;
}

4.数理统计

题解:线段树板子题。。。。QAQ初始化一定要足够大不然容易WA

#include <bits/stdc++.h>

const int MAXN = 10000000;

using namespace std;

int n,q,qL,qR;
long long sum[MAXN],tmp,Max[MAXN],Min[MAXN],add[MAXN];

pair<long long,long long>ans;

inline int read(){
    int x = 0,f = 1;char ch = getchar();
    while(ch < '0' || '9' < ch){if(ch == '-') f = -1;ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x*f;
}

inline void pushdown(int o,long long M){
    if(add[o]){
        sum[o<<1] += (M-M/2)*add[o];
        sum[o<<1|1] += (M/2)*add[o];
        Max[o<<1] += add[o];
        Max[o<<1|1] += add[o];
        Min[o<<1] += add[o];
        Min[o<<1|1] += add[o];
        add[o<<1] += add[o];
        add[o<<1|1] += add[o];
        add[o] = 0;
    }
}

inline void pushup(int o){
    sum[o] = sum[o<<1] + sum[o<<1|1];
    Max[o] = max(Max[o<<1],Max[o<<1|1]);
    Min[o] = min(Min[o<<1],Min[o<<1|1]);
}

void update(int o,long long L,long long R,int val){
    if(qL <= L && R <= qR){
        sum[o] += (R - L + 1) * val;
        Max[o] += val;
        Min[o] += val;
        add[o] += val;
        return;
    }
    pushdown(o,R - L +1);
    long long M = (L + R) >> 1;
    if(qL <= M) update(o<<1,L,M,val);
    if(M < qR) update(o<<1|1,M+1,R,val);
    pushup(o);
}

void query(int o,int L,int R){
    if(qL <= L && R <= qR){
        tmp += sum[o];
        ans.first = max(ans.first,Max[o]);
        ans.second = min(ans.second,Min[o]);
        return;
    }
    pushdown(o,R - L + 1);
    long long M = (L + R) >> 1;
    if(qL <= M) query(o<<1,L,M);
    if(M < qR) query(o<<1|1,M+1,R);
    pushup(o);
}

int main()
{
    n = read();q = read();

    int k,d;
    while(q--){
        k = read();
        if(k == 1){
            qL = read();qR = read();d = read();
            update(1,1,n,d);
        }
        if(k == 2){
            qL = read();qR = read();
            tmp = 0;
            ans.first = -0x3f3f3f3f3f3f3f3f;
            ans.second = 0x3f3f3f3f3f3f3f3f;
            query(1,1,n);
            printf("%lld\n",tmp);
        }
        if(k == 3){
            qL = read();qR = read();
            tmp = 0;
            ans.first = -0x3f3f3f3f3f3f3f3f;
            ans.second = 0x3f3f3f3f3f3f3f3f;
            query(1,1,n);
            printf("%lld\n",ans.first - ans.second);
        }
    }

    return 0;
}

5.战争

题解:维护一个01trie树,然后在trie树上查询最大值和最小值

#include <bits/stdc++.h>

const int MAXN = 10000005,N = 32;

using namespace std;

int n;
long long d[N],sum[MAXN],data[MAXN],ans[MAXN],Max;

struct Trie{
    int ch[MAXN][6];
    int L,root;
    inline int newnode(){
        ch[L][0] = ch[L][7] = -1;
        L++;
        return L - 1;
    }
    inline void init(){
        L = 0;
        root = newnode();
    }
    
    inline void insert1(long long x)
    {
        bitset<N>bit = x;
        int now = root,v;
        for(int i = 31;i >= 0;i--){
            v = bit[i];
            if(ch[now][v] == -1)
                ch[now][v] = newnode();
            now = ch[now][v];
            sum[now]++;
        }
    }

    inline void insert2(long long x)
    {
        bitset<N>bit = x;
        int now = root,v;
        for(int i = 31;i >= 0;i--){
            v = bit[i];
            now = ch[now][v];
            sum[now]--;
        }
    }
    
    inline long long query1(long long x)
    {
        bitset<N>bit = x;
        long long ret = 0;
        int now = root,v;
        for(int i = 31;i >= 0;i--){
            v = bit[i];
            if(ch[now][v^1] != -1 && sum[ch[now][v^1]] != 0){
                ret += d[i];
                now = ch[now][v^1];
            }
            else now = ch[now][v];    
        }
        return ret;
    }

    inline long long query2(long long x)
    {
        bitset<N>bit = x;
        long long ret = 0;
        int now = root,v;
        for(int i = 31;i >= 0;i--){
            v = bit[i];
            if(ch[now][v] != -1 && sum[ch[now][v]] != 0){
                now = ch[now][v];
            }
            else {
                ret += d[i];
                now = ch[now][v^1];
            }
        }
        return ret;
    }
    
}T;

int main()
{
    //freopen("input.txt","r",stdin);
    d[0] = 1;
    for(int i = 1;i < N;i++) d[i] = d[i-1] << 1;

    T.init();//T.insert1(0);

    scanf("%d",&n);
    int k,v;
    while(n--)
    {
        scanf("%d %d",&k,&v);
        if(k == 1){
            T.insert1(v);
        }
        if(k == 2){
            T.insert2(v);
        }
        if(k == 3){
            printf("%lld %lld\n",T.query2(v),T.query1(v));
        }
    }
    
    
    return 0;
}

6.对答案

题解:我们维护前缀异或和,我们可以认为区间为奇数就是异或为1,偶数就是异或为0,然后我们判断这一段的就性相同

#include <bits/stdc++.h>

const int MAXN = 10000000;

using namespace std;

int n,m;
int fa[MAXN];

int G(int x){
    return fa[x] == x ? x : fa[x] = G(fa[x]);
}

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

    int u,v;
    char s[100];
    
    for(int i = 0;i <= 3*n;i++) fa[i] = i;

    for(int i = 1;i <= m;i++){
        scanf("%d %d",&u,&v);
        u--;
        int f1 = G(u);
        int f2 = G(u+2*n);
        int f3 = G(v);
        int f4 = G(v+2*n);
        scanf("%s",s+1);
        if(s[1] == 'o'){
            if(f1 == f3 || f2 == f4){
                printf("%d\n",i-1);
                return 0;
            }
            fa[f1] = f4;
            fa[f2] = f3;
        }
        else{
            if(f1 == f4 || f2 == f3){
                printf("%d\n",i-1);
                return 0;
            }
            fa[f1] = f3;
            fa[f2] = f4;
        }
    }
    printf("ORZQHQH\n");

    return 0;
}

7.人在地上走,锅从天上来

题解:这个题目的那个暴力过程很好理解,唯一的问题就是怎么证明时间复杂度是正确的。我们可以考虑每一个线段,最多被访问到两次,第一次插入,第二次是合并。这样的话我们看似不清楚的时间复杂度就变得很明了。

#include <bits/stdc++.h>

const int MAXN = 1000000;

using namespace std;

int n,sum;

struct node{
    int L,R;
    friend bool operator < (const node &A,const node &B){
        return A.R < B.R;
    }
};

set<node>S;

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

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&L,&R);
        while(true){
            auto it = S.lower_bound((node){2147483647,L});
            if(it == S.end()) break;
            L = min(L,it->L);
            if(it->L > R) break;
            R = max(R,it->R);
            S.erase(it);
        }
        S.insert((node){L,R});
        printf("%d ",(int)S.size());
    }

    return 0;
}

8.My description is the most 単純な one,come on!

题解:动态点分板子题

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,m,R,Tsz,anc[MAXN][20],ans;
bool vis[MAXN],p[MAXN];

vector<int>E[MAXN],H[MAXN];
pair<int,int>d[MAXN];

struct node{
    int sz,son,mx,fa,deep;
}T[MAXN];

void dfs1(int u,int f){//找重心 
    T[u].sz = 1;T[u].mx = 0;
    for(auto v : E[u]){
        if(vis[v] || v == f) continue;
        dfs1(v,u);
        T[u].mx = max(T[u].mx,T[v].sz);
        T[u].sz += T[v].sz;
    }
    T[u].mx = max(T[u].mx,Tsz - T[u].sz);
    if(T[R].mx > T[u].mx) R = u;
}

void dfs2(int u){
    vis[u] = true;
    for(auto v : E[u]){
        if(vis[v]) continue;
        Tsz = T[v].sz;R = 0;
        dfs1(v,u);
        T[R].fa = u;
        H[u].push_back(R);
        dfs2(R);
    } 
}

inline void swim(int &u,int h){
    for(int i = 0;h;i++){
        if(h&1) u = anc[u][i];
        h >>= 1;
    }
}

int Q(int x,int y){
    if(y == 1000000) return 1000000;
    int fx = x; 
    int fy = y;
    if(T[x].deep < T[y].deep) swap(x,y);
    swim(x,T[x].deep - T[y].deep);
    for(int i = 18;i >= 0;i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    if(x != y){
        x = anc[x][0];
    }
    return (T[fx].deep + T[fy].deep - 2 * T[x].deep);
}

void dfs3(int x){
    d[x] = make_pair(0,x);
    int fa = T[x].fa;
    while(fa){
        d[fa] = min(d[fa],make_pair(Q(fa,x),x));
        fa = T[fa].fa;
    }
}

void query(int x){
    ans = min(ans,Q(x,d[x].second));
    int fa = T[x].fa;
    while(fa){
        ans = min(ans,Q(x,d[fa].second));
        fa = T[fa].fa;
    }
}

void Pre(int u,int fa){
    for(int i = 1;i <= 18;i++) anc[u][i] = anc[anc[u][i-1]][i-1];
    for(auto v : E[u]){
        if(v == fa) continue;
        anc[v][0] = u;
        T[v].deep = T[u].deep + 1;
        Pre(v,u);
    }
}

int main()
{
    //freopen("input.txt","r",stdin); 
    scanf("%d %d",&n,&m);
    
    int u,v;
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    Pre(1,0);
    
    T[0].mx = INF;Tsz = n;
    dfs1(1,0);
    dfs2(R);
        
    for(int i = 1;i <= n;i++) d[i] = make_pair(1000000,1000000);
        
    dfs3(1);
    
    //for(int i = 1;i <= n;i++) printf("d[%d]=%d\n",i,d[i]);
    
    int opt,x;
    while(m--){
        scanf("%d %d",&opt,&x);
        if(opt == 1){
            dfs3(x);
            //for(int i = 1;i <= n;i++) printf("d[%d]=%d\n",i,d[i]);
        }
        else {
            ans = n;
            query(x);
            printf("%d\n",ans);
        }
    }
    
    return 0;
}
Last modification:July 2nd, 2019 at 06:19 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment