さなぷり。

Take me with you。


< Click Here >
sanapri
さなぷり。
Take me with you。
66
2
0

Luogu | P2042 [NOI 2005] 维护数列 | 数据结构 | 平衡树


Description

请写一个程序,要求维护一个数列,支持以下 $6$ 种操作:(请注意,格式栏中的下划线_表示实际输入文件中的空格)

2042


Input Format

输入文件的第 $1$ 行包含两个数 $N$ 和 $M$,$N$ 表示初始时数列中数的个数,$M$ 表示要进行的操作数目。

第 $2$ 行包含 $N$ 个数字,描述初始时的数列。 以下 $M$ 行,每行一条命令,格式参见问题描述中的表格。


Output Format

对于输入数据中的 GET-SUMMAX-SUM 操作,向输出文件依次打印结果,每个答案(数字)占一行。


Input Sample

Sample 01

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM


Output Sample

Sample 01

-1
10
1
10


Data Range

$1 \le M \le 2\times 10^5$。

任何时候数列中最多含有 $5\times 10^5$ 个数。

数列中插入数字总数不超过 $4 \times 10^6$。

数列中任何一个数字均在 $[-10^3,10^3]$ 以内。


Solution

Splay 维护数列。

考虑用 $lsum[x]$ 维护以 x 为根的子树代表的区间中包含区间左端点的最大前缀和,$rsum[x]$ 维护以 x 为根的子树代表的区间中包含区间右端点的最大后缀和,$msum[x]$ 维护区间最大子段和。

需要注意两点:

  • 最大子段和至少包含一个元素。
  • 垃圾回收。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define Rel(x) ch[fa[x]][1]==x
#define Link(x,y,z) fa[x]=y,ch[y][z]=x

using std::max;
using std::swap;

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

int N;
int M;
int top;
int root;

int fa[500010];
int seq[500010];
int val[500010];
int sum[500010];
int size[500010];

int lsum[500010];
int rsum[500010];
int msum[500010];

int r_tag[500010];
int m_tag[500010];

int stk[500010];

int ch[500010][2];

char inst[15];

void Maintain(int x){
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
    lsum[x]=max(lsum[ch[x][0]],sum[ch[x][0]]+val[x]+lsum[ch[x][1]]);
    rsum[x]=max(rsum[ch[x][1]],sum[ch[x][1]]+val[x]+rsum[ch[x][0]]);
    msum[x]=max(rsum[ch[x][0]]+val[x]+lsum[ch[x][1]],max(msum[ch[x][0]],msum[ch[x][1]]));
    return;
}

void Adjust(int x){
    if(m_tag[x]){
        rep(i,0,1){
            m_tag[ch[x][i]]=1;
            val[ch[x][i]]=val[x];
            sum[ch[x][i]]=val[x]*size[ch[x][i]];
            if(val[x]>0)
                lsum[ch[x][i]]=rsum[ch[x][i]]=msum[ch[x][i]]=sum[ch[x][i]];
            else
                lsum[ch[x][i]]=rsum[ch[x][i]]=0,msum[ch[x][i]]=val[ch[x][i]];
        }
        r_tag[x]=0;
        m_tag[x]=0;
    }
    if(r_tag[x]){
        int y;
        rep(i,0,1){
            y=ch[x][i];
            r_tag[y]^=1;
            swap(lsum[y],rsum[y]);
            swap(ch[y][0],ch[y][1]);
        }
        r_tag[x]=0;
    }
    return;
}

void Rotate(int x){
    int y=fa[x];
    int z=fa[y];
    bool d=Rel(x);
    Link(x,z,Rel(y));
    Link(ch[x][!d],y,d);
    Link(y,x,!d);
    Maintain(y);
    Maintain(x);
    return;
}

void Splay(int x,int dest){
    int y,z;
    while(fa[x]!=dest){
        y=fa[x],z=fa[y];
        if(z!=dest)
            Rel(x)^Rel(y)?Rotate(x):Rotate(y);
        Rotate(x);
    }
    if(!dest)
        root=x;
    return;
}

int Kth(int k){
    int u=root;
    if(size[u]<k)
        return -1;
    while(1){
        Adjust(u);
        if(size[ch[u][0]]>=k)
            u=ch[u][0];
        else if(size[ch[u][0]]+1>=k)
            return u;
        else{
            k-=size[ch[u][0]]+1;
            u=ch[u][1];
        }
    }
    return -1;
}

int Build(int L,int R){
    if(L>R)
        return 0;
    int now=stk[top--];
    int mid=(L+R)>>1;
    size[now]=1;
    val[now]=seq[mid];
    if(seq[mid]>0)
        lsum[now]=rsum[now]=msum[now]=sum[now]=seq[mid];
    else
        lsum[now]=rsum[now]=0,msum[now]=sum[now]=seq[mid];
    if(L==R) return now;
    ch[now][0]=Build(L,mid-1);
    ch[now][1]=Build(mid+1,R);
    if(ch[now][0])
        fa[ch[now][0]]=now;
    if(ch[now][1])
        fa[ch[now][1]]=now;
    Maintain(now);
    return now;
}

void Empty(int x){
    fa[x]=0;
    val[x]=0;
    sum[x]=0;
    size[x]=0;
    ch[x][0]=ch[x][1]=0;
    m_tag[x]=r_tag[x]=0;
    lsum[x]=rsum[x]=msum[x]=0;
    stk[++top]=x;
    return;
}

void Travel(int x){
    if(ch[x][0])
        Travel(ch[x][0]);
    if(ch[x][1])
        Travel(ch[x][1]);
    Empty(x);
    return;
}

void Delete(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    Travel(ch[tl][0]);
    ch[tl][0]=0;
    Maintain(tl);
    Maintain(hd);
    return;
}

void Modify(int s,int k,int v){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    val[x]=v;
    m_tag[x]=1;
    sum[x]=size[x]*v;
    if(v>0)
        lsum[x]=rsum[x]=msum[x]=sum[x];
    else
        lsum[x]=rsum[x]=0,msum[x]=v;
    Maintain(tl);
    Maintain(hd);
    return;
}

void Reverse(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    r_tag[x]=1;
    swap(lsum[x],rsum[x]);
    swap(ch[x][0],ch[x][1]);
    Maintain(tl);
    Maintain(hd);
    return;
}

void Insert(int s,int k){
    int hd=Kth(s+1);
    int tl=Kth(s+2);
    Splay(hd,0);
    Splay(tl,hd);
    ch[tl][0]=Build(1,k);
    if(ch[tl][0])
        fa[ch[tl][0]]=tl;
    Maintain(tl);
    Maintain(hd);
    return;
}

void GetSum(int s,int k){
    int hd=Kth(s);
    int tl=Kth(s+k+1);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    printf("%d\n",sum[x]);
    return;
}

void GetMaxSum(){
    int hd=Kth(1);
    int tl=Kth(size[root]);
    Splay(hd,0);
    Splay(tl,hd);
    int x=ch[tl][0];
    printf("%d\n",msum[x]);
    return;
}

int main(){
    int pos,cnt,v;
    rep(i,1,500005)
        stk[++top]=i;
    rep(i,1,2)
        seq[i]=-0x2f2f2f2f;
    msum[0]=-0x2f2f2f2f;
    root=Build(1,2);
    Read(N);
    Read(M);
    rep(i,1,N)
        scanf("%d",&seq[i]);
    Insert(0,N);
    while(M--){
        scanf("%s",inst+1);
        if(inst[1]=='I'){
            Read(pos);
            Read(cnt);
            rep(i,1,cnt)
                scanf("%d",&seq[i]);
            Insert(pos,cnt);
        }
        else if(inst[1]=='D'){
            Read(pos);
            Read(cnt);
            Delete(pos,cnt);
        }
        else if(inst[1]=='R'){
            Read(pos);
            Read(cnt);
            Reverse(pos,cnt);
        }
        else if(inst[1]=='G'){
            Read(pos);
            Read(cnt);
            GetSum(pos,cnt);
        }
        else{
            if(inst[3]=='K'){
                Read(pos);
                Read(cnt);
                scanf("%d",&v);
                Modify(pos,cnt,v);
            }
            else
                GetMaxSum();
        }
    }
    return 0;
}

Luogu | P3960 [NOIP2017] Phalanx 列队 | 数据结构 | BIT / 线段树 / 平衡树


Description

Sylvia 是一个热爱学习的女孩子。

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。

Sylvia 所在的方阵中有$n \times m$名学生,方阵的行数为 $n$,列数为 $m$。

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 $1$ 到 $n \times m$ 编上了号码(参见后面的样例)。即:初始时,第 $i$ 行第 $j$ 列 的学生的编号是$(i-1)\times m + j$。

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 $q$ 件这样的离队事件。每一次离队事件可以用数对$(x,y)$描述,表示第 $x$ 行第 $y$ 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:

  1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 $x$ 行第 $m$ 列。
  2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 $n$ 行第 $m$ 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后, 下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 $n$ 行 第 $m$ 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。


Input Format

输入共 $q+1$ 行。

第 $1$ 行包含 $3$ 个用空格分隔的正整数 $n, m, q$ ,表示方阵大小是 $n$ 行 $m$ 列,一共发生了 $q$ 次事件。

接下来 $q$ 行按照事件发生顺序描述了 $q$ 件事件。每一行是两个整数 $x, y$,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 $x$ 行第 $y$ 列。


Output Format

按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。


Input Sample

Sample 01

2 2 3
1 1
2 2
1 2


Output Sample

Sample 01

1
1
4


Data Range

$1 <= n,m,q <= 3×10^5 $。


Solution

观察一下,可以发现,每次移动后,除了离开的学生和补缺口的最多两个学生,$n$行中前$m-1$列学生的左右的相对位置没有变化,最后一列学生上下的相对位置没有变化。

考虑用数据结构维护$n$行的前$m-1$个元素,单独维护最后一列的元素。这样对于每次事件,只需要从第$x$行中拿出第$y$个元素,从最后一列拿出第$x$个元素放在第$x$行的第$m-1$个位置,然后把最开始拿出来的元素放在最后一列的最后一个。

这里的做法是建立$2n+1$棵线段树,对于每行的前$m-1$个元素建立两颗线段树:一颗维护初始状态下的序列(左),一颗维护询问添加到某一行的末尾时的序列(右)。每一棵线段树都需要动态开点(当然为了偷懒,最后一列那一颗不需要)。问题在于初始状态下左树是一颗满树,右树是一颗空树,所以他们的结点的大小需要分开计算。这里对于左树的结点大小,记录的是区间删除元素的个数,对于右树则是区间存在元素的个数(所以这样kth操作也比较麻烦)。

另一种方法是维护$n+1$棵平衡树,意义与上面大致相同,初始状态下每棵树只有一个结点,代表这一行的前$m-1$个元素,即每一个点维护一个区间。对于每一次操作,可以将一个区间的点拆成多个点(前面的部分,中间取出来的那一个点,后面的部分)。同样需要面对kth不是太好写的问题。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define LC lch[now]
#define RC rch[now]
#define mid ((L+R)>>1)
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

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

struct data{
    int size; long long val;
}d[10000005],T,D;

int node,N,M,Q;
int root[300005][2],lch[10000005],rch[10000005],last[300005];

void upload(int now){
    d[now].size=d[LC].size+d[RC].size; return;
}

void build(int &now,int L,int R){ now=++node;
    if(L==R) { d[now].size=1; d[now].val=(long long)L*M; return; }
    build(LC,L,mid); build(RC,mid+1,R); upload(now); return;
}

void Build(int id){
    root[id][0]=++node; root[id][1]=++node; return;
}

data kth_preT(int now,int td,int L,int R,int K){
    if(L==R){ return (data){L,d[now].val?d[now].val:(long long)(td-1)*M+L}; }
    if(!LC) LC=++node; if((mid-L+1-d[LC].size)>=K) return kth_preT(LC,td,L,mid,K);
    if(!RC) RC=++node; return kth_preT(RC,td,mid+1,R,K-(mid-L+1-d[LC].size));
}

data kth_sufT(int now,int L,int R,int K){
    if(L==R) return (data){L+M-1,d[now].val};
    if(d[LC].size>=K) return kth_sufT(LC,L,mid,K);
    return kth_sufT(RC,mid+1,R,K-d[LC].size); 
}

data Kth(int id,int K){
    if((M-1-d[root[id][0]].size)>=K) return kth_preT(root[id][0],id,1,M-1,K);
    else return kth_sufT(root[id][1],1,Q,K-(M-1-d[root[id][0]].size));
}

void del_preT(int now,int L,int R,int pos){
    if(L==R) { d[now].size=1; d[now].val=0; return; }
    if(pos<=mid) del_preT(LC,L,mid,pos);
    else del_preT(RC,mid+1,R,pos); upload(now); return;
}

void del_sufT(int now,int L,int R,int pos){
    if(L==R) { d[now].size=0; d[now].val=0; return; }
    if(pos<=mid) del_sufT(LC,L,mid,pos);
    else del_sufT(RC,mid+1,R,pos); upload(now); return;
}

void Del(int id,int pos){
    if(pos<=(M-1)) del_preT(root[id][0],1,M-1,pos);
    else del_sufT(root[id][1],1,Q,pos-M+1);
}

void upd_sufT(int now,int L,int R,int pos,long long val){
    if(L==R) { d[now].val=val; d[now].size=1; return; }
    if(pos<=mid) {
        if(!LC) LC=++node; upd_sufT(LC,L,mid,pos,val);
    } else{
        if(!RC) RC=++node; upd_sufT(RC,mid+1,R,pos,val); 
    }upload(now); return;
}

int main(){
    int xp,yp; Read(N); Read(M); Read(Q);
    rep(i,1,N) Build(i);
    build(root[N+1][0],1,N); root[N+1][1]=++node;
    rep(i,1,Q){
        Read(xp); Read(yp);
        if(yp==M){
            if(d[root[N+1][0]].size>=xp){
                T=kth_sufT(root[N+1][0],1,N,xp);
                T.size=T.size-M+1;
            }
            else{
                T=kth_sufT(root[N+1][1],1,Q,xp-d[root[N+1][0]].size);
                T.size=T.size-M+1; T.size+=N;
            } printf("%lld\n",T.val); 
            if(T.size<=N) del_sufT(root[N+1][0],1,N,T.size);
            else del_sufT(root[N+1][1],1,Q,T.size-N);
            upd_sufT(root[N+1][1],1,Q,++last[N+1],T.val);
        }else{
            T=Kth(xp,yp); printf("%lld\n",T.val);
            Del(xp,T.size);
            if(d[root[N+1][0]].size>=xp){
                D=kth_sufT(root[N+1][0],1,N,xp);
                D.size=D.size-M+1;
            }
            else{
                D=kth_sufT(root[N+1][1],1,Q,xp-d[root[N+1][0]].size);
                D.size=D.size-M+1; D.size+=N;
            }if(D.size<=N) del_sufT(root[N+1][0],1,N,D.size);
            else del_sufT(root[N+1][1],1,Q,D.size-N);
            upd_sufT(root[xp][1],1,Q,++last[xp],D.val);
            upd_sufT(root[N+1][1],1,Q,++last[N+1],T.val);
        }
    }
    return 0;
}

Luogu | P2860 Redundant Paths | 图论 | Tarjan


Description

为了从$N$个草场中的一个走到另一个,贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。

每对草场之间已经有至少一条路径。给出所有$R$条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。两条路径相互分离,是指两条路径没有一条重合的道路。但是,两条分离的路径上可以有一些相同的草场。对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路。


Input Format

第一行两个整数$N,M$,分别为草场数和原来的路数。

接下来$M$行每行两个整数$u,v$,代表一条路径的两个端点。


Output Format

一行一个正整数,表示最少的新建道路的数量。


Input Sample

Sample 01

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7


Output Sample

Sample 01

2


Data Range

$1 <= N,M <= 5×10^4 $。


Solution

两个点之间要有至少两条相互分离的路径,则这两个点之间的必经路径一定不能有桥,或者说这两个点的在一个环上,即两个点都在同一个边双连通分量内。

考虑将原本就已经在边双连通分量里的点缩成一个点,这样就得到了一棵树。接下来考虑将这棵树通过加边变成一个边双连通分量。当前树上的每一条边都是一个桥。可以将两个度为$1$的点之间连一条边,这样这两个点就可以跟上面的点构成一个环。可能剩下一个度为$1$的点,再随便连一条边即可。


Code

#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::stack;

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

struct edge{
    int from,to,next,id;
}e[200005];

int N,M,node,dfs_clock,ebcc;
int first[50005],last[50005],deg[50005],low[50005],dfn[50005],belong[50005];

stack<int>stk;

void addedge(int u,int v,int id){
    e[++node]=(edge){u,v,0,id}; if(first[u]==0) first[u]=node;
    else e[last[u]].next=node; last[u]=node; return;
}

void tarjan(int x,int fd){ stk.push(x);
    low[x]=dfn[x]=++dfs_clock;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to; if(!dfn[y]){
            tarjan(y,e[p].id); 
            low[x]=min(low[x],low[y]);
        }else if(e[p].id!=fd) low[x]=min(low[x],dfn[y]);
    }if(dfn[x]==low[x]){
        belong[x]=++ebcc;
        while(stk.top()!=x){
            belong[stk.top()]=ebcc;
            stk.pop();
        }stk.pop();
    }
}

void init(){ int f,t;
    Read(N); Read(M);
    rep(i,1,M){
        Read(f); Read(t);
        addedge(f,t,i); addedge(t,f,i);
    }
}

void solve(){ int cnt=0;
    rep(i,1,N) if(!dfn[i]) tarjan(i,0);
    rep(x,1,N){
        for(int p=first[x];p;p=e[p].next){
            int y=e[p].to; if(belong[x]!=belong[y]){
                deg[belong[x]]++; deg[belong[y]]++;
            }
        }
    } rep(i,1,ebcc) cnt+=deg[i]==2;
    printf("%d\n",(cnt+1)/2); return;
}

int main(){
    init();
    solve();
    return 0;
}

一中OJ | C159-5 / BZOJ2935 [POI1999] 原始生物 | 图论 | 欧拉图


Description

原始生物的遗传密码是一个自然数的序列 $K=(a_1,...,a_n)$。原始生物的特征是指在遗传密码中连续出现的数对​$(l,r)$,即存在自然数 ​$i$ 使得 ​$l=a_i$ 且 ​$r=a_{i+1}$。在原始生物的遗传密码中不存在 (p,p) 形式的特征。
请设计一个程序:

  • 读入一系列的特征。
  • 计算包含这些特征的最短的遗传密码。
  • 将结果输出。

Input Format

第一行是一个整数$n$ ,表示特征的总数。

在接下来的$n$行里,每行都是一对由空格分隔的自然数$l$和$r$。

数对$(l,r)$是原始生物的特征之一。输入文件中的特征不会有重复。


Output Format

唯一一行,一个整数,包含了所有特征的遗传密码的最小长度。


Input Sample

Sample 01

12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6


Output Sample

Sample 01

15


Data Range

$1 <= N <= 10^6 $。$ 1 <= l,r <= 2×10^3$。


Solution

根据输入数据建图,可以发现如果一条边接一条边能最大程度减小答案长度。

对于任意一个连通分量,可以考虑将图通过加边建成一张具有欧拉路径的图(入度少的点连向出度少的点,最后除了起点和终点所有点的入度和出度都相等)。单个点在欧拉路径上出现的次数为$\max(cd_i,rd_i)$。

如果整个连通分量上有一个欧拉环,则答案还要$+1$(最终会回到起点)。

需要注意的是,数据中可能有一些点没有边,需要跳过。


Code

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::vector;

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

struct edge{
    int from,to,next;
}e[2000005];

int node,cc,N,M,ans;
int first[2005],last[2005],cd[2005],rd[2005],belong[2005],exist[2005];

vector<int>ccs[2005];

void addedge(int u,int v){
    e[++node]=(edge){u,v,0}; if(first[u]==0) first[u]=node;
    else e[last[u]].next=node; last[u]=node; return;
}

void dfs(int x){ belong[x]=cc;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to; if(!belong[y]) dfs(y);
    } ccs[cc].push_back(x); return;
}

void init(){ int f,t;
    Read(M); rep(i,1,M){
        Read(f); Read(t); rd[t]++,cd[f]++; exist[t]=exist[f]=1;
        addedge(f,t); addedge(t,f); N=max(N,max(f,t));
    }rep(i,1,N) if(!belong[i]&&exist[i]) { ++cc; dfs(i); }
    rep(i,1,cc){ bool valid=true;
        rep(j,0,ccs[i].size()-1){
            if(rd[ccs[i][j]]!=cd[ccs[i][j]]){
                valid=false;break;
            }
        }ans+=valid;
    }rep(i,1,N) ans+=max(cd[i],rd[i]);
    printf("%d\n",ans); return;
}

int main(){
    init();
    return 0;
}

Luogu | P2515 [HAOI2010] 软件安装 | 图论 / 动态规划 | Tarjan + 树上DP


Description

现在我们的手头有$N$个软件,对于一个软件$i$,它要占用$W_i$的磁盘空间,它的价值为$V_i$。我们希望从中选择一些软件安装到一台磁盘容量为$M$计算机上,使得这些软件的价值尽可能大(即$V_i$的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件$i$只有在安装了软件$j$(包括软件$j$的直接或间接依赖)的情况下才能正确工作(软件$i$依赖软件$j$)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为$0$。

我们现在知道了软件之间的依赖关系:软件$i$依赖软件$D_i$。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则$D_i=0$,这时只要这个软件安装了,它就能正常工作。


Input Format

第$1$行:$N,M$。

第$2$行:$W_1,W_2, ... W_i, ..., W_n$ 。

第$3$行:$V_1, V_2, ..., V_i, ..., V_n$ 。

第$4$行:$D_1, D_2, ..., D_i, ..., D_n$ 。


Output Format

一个整数,代表最大价值。


Input Sample

Sample 01

3 10
5 5 6
2 3 4
0 1 1


Output Sample

Sample 01

5


Data Range

$0\leq N\leq 100, 0\leq M\leq 500$。$0\leq W_i\leq M$。$0\leq V_i\leq 1000$。$0\leq D_i\leq N, D_i≠i$。


Solution

软件的依赖关系可能会构成环,也就是说想安装这个环上的软件必须得一次性安装完。所以考虑将环缩成一个点。

接下来,建立一个价值和空间均为$0$的虚拟根,从它开始向其它入度为$0$的点连边,跑树上背包即可。


Code

#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::stack;

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

struct edge{
    int from,to,next;
}e[105],E[105];

int N,M,node,dfs_clock,ans,scc=1;
int first[105],last[105],belong[105],size[105],w[105],v[105],rd[105];
int tw[105],tv[105],low[105],dfn[105],dl[105],df[105],d[105][505];

stack<int>stk;

void addedge(int u,int v){
    e[++node]=(edge){u,v,0}; if(first[u]==0) first[u]=node;
    else e[last[u]].next=node; last[u]=node; return;
}

void Addedge(int u,int v){
    E[++node]=(edge){u,v,0}; if(df[u]==0) df[u]=node;
    else E[dl[u]].next=node; dl[u]=node; return;
}

void tarjan(int x){
    stk.push(x); low[x]=dfn[x]=++dfs_clock;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); }
        else if(!belong[y]) low[x]=min(low[x],dfn[y]);
    }if(low[x]==dfn[x]){
        belong[x]=++scc; size[scc]=1;
        while(stk.top()!=x){
            belong[stk.top()]=scc; size[scc]++; stk.pop();
        }stk.pop();
    }return;
}

void treed(int x){
    rep(i,0,M) d[x][i]=-0x7f7f7f7f;
    d[x][tw[x]]=tv[x];
    for(int p=df[x];p;p=E[p].next){
        int y=E[p].to; treed(y);
        for(int i=M-tw[x];i>=0;i--) rep(j,0,i){
            if(d[x][i-j+tw[x]]>=0&&d[y][j]>=0)
            d[x][i+tw[x]]=max(d[x][i+tw[x]],d[x][i-j+tw[x]]+d[y][j]);
        } 
    }return;
}

int main(){ int fa;
    Read(N); Read(M);
    rep(i,1,N) Read(w[i]);
    rep(i,1,N) Read(v[i]);
    rep(i,1,N) { Read(fa); addedge(fa,i); }
    rep(i,1,N) if(!dfn[i]) tarjan(i);
    node=0; rep(x,1,N){
        tw[belong[x]]+=w[x],tv[belong[x]]+=v[x];
        for(int p=first[x];p;p=e[p].next){
            int y=e[p].to; if(belong[x]!=belong[y]){
                Addedge(belong[x],belong[y]); rd[belong[y]]=1;
            }
        }
    }rep(i,2,scc) if(rd[i]==0) Addedge(1,i); 
    treed(1); rep(i,1,M) ans=max(ans,d[1][i]);
    printf("%d\n",ans); return 0;
}

一中OJ | C159-3 / BZOJ3033 太鼓达人 | 图论 | 欧拉路径


Description

七夕祭上,Vani牵着cl的手,在明亮的灯光和欢乐的气氛中愉快地穿行。这时,在前面忽然出现了一台太鼓达人机台,而在机台前坐着的是刚刚被精英队伍成员XLkPoet_shylydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣,applepi果断闪人,于是cl拿起鼓棒准备挑战。然而即使是在普通难度下,cl的路人本性也充分地暴露了出来。一曲终了,不但没有过关,就连鼓都不灵了。Vani十分过意不去,决定帮助工作人员修鼓。

鼓的主要元件是$M$个围成一圈的传感器。每个传感器都有开和关两种工作状态,分别用$1$和$0$表示。显然,从不同的位置出发沿顺时针方向连续检查$K$个传感器可以得到$M$个长度为$K$的01串。Vani知道这$M$个01串应该是互不相同的。而且鼓的设计很精密,$M$会取到可能的最大值。现在Vani已经了解到了$K$的值,他希望你求出$M$的值,并给出字典序最小的传感器排布方案。


Input Format

一个整数$K$。


Output Format

一个整数$M$和一个二进制串,由一个空格分隔。分别表示可能的最大的$M$,以及字典序最小的排布方案,字符$0$表示关,$1$表示开。你输出的串的第一个字和最后一个字是相邻的。


Input Sample

Sample 01

3


Output Sample

Sample 01

8 00010111


Data Range

$1 <= K <= 11 $。


Solution

手玩样例,容易看出这个循环序列长度是$2 ^ K$,并且一定是由一串长度为$K$的$0$开头。

可以用欧拉回路解(当然有更好的做法)。

考虑建模:将各个数字建成点($0 \sim 2^K-1$),然后每个点最多能连两条合法的边。但是这样就不能用欧拉回路的方法做了。所以更换一个模型。

考虑只建两个点。表示当前长串的末尾的数字为$0$或者为$1$。这样就可以在中间连$2^K$条边,然后考虑从$0$开始找一条字典序最小的欧拉回路即可。

但是这样还有一个问题,可能走边的顺序不合法,导致$M$的长度超标。所以可以用模型$1$来判定合法,模型$2$跑欧拉回路,若不合法则回溯。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

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

struct edge{
    int from,to,next,id;
}e[5005];

int N,node,cnt;
char str[2049][13],path[2049];
bool vis[2049],valid[2049][2049];
int first[2049],last[2049],ord[2049];

void addedge(int u,int v,int id){
    e[++node]=(edge){u,v,0,id}; if(first[u]==0) first[u]=node;
    else e[last[u]].next=node; last[u]=node; return;
}

void Init(){
    Read(N); printf("%d ",1<<N);
    return;
}

void Generate(){
    rep(i,0,(1<<N)-1){
        rep(j,0,N-1) if(i&1<<j) str[i][N-j]=1;
    }rep(i,0,(1<<N)-1)
        addedge(str[i][N-1],str[i][N],i);
    valid[0][0]=1; rep(i,0,(1<<N)-1){
        int dest=0; rep(j,2,N){
            dest+=str[i][j]<<(N-j+1);
        }valid[i][dest]=1;
        valid[i][dest+1]=1;
    }
}

bool DFS(int x,int lastE,int dep){ bool ret=0;
    if(dep==(1<<N)+1) return true;
    for(int p=first[x];p;p=e[p].next){
        if(!vis[e[p].id]){
            if(valid[lastE][e[p].id]){
                vis[e[p].id]=1; ord[dep]=e[p].id;
                ret=DFS(e[p].to,e[p].id,dep+1);
                if(!ret) vis[e[p].id]=0,ord[dep]=0; 
            }
        }
    }return ret;
}

void GetPath(){
    for(int cnt=N,i=1,Lim=1<<N;cnt<=Lim;cnt++,i++){
        path[cnt]=str[ord[i]][N];
    }rep(i,1,1<<N) printf("%d",path[i]);
}

int main(){
    Init();
    Generate();
    DFS(0,0,1);
    GetPath();
    return 0;
}

Luogu | P2403 [SDOI2010] 所驼门王的宝藏 | 图论 / 动态规划 | Tarjan


Description

在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:

  1. “横天门”:由该门可以传送到同行的任一宫室;
  2. “纵寰门”:由该门可以传送到同列的任一宫室;
  3. “自由门”:由该门可以传送到以该门所在宫室为中心周围$8$格中任一宫室(如果目标宫室存在的话)。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。

现在Henry已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。


Input Format

第一行给出三个正整数$N, R, C$。

以下$N$行,每行给出一扇传送门的信息,包含三个正整数$x_i, y_i, T_i$,表示该传送门设在位于第$x_i$行第$y_i$列的藏宝宫室,类型为$T_i$。

$T_i$是一个$1\sim 3$中的整数,$1$表示可以传送到第$x_i$行任意一列的“横天门”,$2$表示可以传送到任意一行第$y_i$列的“纵寰门”,$3$表示可以传送到周围$8$格宫室的“自由门”。


Output Format

一个正整数,表示你确定的路线所经过不同藏宝宫室的最大数目。


Input Sample

Sample 01

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1


Output Sample

Sample 01

9


Data Range

$1 <= N <= 5×10^5 $。$ 1 <= R,C <= 10^6$。$1 <= x_i <= R , 1 <= y_i <= C$。

所有的传送门位置互不相同。


Solution

题很水,只有建图稍微讲究一点。

分析题目,可以发现该图的边可能达到 $N^2$ 级别。考虑将某行内所有的横天门建成一个环,列内所有的纵寰门建成一个环,然后由环上的点引一次边到不在环上的点。自由门用Hash或者Map即可。当然我懒并没有这么做,直接连边水过了

接下来就是DAG图上点带权的最长路。码量还是挺大的。


Code

#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define hS 1007
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::stack;
using std::vector;

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

struct pt{
    int x,y,t,id;
}h[100005];

struct edge{
    int from,to,next;
}e[10000005],E[1000005];

int N,R,C,node,dfs_clock,scc,ans;
int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};
int first[100005],last[100005],df[100005],dl[100005],dp[100005];
int low[100005],dfn[100005],belong[100005],size[100005],rd[100005];
stack<int>stk;
vector<pt>Ha[hS];
vector<int>He[1000005];
vector<int>Wd[1000005];

void addedge(int u,int v){
    e[++node]=(edge){u,v,0}; if(first[u]==0) first[u]=node;
    else e[last[u]].next=node; last[u]=node; return;
}

void Addedge(int u,int v){
    E[++node]=(edge){u,v,0}; if(df[u]==0) df[u]=node;
    else E[dl[u]].next=node; dl[u]=node; return;
}

int Get_Addr(int x,int y){
    return (long long)((long long)x*998244353+y)%hS;
}

void HInsert(int x,int y,int t,int id){
    Ha[Get_Addr(x,y)].push_back((pt){x,y,t,id});
    return;
}

int HQuery(int x,int y){
    int Addr=Get_Addr(x,y);
    rep(i,0,Ha[Addr].size()-1){
        if(Ha[Addr][i].x==x&&Ha[Addr][i].y==y){
            return Ha[Addr][i].id;
        }
    }return -1;
}

void Init(){ int x,y,t;
    Read(N); Read(R); Read(C);
    rep(i,1,N){
        Read(x); Read(y); Read(t);
        HInsert(x,y,t,i);
        h[i]=(pt){x,y,t,i};
        He[x].push_back(i);
        Wd[y].push_back(i);
    }rep(i,1,N){
        if(h[i].t==1){
            rep(j,0,He[h[i].x].size()-1)
                if(He[h[i].x][j]!=i)
                    addedge(i,He[h[i].x][j]);
        }else if(h[i].t==2){
            rep(j,0,Wd[h[i].y].size()-1)
                if(Wd[h[i].y][j]!=i)
                    addedge(i,Wd[h[i].y][j]);
        }else{
            int nx,ny,res;
            rep(j,0,7){
                nx=h[i].x+dx[j],ny=h[i].y+dy[j];
                if(nx>0&&ny>0&&nx<=R&&ny<=C){
                    res=HQuery(nx,ny);
                    if(res!=-1) addedge(i,res); 
                }
            }
        }
    }
}

void Tarjan(int x){ stk.push(x);
    low[x]=dfn[x]=++dfs_clock;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(!belong[y]){
            low[x]=min(low[x],dfn[y]);
        }
    }if(low[x]==dfn[x]){
        belong[x]=++scc; size[scc]=1;
        while(stk.top()!=x){
            belong[stk.top()]=scc;
            size[scc]++; stk.pop();
        }stk.pop();
    }
}

int Dfs(int x){ int ret=0;
    for(int p=df[x];p;p=E[p].next){
        int y=E[p].to;
        if(dp[y]==0) Dfs(y);
        ret=max(ret,dp[y]);
    } return dp[x]=ret+size[x];
}

void Solve(){
    rep(x,1,N){
        if(!dfn[x]) Tarjan(x);
    }node=0; rep(x,1,N){
        for(int p=first[x];p;p=e[p].next){
            int y=e[p].to;
            if(belong[x]!=belong[y]){ 
                rd[belong[y]]=1;
                Addedge(belong[x],belong[y]);
            }
        }
    }rep(x,1,scc)
        if(rd[x]==0)
            ans=max(ans,Dfs(x));
    printf("%d\n",ans); return;
}

int main(){
    Init();
    Solve();
    return 0;
}