首页 > 其他分享 >数据结构专题 1

数据结构专题 1

时间：2023-05-25 21:24:30浏览次数：88  
标签：数据结构 int 200010 dep 专题 100010 ans include

图论狗都不写。宁可写数据结构也不想写图论了。写吐了。牛子老师说这套题的后半全是正经数据结构，而且无 Ynoi。

所以啥时候开多项式。

由于写题解主要是合集，因此打算分拆一下水点社贡。目前停留在打算阶段。

日，为什么明天考试。

CF1039D You Are Given a Tree

很久以前看到过。这题主要在想到这玩意可以根号分治。

\(k\le B\) 贪心 dfs，大于的容易发现答案不超过根号，对每个答案二分一下左右端点。\(B\) 取 \(\sqrt{n\log n}\) 最优。

卡常，要预处理 dfs 序，还要记忆化。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n,sq;
struct node{
    int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int num,dfn[100010],fa[100010];
void dfs(int x,int f){
    dfn[++num]=x;fa[x]=f;
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f)dfs(edge[i].v,x);
    }
}
int dep[100010],ans[100010];
map<int,int>mp;
int check(int k){
    if(k==1)return n;
    if(mp.find(k)!=mp.end())return mp[k];
    for(int i=1;i<=n;i++)dep[i]=1;
    int ans=0;
    for(int i=n;i>=1;i--){
        int x=dfn[i];
        if(fa[x]&&dep[fa[x]]&&dep[x]){
            if(dep[x]+dep[fa[x]]>=k)ans++,dep[fa[x]]=0;
            else dep[fa[x]]=max(dep[fa[x]],dep[x]+1);
        }
    }
    return mp[k]=ans;
}
int main(){
    scanf("%d",&n);sq=sqrt(n*__lg(n));
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=sq;i++)ans[i]=check(i);
    for(int i=sq;i>=1;i--){
        int l=1,r=n+1,L,R;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid)<=i)r=mid;
            else l=mid+1;
        }
        if(l==1||l==n+1)continue;
        L=l;
        l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(check(mid)>=i)l=mid;
            else r=mid-1;
        }
        R=r;
        for(int j=L;j<=R;j++)ans[j]=i;
    }
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

CF983E NN country

牛子老师说是水题。

首先套路倍增一个 \(f_{i,j}\) 表示 \(i\) 点跳 \(j\) 条链能到哪里，然后根据是否有链经过 lca 来 \(-1\)。这是个套路二维数点，冲啥都行。

那好像真是水题，但是不是很想写。算了闲着也是闲着，写一发。

交了三发。主席树都写不清楚了！越来越菜了！

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n,m,q;
struct gra{
    int v,next;
}edge[200010];
int tot,head[200010];
void add(int u,int v){
    edge[++tot].v=v;edge[tot].next=head[u];head[u]=tot;
}
int num,dfn[200010],sz[200010],fa[200010],top[200010],son[200010],dep[200010];
void dfs1(int x,int f){
    sz[x]=1;dep[x]=dep[f]+1;
    for(int i=head[x];i;i=edge[i].next){
        dfs1(edge[i].v,x);
        sz[x]+=sz[edge[i].v];
        if(sz[son[x]]<sz[edge[i].v])son[x]=edge[i].v;
    }
}
void dfs2(int x,int f,int tp){
    dfn[x]=++num;top[x]=tp;
    if(son[x])dfs2(son[x],x,tp);
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=son[x])dfs2(edge[i].v,x,edge[i].v);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
struct node{
    #define lson tree[rt].ls
    #define rson tree[rt].rs
    int ls,rs,val;
}tree[400010<<5];
int t,rt[200010];
void pushup(int rt){
    tree[rt].val=tree[lson].val+tree[rson].val;
}
void update(int &rt,int pre,int L,int R,int pos){
    rt=++t;tree[rt]=tree[pre];
    if(L==R){
        tree[rt].val++;return;
    }
    int mid=(L+R)>>1;
    if(pos<=mid)update(lson,tree[pre].ls,L,mid,pos);
    else update(rson,tree[pre].rs,mid+1,R,pos);
    pushup(rt);
}
int query(int x,int y,int L,int R,int l,int r){
    if(tree[y].val-tree[x].val==0)return 0;
    if(l<=L&&R<=r)return tree[y].val-tree[x].val;
    int mid=(L+R)>>1,val=0;
    if(l<=mid)val+=query(tree[x].ls,tree[y].ls,L,mid,l,r);
    if(mid<r)val+=query(tree[x].rs,tree[y].rs,mid+1,R,l,r);
    return val;
}
vector<int>g[200010];
int f[200010][20];
pair<int,int> getfa(int x,int fa){
    int ans=0;
    for(int i=__lg(n);i>=0;i--)if(f[x][i]>fa)x=f[x][i],ans+=1<<i;
    return make_pair(x,ans);
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&fa[i]);
        add(fa[i],i);
    }
    dfs1(1,0);dfs2(1,0,1);
    for(int i=1;i<=n;i++)f[i][0]=i;
    scanf("%d",&m);
    while(m--){
        int u,v;scanf("%d%d",&u,&v);
        int lc=lca(u,v);
        f[u][0]=min(f[u][0],lc);f[v][0]=min(f[v][0],lc);
        g[dfn[u]].push_back(dfn[v]);g[dfn[v]].push_back(dfn[u]);
    }
    for(int i=n;i>=1;i--)f[fa[i]][0]=min(f[fa[i]][0],f[i][0]);
    for(int x=1;x<=n;x++){
        for(int i=1;i<=__lg(n);i++)f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=1;i<=n;i++){
        rt[i]=rt[i-1];
        for(int x:g[i])update(rt[i],rt[i],1,n,x);
    }
    scanf("%d",&q);
    while(q--){
        int u,v;scanf("%d%d",&u,&v);
        int lc=lca(u,v),ans=0;
        if(f[u][__lg(n)]>lc||f[v][__lg(n)]>lc){
            puts("-1");continue;
        }
        if(lc==u){
            printf("%d\n",getfa(v,lc).second+1);continue;
        }
        if(lc==v){
            printf("%d\n",getfa(u,lc).second+1);continue;
        }
        pair<int,int>p=getfa(u,lc);
        u=p.first;ans+=p.second;
        p=getfa(v,lc);
        v=p.first;ans+=p.second;
        if(query(rt[dfn[u]-1],rt[dfn[u]+sz[u]-1],1,n,dfn[v],dfn[v]+sz[v]-1))ans++;
        else ans+=2;
        printf("%d\n",ans);
    }
    return 0;
}

AGC001F Wide Swap

板刷 AGC 产物。详见 https://www.cnblogs.com/gtm1514/p/16878893.html。

CF1578B Building Forest Trails

NOIP 时代的考试题，但我没改，现在还是不会。该来的还是要来的。

Delov，然和 Kaguya 都改了。

首先断环成链，令每个点向下一个同连通块的点连边，那么任意两个连通块不会相交。设 \(p_i\) 为覆盖位置 \(i\) 的边个数（即左端点小于 \(i\)，右端点大于 \(i\)），那么相邻两点的 \(p_i\) 相差不超过 \(1\)。

考虑如何连边。不妨假设 \(u<v\)，两种情况：

  1. \(p_u\neq p_v\)，假设 \(p_u>p_v\)。找到 \(u\) 右边第一个点 \(pos\) 满足 \(p_{pos}<p_u\)，那 \(pos\) 所在的连通块一定覆盖了 \(x\) 所在连通块，因此可以合并。

  2. \(p_u=p_v\)：找到上述 \(pos\)，若 \(pos<y\) 仍按上述操作，若 \(pos\ge y\) 则说明 \(x,y\) 可以直接合并。

合并只有 \(O(n)\) 次，找 \(pos\) 可以线段树上二分，合并两个连通块时根据有无交来区间加减 \(p\)，并查集多维护个连通块左右端点即可。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int n,m;
struct node{
    #define lson rt<<1
    #define rson rt<<1|1
    int min,lz;
}tree[800010];
void pushup(int rt){
    tree[rt].min=min(tree[lson].min,tree[rson].min);
}
void pushtag(int rt,int val){
    tree[rt].min+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
    if(tree[rt].lz){
        pushtag(lson,tree[rt].lz);
        pushtag(rson,tree[rt].lz);
        tree[rt].lz=0;
    }
}
void update(int rt,int L,int R,int l,int r,int val){
    if(l<=L&&R<=r){
        pushtag(rt,val);return;
    }
    pushdown(rt);
    int mid=(L+R)>>1;
    if(l<=mid)update(lson,L,mid,l,r,val);
    if(mid<r)update(rson,mid+1,R,l,r,val);
    pushup(rt);
}
int query(int rt,int L,int R,int pos){
    if(L==R)return tree[rt].min;
    pushdown(rt);
    int mid=(L+R)>>1;
    if(pos<=mid)return query(lson,L,mid,pos);
    else return query(rson,mid+1,R,pos);
}
int queryL(int rt,int L,int R,int pos,int val){
    if(R<=pos){
        if(tree[rt].min>=val)return 0;
        if(L==R)return L;
        pushdown(rt);
        int mid=(L+R)>>1;
        if(tree[rson].min<val)return queryL(rson,mid+1,R,pos,val);
        else return queryL(lson,L,mid,pos,val);
    }
    pushdown(rt);
    int mid=(L+R)>>1,ans=0;
    if(mid<pos)ans=queryL(rson,mid+1,R,pos,val);
    if(!ans)ans=queryL(lson,L,mid,pos,val);
    return ans;
}
int queryR(int rt,int L,int R,int pos,int val){
    if(pos<=L){
        if(tree[rt].min>=val)return n+1;
        if(L==R)return L;
        pushdown(rt);
        int mid=(L+R)>>1;
        if(tree[lson].min<val)return queryR(lson,L,mid,pos,val);
        else return queryR(rson,mid+1,R,pos,val);
    }
    pushdown(rt);
    int mid=(L+R)>>1,ans=n+1;
    if(pos<=mid)ans=queryR(lson,L,mid,pos,val);
    if(ans==n+1)ans=queryR(rson,mid+1,R,pos,val);
    return ans;
}
int fa[200010],l[200010],r[200010];
int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(r[x]<l[y])update(1,1,n,r[x]+1,l[y]-1,1);
    else update(1,1,n,max(l[x],l[y]),min(r[x],r[y]),-1);
    l[x]=min(l[x],l[y]);r[x]=max(r[x],r[y]);
    fa[y]=x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=l[i]=r[i]=i;
    while(m--){
        int od,u,v;scanf("%d%d%d",&od,&u,&v);
        if(od==1){
            if(u>v)swap(u,v);
            int val1=query(1,1,n,u),val2=query(1,1,n,v);
            while(find(u)!=find(v)){
                if(val1>val2){
                    merge(u,queryR(1,1,n,u,val1));
                    val1--;
                }
                else if(val1<val2){
                    merge(v,queryL(1,1,n,v,val2));
                    val2--;
                }
                else{
                    int pos=queryR(1,1,n,u,val1);
                    if(pos<v)merge(u,pos),val1--;
                    else merge(u,v);
                }
            }
        }
        else putchar((find(u)==find(v))+'0');
    }
    puts("");
    return 0;
}

CF1129D Isolation

小清新。这题目名称让我想起来一句歌词：

Provoking black clouds in isolation

但是数据结构真就啥题都有。算了没 Ynoi 就行。

首先显然是扫描线然后拿个什么数据结构维护的。然后设 \(a_i\) 上一次出现在 \(pre_i\)，那么每个地方是 \([pre_{pre_i}+1,pre_i]\) 减 \(1\)，\([pre_i+1,i]\) 加 \(1\)，然后要查询所有 \(\le k\) 位置的 \(dp_i\) 和。这个没法 polylog，直接分块，每个块开个桶维护是这个值的 \(dp\) 值之和，修改可以整体打标记然后给答案加减一个位置的值。

写的意愿不是很大，于是贺了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int mod=998244353;
int n,k,sq,ans,a[100010],L[320],R[320],belong[100010],f[320][100010],lz[320],cnt[100010];
int dp[100010],pre[100010],pos[100010];
void build(){
    for(int i=1;i<=sq;i++){
        L[i]=R[i-1]+1;R[i]=L[i]+sq-1;
    }
    R[sq]=n;
    for(int i=1;i<=sq;i++){
        for(int j=L[i];j<=R[i];j++)belong[j]=i;
    }
}
void upd(int x,int val){
    cnt[x]-=lz[belong[x]];
    ans=(ans+val)%mod;
    f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]+val)%mod;
}
void pushdown(int x,int val){
    f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]-dp[x-1]+mod)%mod;
    if(cnt[x]+lz[belong[x]]<=k)ans=(ans-dp[x-1]+mod)%mod;
    cnt[x]+=val;
    f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]+dp[x-1])%mod;
    if(cnt[x]+lz[belong[x]]<=k)ans=(ans+dp[x-1])%mod;
}
void update(int l,int r,int val){
    if(l>r)return;
    if(belong[l]==belong[r]){
        for(int i=l;i<=r;i++)pushdown(i,val);
        return;
    }
    for(int i=l;i<=R[belong[l]];i++)pushdown(i,val);
    for(int i=L[belong[r]];i<=r;i++)pushdown(i,val);
    for(int i=belong[l]+1;i<belong[r];i++){
        if(val==1)ans=(ans-f[i][k-lz[i]]+mod)%mod;
        else ans=(ans+f[i][k-lz[i]+1])%mod;
        lz[i]+=val;
    }
}
int main(){
    scanf("%d%d",&n,&k);sq=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pre[i]=pos[a[i]],pos[a[i]]=i;
    dp[0]=1;build();
    for(int i=1;i<=n;i++){
        upd(i,dp[i-1]);
        update(pre[pre[i]]+1,pre[i],-1);
        update(pre[i]+1,i,1);
        dp[i]=ans;
    }
    printf("%d\n",dp[n]);
    return 0;
}

AGC015E Mr.Aoki Incubator

板刷 AGC，但是刚刚做到所以没题解。

先考虑如果染一个 \(i\) 那么哪些会被染。显然是前边比后缀最小值走的快的和后边比前缀最大值走的慢的。这俩都是单调的，所以若设 \(dp_i\) 为选 \(i\) 的方案数，枚举上一次染 \(j\)，从 \(dp_j\) 转移过来，那么只有 \((j,i)\) 间速度在 \([premax_j,sufmin_i]\) 中的人不会被染色，这俩都是单调的，可以双指针维护。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
int n,lsh[200010],dp[200010],sum[200010];
struct node{
    int x,v;
    bool operator<(const node&s)const{
        return x<s.x;
    }
}a[200010];
int l=1,r,L=1,R,cnt,mx[200010],mn[200010],pos[200010];
bool check(int l1,int r1,int L1,int R1){
    if(l1>r1||L1>R1)return false;
    while(r<r1){
        r++;
        if(a[r].v>=L&&a[r].v<=R)cnt++;
    }
    while(l<l1){
        if(a[l].v>=L&&a[l].v<=R)cnt--;
        l++;
    }
    while(R<R1){
        R++;
        if(pos[R]>=l&&pos[R]<=r)cnt++;
    }
    while(L<L1){
        if(pos[L]>=l&&pos[L]<=r)cnt--;
        L++;
    }
    return cnt;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].v),lsh[i]=a[i].v;
    sort(a+1,a+n+1);sort(lsh+1,lsh+n+1);
    for(int i=1;i<=n;i++)a[i].v=lower_bound(lsh+1,lsh+n+1,a[i].v)-lsh,pos[a[i].v]=i;
    for(int i=1;i<=n;i++)mx[i]=max(mx[i-1],a[i].v);
    mn[n+1]=n+1;
    for(int i=n;i>=1;i--)mn[i]=min(mn[i+1],a[i].v);
    dp[0]=sum[0]=1;
    for(int i=1,l=0;i<=n+1;i++){
        while(check(l+1,i-1,mx[l],mn[i]))l++;
        dp[i]=(sum[i-1]-(l?sum[l-1]:0)+mod)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    printf("%d\n",dp[n+1]);
    return 0;
}

AGC007E Shik and Travel

板刷 AGC 产物。详见 https://www.cnblogs.com/gtm1514/p/16897422.html。

CF1446D2 Frequency Problem (Hard Version)

超级 CF 结论题。

首先有结论：原序列的众数 \(x\) 一定是答案区间的众数之一。反证：如果不是，那每次扩展一个，由于 \(x\) 出现次数最多，那么一定有一次扩展使得 \(x\) 和另一个众数出现次数相等。（类似介值定理？）

然后 Easy Verson 直接枚举另一个众数前缀和开个桶就做完了。Hard Verson 值域大所以 8 太行。

这玩意看着就很不 polylog，直接考虑根号做法。根号做法：序列分块，值域分块，根号分治，操作分块。24 直接 pass，1 看 Easy Verson 就和序列半点关系没有，考虑根号分治。

超过根号次的不超过根号个，按照 Easy Verson 的做法暴力枚举。然后考虑剩下的。一开始想的是找所有出现位置跑双指针，有点假。实际上枚举出现次数然后使所有数出现次数都不超过这个数就能跑了，也是双指针。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int n,sq,mx,ans,a[200010],cnt[200010],sum[200010],s[400010];
void solve1(int x){
    for(int i=0;i<=2*n;i++)s[i]=0;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if(a[i]==mx)sum[i]++;
        if(a[i]==x)sum[i]--;
        if(sum[i]&&!s[sum[i]+n])s[sum[i]+n]=i;
    }
    for(int i=1;i<=n;i++)ans=max(ans,i-s[sum[i]+n]);
}
void solve2(int x){
    for(int i=1;i<=n;i++)cnt[i]=s[i]=0;
    for(int l=1,r=0;l<=n;){
        while(r<n&&cnt[a[r+1]]<x){
            r++;
            s[cnt[a[r]]]--;
            cnt[a[r]]++;
            s[cnt[a[r]]]++;
            if(s[cnt[mx]]>1)ans=max(ans,r-l+1);
        }
        s[cnt[a[l]]]--;
        cnt[a[l]]--;
        s[cnt[a[l]]]++;
        l++;
    }
}
int main(){
    scanf("%d",&n);sq=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
    for(int i=1;i<=n;i++)if(cnt[i]>=cnt[mx])mx=i;
    for(int i=1;i<=n;i++)if(cnt[i]==cnt[mx]&&i!=mx){
        printf("%d\n",n);return 0;
    }
    for(int i=1;i<=n;i++)if(cnt[i]>=sq&&i!=mx)solve1(i);
    for(int i=1;i<=sq;i++)solve2(i);
    printf("%d\n",ans);
    return 0;
}

CF765F Souvenirs

典题。

先只考虑 \(j<i,a_j<a_i\) 的二元组 \((j,i)\)，然后值域翻过来再做一遍。对右端点考虑可能成为答案的 \(j\)，那么设上一个贡献的是 \(j_0\)，它左边的 \(j_1\) 可能有贡献则 \(a_i-a_{j_1}\le\dfrac 12(a_i-a_{j_0})\)，于是暴跳只会跳 \(O(\log a_i)\) 次，复杂度是对的。因此扫描线，权值线段树维护 \(a\)，查询套上个树状数组维护后缀最大值就行了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int inf=1000000000;
int n,m,ans[300010],a[100010];
vector<pair<int,int> >q[300010];
struct node{
    #define lson tree[rt].ls
    #define rson tree[rt].rs
    int ls,rs,max;
}tree[100010<<5];
int t,rt;
void pushup(int rt){
    tree[rt].max=max(tree[lson].max,tree[rson].max);
}
void update(int &rt,int L,int R,int pos,int val){
    if(!rt)rt=++t;
    if(L==R){
        tree[rt].max=val;return;
    }
    int mid=(L+R)>>1;
    if(pos<=mid)update(lson,L,mid,pos,val);
    else update(rson,mid+1,R,pos,val);
    pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
    if(!rt)return 0;
    if(l<=L&&R<=r)return tree[rt].max;
    int mid=(L+R)>>1,val=0;
    if(l<=mid)val=max(val,query(lson,L,mid,l,r));
    if(mid<r)val=max(val,query(rson,mid+1,R,l,r));
    return val;
}
struct BIT{
    int c[100010];
    #define lowbit(x) (x&-x)
    void update(int x,int val){
        while(x)c[x]=min(c[x],val),x-=lowbit(x);
    }
    int query(int x){
        int sum=inf;
        while(x<=n)sum=min(sum,c[x]),x+=lowbit(x);
        return sum;
    }
}c;
void solve(){
    for(int i=1;i<=n;i++)c.c[i]=inf;
    for(int i=1;i<=n;i++){
        int pre=0;
        while(pre<=a[i]){
            int pos=query(rt,0,inf,pre,a[i]);
            if(!pos)break;
            c.update(pos,a[i]-a[pos]);
            pre=(a[pos]+a[i]+2)>>1;
        }
        for(pair<int,int>p:q[i])ans[p.second]=min(ans[p.second],c.query(p.first));
        update(rt,0,inf,a[i],i);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r;scanf("%d%d",&l,&r);
        q[r].push_back(make_pair(l,i));ans[i]=inf;
    }
    solve();
    for(int i=1;i<=n;i++)a[i]=inf-a[i];
    for(int i=1;i<=t;i++)tree[i].ls=tree[i].rs=tree[i].max=0;t=0;rt=0;
    solve();
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

CF1458D Flip and Reverse

《数据结构》

欧拉回路都能在数据结构专题里边了，那你咋不塞个多项式进去呢？哦我懂了，他看见 CF 有 data structure 标签就塞进去了。

按照原串建图，\(0\) 为 \(-1\)，\(1\) 为 \(1\) 做前缀和 \(s\)，连 \(s_i\rightarow s_{i+1}\) 的边。然后考虑翻转干了什么事。发现翻转的区间 \(l,r\) 满足 \(s_{l-1}=s_r\)，那就是把一个环倒过来，于是连无向边跑一发字典序最小的欧拉路就完。你甚至都不用建图。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int n,cnt[1000010][2];
char s[500010];
int main(){
    int tim;scanf("%d",&tim);
    while(tim--){
        scanf("%s",s+1);n=strlen(s+1);
        int p=0;
        for(int i=1;i<=n;i++){
            cnt[n+p][s[i]-'0']++;
            if(s[i]=='0')p--;
            else p++;
        }
        p=0;
        for(int i=1;i<=n;i++){
            if(cnt[n+p][0]&&cnt[n+p-1][1])putchar('0'),cnt[n+p][0]--,p--;
            else if(cnt[n+p][1]&&cnt[n+p+1][0])putchar('1'),cnt[n+p][1]--,p++;
            else if(cnt[n+p][0])putchar('0'),cnt[n+p][0]--,p--;
            else if(cnt[n+p][1])putchar('1'),cnt[n+p][1]--,p++;
        }
        puts("");
    }
    return 0;
}

标签：数据结构,int,200010,dep,专题,100010,ans,include
From： https://www.cnblogs.com/gtm1514/p/17432963.html

相关文章

  • 数据结构期末复习——图的遍历
    图的遍历：1.定义：从某个结点出发访问遍图中结点，且使每个结点仅被访问一次图的遍历具有复杂性，主要体现在以下几点1.遍历没有规定从哪个结点开始访问，因此从任意结点开始访问均可2.图的一个结点可以连接多个结点，因此无法确定访问此结点之后应该访问哪一个结点3.如果一个图中存在回......
  • 5_24_打卡_数据结构之循环队列
    //循环队列可存储数据数量是maxsize-1//队列长度为（front-rear+maxsize）%maxsize//队列为空时front==rear//队列满时（front+1）%maxsize==rear；#defineMAXSIZE5#include<iostream>usingnamespacestd;typedefstructqueue{ intfront; intrear; intdata[MAXSIZE];}......
  • 关于redis的描述、数据结构、持久化学习笔记
    前言本文围绕面试问题、redis学习记录。本文是个人的笔记，会有遗漏或含糊的地方。描述下redisredis是一款非关系型数据库，它是以key-value的形式存在数据，因为它的数据在内存中所以它的读写速度极高。当然它支持持久化，将数据以二进制形式或者以命令的形式持久化到磁盘。然后......
  • redis专题六：redis 删除策略、淘汰策略、数据库与缓存数据一致性、事物、发布订阅
    文章目录一、删除策略二、淘汰策略三、数据库与缓存数据一致性四、redis事务五、redis发布订阅一、删除策略redis使用：惰性删除+定期删除1、定时删除–>以CPU内存换redis内存定时删除过期的缓存值2、惰性删除–>以redis内存换CPU内存查询到该key时如果过期，删除该过期的缓存值......
  • 5.22 字符串专题模拟赛
    T1P7469[NOIOnline2021提高组]积木小赛签到题，考虑固定\(\texttt{Bob}\)的左端点，双指针去判断是否匹配即可，时间复杂度\(O(n^2)\)。T2P7114[NOIP2020]字符串匹配考虑到\(AB\)必然是一个前缀，枚举\(AB\)长度\(len\)，\(C\)的长度只有\(\lfloor\dfrac{n-len}{l......
  • 数据结构—树(自学笔记）（郝斌）
    文章目录树的定义专业定义通俗的定义相关术语树的分类一般树二叉树二叉树的分类二叉树的性质对于第一条来说是显然的，i=1时就是根节点。i>1时，比如节点7，它的双亲就是•⌊......
  • 2.6 异质的数据结构
    结构C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息，指示每个字段(......
  • 《数据结构与算法》之数据的顺存储
    导言：数据结构中，对一些数据序列我们使用的是顺序的方式存储，比较常见的有数组，链表，这些都是最基本的顺序存储的结构，我们会用几个简单的例子来描述顺序存储的方式和演变我们知道顺序存储中有链表，有链表我们就必须知道指针，所以我们先复习一下指针，再来看顺序存储一.指针在C语言中，我......
  • 图论专题 1
    喜报：图论专题1前五题都是uoj题。后边是WC2007剪刀石头布和两个*3100。喜报：我不会图论！观察了一下发现除了我们以外做这些题的确实都不是活人。那我们在和波特对战！很恐怖！随手交了一发新年的追逐战居然最优解了。该说uoj卡多项式全家桶最优解的没多少吗。速度明显慢下来......
  • 《数据结构与算法》之十大基础排序算法
    一.冒泡排序什么是冒泡排序？冒泡排序是一种交换排序，它的思路就是在待排序的数据中，两两比较相邻元素的大小，看是否满足大小顺序的要求，如果满足则不动，如果不满足则让它们互换。然后继续与下一个相邻元素的比较，一直到一次遍历完成。一次遍历的过程就被成为一次冒泡，一次冒泡的结束至......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99