分类目录归档:算法竞赛

[cf1051F]The shortest statement

Link

$n$个点,$m(m-n< 20)$条边的连通图,多组询问两点的最短路。

Solution

求出图的任意一个生成树,把不在生成树上的边所连接的点都做一遍最短路。
如果两点最短路在生成树上,那么求出树上最短路就得到答案。
否则,考虑floyd算法,选取点$u$,用$d[x][u]+d[u][y]$更新答案。选取的点$u$只需选取那些不在生成树上的边连接的点,因为如果生成树上的某点到点$x$在树上的距离不是最短路,那么最短路一定经过某个不在生成树上的边连接的点,因此只用这些点松弛就行了。

[zoj4053][icpc 2018 Qingdao Online]Couleur

Link

Solution

假设将区间$[l,r]$中间的$p$ ban掉,并且知道$[l,r]$的逆序堆数,容易计算出$[l,p-1]$和$[p+1,r]$之间,以及他们分别和$p$产生的逆序数。
用启发式的思想,每次将这两个区间中小的那个遍历,在另一个区间的主席树中查询,最终复杂度为$O(n\log^2n)$

Tips

赛场上没有过这道题,是因为偷懒直接把问题一般化,得到$O(n\sqrt {n\log n})$的做法,最终自闭。

Code

const int XN=1e5+11;

struct SegTree {
    struct Node {
        Node *son[2];
        long long cnt;

        Node():cnt(0) {
            son[0]=son[1]=null;
        }

        Node(void*):cnt(0) {
            son[0]=son[1]=this;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc(XN*20*sizeof(Node)),*mem=pool++;
            return flag?mem++:mem=pool;
        }

        void Up() {
            cnt=son[0]->cnt+son[1]->cnt;
        }

    }*root[XN];
    int n,L,R;
    static Node *null;

    SegTree(int L,int R):n(0),L(L),R(R) {
        root[0]=null;
    }

    void Append(int v) {
        ++n;
        Modify(root[n]=root[n-1],L,R,v);
    }

    long long Query(int lbd,int rbd,int l,int r) {
        return lbd<=rbd && l<=r?Query(root[lbd-1],root[rbd],L,R,l,r):0;
    }

    static void Modify(Node *&pos,int L,int R,int goal) {
        pos=new Node(*pos);
        if(L==R)
            pos->cnt++;
        else {
            int M=(L+R)/2;
            if(goal<=M)
                Modify(pos->son[0],L,M,goal);
            else
                Modify(pos->son[1],M+1,R,goal);
            pos->Up();
        }
    }

    static long long Query(Node *pl,Node *pr,int L,int R,int l,int r) {
        if(L==l && R==r)
            return pr->cnt-pl->cnt;
        else {
            int M=(L+R)/2;
            if(r<=M)
                return Query(pl->son[0],pr->son[0],L,M,l,r);
            else if(M+1<=l)
                return Query(pl->son[1],pr->son[1],M+1,R,l,r);
            else
                return Query(pl->son[0],pr->son[0],L,M,l,M)
                      +Query(pl->son[1],pr->son[1],M+1,R,M+1,r);
        }
    }
}seg(-1,-1);

SegTree::Node *SegTree::null=new SegTree::Node((void*)0);

int a[XN];

void Work() {
    SegTree::Node::operator new(0);
    int n;fin>>n;
    new(&seg) SegTree(1,n);
    long long last=0;
    std::set<int> unav;
    std::multiset<long long> S;
    for(int i=1;i<=n;++i) {
        fin>>a[i];
        last+=seg.Query(1,i-1,a[i]+1,n);
        seg.Append(a[i]);
    }
    unav.insert(0);
    unav.insert(n+1);
    static std::multiset<long long>::iterator its[XN];
    its[1]=S.insert(last);
    for(int lop=1;lop<=n;++lop) {
        fout<<last<<(lop==n?'\n':' ');
        long long p;fin>>p;p^=last;
        std::set<int>::iterator pt=unav.upper_bound(p);
        int r=(*pt)-1,l=(*--pt)+1;
        unav.insert(p);
        long long tot=*its[l];
        S.erase(its[l]);
        tot-=seg.Query(l,p-1,a[p]+1,n)+seg.Query(p+1,r,1,a[p]-1);
        if(p-l>r-p) {
            long long ic=0,lc=0;
            for(int i=p+1;i<=r;++i) {
                lc+=seg.Query(l,p-1,a[i]+1,n);
                ic+=seg.Query(p+1,i-1,a[i]+1,n);
            }
            its[l]=S.insert(tot-lc-ic);
            its[p+1]=S.insert(ic);
        } else {
            long long ic=0,rc=0;
            for(int i=l;i<=p-1;++i) {
                rc+=seg.Query(p+1,r,1,a[i]-1);
                ic+=seg.Query(l,i-1,a[i]+1,n);
            }
            its[l]=S.insert(ic);
            its[p+1]=S.insert(tot-rc-ic);
        }
        last=*S.rbegin();
    }
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[zoj4056][ICPC 2018 Qingdao Online]Press the Button

Link

Solution

问题最后是求一个长度为$t$的数轴上有多少对相邻的关键点距离$\ge v$,关键点是所有$a$和$c$的倍数的点。
假设$a < c$
如果$a < v$则不存在
否则
考虑$c$的倍数与它后面相邻的$a$的倍数的距离
根据根据鸽巢原理,至多$c$步,这个距离就会开始循环
然后把$t$分成三部分:
不在循环+循环部分+一段没循环完的部分
细节巨多写到脑壳疼
~正解是模拟到${\rm lcm}(a,b)$,直接判断,然后循环~

Code

const int XN=1e6+11;
void Work() {
    long long v,t,a,b,c,d;
    fin>>a>>b>>c>>d>>v>>t;
    long long Ans=(long long)((t/a)+1)*b+(long long)((t/c)+1)*d-1;
    if(a>v && c>v) {
        if(a>c)
            std::swap(a,c);
        static int us[XN],ut;
        static long long crec[XN],prec[XN];
        ++ut;long long cnt=0,pc=0,py=0;
        for(;;pc+=c) {
            long long x=(pc/a)*a,y=x+a; 
            cnt+=((pc-x)>v)+((y-pc)>v)+(x-py)/a;
            py=y;
            if(us[y-pc]==ut)
                break;
            us[y-pc]=ut;
            crec[y-pc]=cnt;
            prec[y-pc]=py;
        }
        if(t>prec[py-pc]) {
            long long circnt=cnt-crec[py-pc],cirlen=py-prec[py-pc];
            Ans-=circnt*((t-prec[py-pc])/cirlen)+crec[py-pc];
            py+=((t-prec[py-pc])/cirlen-1)*cirlen;
            pc=(py/c+1)*c;
        } else {
            py=pc=0;
        }
        if(pc<=t)
            for(;;pc+=c) {
                long long x=(pc/a)*a,y=x+a;
                Ans-=((pc-x)>v)+(x-py)/a;
                if(y<=t) {
                    Ans-=((y-pc)>v);
                }
                py=y;
                if(pc+c>t)
                    break;
            }
        if(py<t)
            Ans-=(t-py)/a;
    }
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[hdu6393][多校第七场]Traffic Network in Numazu

Link

求一个环套树上两点的最短路,支持边权修改。

Solution

找出环来,拆开,用树状数组维护环拆成的链的前缀和,求最短距离的话两种情况枚举一下。
对于环上的森林,就每棵树都用树状数组维护DFS序,再加上任意一种LCA方法,就可以求出了。

Tips

  1. 倍增LCA需要判一下当前第$2^k$祖先是否存在!
  2. 注意应该用的数据类型,又爆int了,造了链的数据才拍出来。

Code

const int XN=1e5+11,XLOGN=17;

int lg2[XN];

long long Sum(std::vector<long long> const& bit,int pos) {
    long long res=0;
    for(;pos;pos-=pos & -pos)
        res+=bit[pos];
    return res;
}

void Add(std::vector<long long> &bit,int pos,int v) {
    for(int n=bit.size();pos<n;pos+=pos & -pos)
        bit[pos]+=v;
}

struct Edge {
    int to,v;Edge *pre;

    Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
}*G[XN];

void Adde(int x,int y,int v) {
    G[x]=new Edge(y,v,G[x]);
    G[y]=new Edge(x,v,G[y]);
}

int circle[XN],circ;
bool ud[XN];
bool FindCircle(int pos,int pred) {
    static int stack[XN],top;
    if(ud[pos]) {
        circ=0;
        do {
            circle[++circ]=stack[top--];
        }while(stack[top+1]!=pos);
        top=0;
        return 1;
    } else {
        ud[stack[++top]=pos]=1;
        for(Edge *e=G[pos];e;e=e->pre) {
            int u=e->to;
            if(u!=pred && FindCircle(u,pos))
                return 1;
        }
        top--;
        return 0;
    }
}

int dc,lbd[XN],rbd[XN],par[XN][XLOGN],dep[XN],belong[XN];
std::vector<long long> bit[XN];
void DFS(int pos,int fa) {
    lbd[pos]=rbd[pos]=++dc;//rbd 0
    par[pos][0]=fa;
    for(int lg=1;lg<=lg2[dep[pos]];++lg)
        par[pos][lg]=par[par[pos][lg-1]][lg-1];
    for(Edge *e=G[pos];e;e=e->pre) {
        int u=e->to;
        if(u!=fa && !belong[u]) {
            belong[u]=belong[pos];
            dep[u]=dep[pos]+1;
            DFS(u,pos);
            rbd[pos]=rbd[u];
        }
    }
}

int LCA(int u,int v) {
    if(dep[u]<dep[v])
        std::swap(u,v);
    for(int lg=lg2[dep[u]-dep[v]];~lg;--lg)
        if((dep[u]-dep[v])>>lg&1)
            u=par[u][lg];
    if(u!=v) {
        for(int lg=lg2[dep[u]];~lg;--lg)
            if((1<<lg)<=dep[u] && par[u][lg]!=par[v][lg]) {//多出来的需要清0!! 可能走出(1<<(lg+1))-1步!
                u=par[u][lg];
                v=par[v][lg];
            }
        u=par[u][0];
    }
    return u;
}
void AddVal(int x,int y,int v) {
    if(circle[belong[x]]!=x || circle[belong[y]]!=y) {
        if(dep[x]>dep[y])
            std::swap(x,y);
        Add(bit[belong[x]],lbd[y],v);
        Add(bit[belong[x]],rbd[y]+1,-v);
    }  else {
        if(belong[x]>belong[y])
            std::swap(x,y);
        if(belong[x]+1==belong[y])
            Add(bit[0],belong[y],v);
        else
            Add(bit[0],belong[x],v);//belong[x]==1
    }
}

long long Query(int p1,int p2) {
    long long len1=Sum(bit[belong[p1]],lbd[p1]),len2=Sum(bit[belong[p2]],lbd[p2]);
    if(belong[p1]==belong[p2]) {
        long long lca=LCA(p1,p2),len3=Sum(bit[belong[lca]],lbd[lca]);
        return len1+len2-2*len3;
    } else {
        p1=belong[p1],p2=belong[p2];
        if(p1>p2) std::swap(p1,p2);
        long long len3=Sum(bit[0],p2)-Sum(bit[0],p1),len4=Sum(bit[0],circ)-len3;
        return len1+len2+std::min(len3,len4);
    }
}

void Work() {
    static struct Edges { int x,y,v; }edges[XN];
    int n,m;fin>>n>>m;
    for(int i=1;i<=n;++i) {
        G[i]=0;
        ud[i]=0;
        belong[i]=0;
    }
    for(int i=1;i<=n;++i) {
        fin>>edges[i].x>>edges[i].y>>edges[i].v;
        Adde(edges[i].x,edges[i].y,edges[i].v);
    }
    FindCircle(1,0);
    bit[0].resize(circ+1);
    std::fill(bit[0].begin(),bit[0].end(),0);
    for(int i=1;i<=circ;++i)
        belong[circle[i]]=i;
    for(int i=1;i<=circ;++i) {
        int pos=circle[i];
        dc=0;dep[pos]=0;
        DFS(pos,0);
        bit[i].resize(dc+1);
        std::fill(bit[i].begin(),bit[i].end(),0);
    }
    for(int i=1;i<=n;++i) {
        int x=edges[i].x,y=edges[i].y,v=edges[i].v;
        AddVal(x,y,v);
    }
    for(int i=1;i<=m;++i) {
        int op,x,y;fin>>op>>x>>y;
        if(op==1) {
            fout<<Query(x,y)<<'\n';
        } else {
            AddVal(edges[x].x,edges[x].y,-edges[x].v);
            AddVal(edges[x].x,edges[x].y,edges[x].v=y);
        }
    }
}
int main() {
    lg2[0]=-1;
    for(int i=1;i<XN;++i)
        lg2[i]=lg2[i>>1]+1;
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[hdu6397][多校第八场]Character Encoding

Link

求$[x^k] (x^0+x^1+x^2+…+x^{n-1})^m$

Solution

生成函数

$\begin{aligned}
&(x^0+x^1+x^2+…+x^{n-1})^m\
=&(x^n-1)^m(x-1)^{-m}\
\end{aligned}$
设$k=\lambda_1n+\lambda_2$

[x^{\lambda_1n}] (x^n-1)^m=\binom m{\lambda_1}(-1)^{\lambda_1}\\
[x^{\lambda_2}] (x-1)^{-m}=\binom {-m}{\lambda_2}(-1)^{\lambda_2}\\
\binom {-m}{\lambda_2}=\frac{(-m)(-m-1)…(-m-\lambda_2+1)}{\lambda_2!}\\
\begin{aligned}&(-m)(-m-1)…(-m-\lambda_2+1)\\
=&(-1)^{\lambda_2}m(m+1)…(m+\lambda_2-1)\end{aligned}

因此

\binom {-m}{\lambda_2}=(-1)^{\lambda_2}\binom {m+\lambda_2-1}{\lambda_2}

然后就能算了。

void Work() {
    int n,m,k;fin>>n>>m>>k;
    int Ans=0;
    for(int lam1=0;lam1*n<=k;++lam1) {
        int lam2=k-lam1*n;
        Ans=Add(Ans,Mul(Mul(C(m,lam1),lam1&1?P-1:1),C(m+lam2-1,lam2)));
    }
    fout<<Ans<<'\n';

容斥原理

如果去掉变量$< n$的限制,那方案数就是

\binom {k+m-1}{m-1}

考虑容斥。
假设至少有$p$个变量$\ge n$,那么方案数为

\binom mp\binom {k-pn+m-1}{m-1}

意思是让超出的都减去$n$。
然后容斥就好了。