HGOI20190809 省常中互测2

　　Problem A 时之终结

构造一个含有$n$个节点的无重边无自环的有向图，

使得从$1$出发，每一次经过一条$(u,v) (u < v)$的边到达节点$n$的方案恰好有$y$种。

对于$100\%$的数据，输出的无向图顶点树$n \leq 64 $给出的$y \leq 10^{18}$

Sol : 首先构造$63$个点的完全图，然后向第64个顶点连边，原问题等价于将$y$二进制拆分。

　　这样构造可以获得满分：复杂度$O( {log_2}^2 n)$

# include <bits/stdc++.h>

# define int long long

using namespace std;

bool mp[][];

signed main()

{

    int y; scanf("%lld",&y);

    int cnt=;

    for (int i=;i<=;i++) for (int j=i+;j<=;j++) mp[i][j]=,cnt++;

    for (int i=;i<=;i++) if ((y>>i)&1ll) mp[i+][]=,cnt++;

    printf("64 %lld\n",cnt);

    for (int i=;i<=;i++)

     for (int j=i+;j<=;j++)

      if (mp[i][j]) printf("%lld %lld \n",i,j);

    return ;

}

A.cpp

　　Problem B 博士之时

$n$个节点，每个节点的度最多为$2$的图，共有$2$种不同的颜色，每一条相邻边都是不同色(0/1)的。

求出有多少种可能的重排置换，使得每个一对原本没有通过某种颜色进行连接的节点，出现在了这种颜色的连接中。

对于$100\%$的数据$n\leq 2\times 10^5$ , 图中每个点的度数最多为$2$。

Sol ：图中所有节点的度数小于等于2的可能只有是环或者链，而整个图一定是由一些单独的环和单独的链和孤立的点组成的。

　　考虑链的情况，相同长度的链是可以互相交换的，同时考虑含有奇数条边的链又可以中心对称翻转的，而含偶数条边的链不行。

　　考虑环的情况，相同长度的环是可以相互交换的，同时考虑每个环是可以转动这个环中的节点数次的。

　　所以，我们有下列算法。

　　　对于链，分含奇数条边的链和偶数条边的链的讨论。

奇数条边的链(设长度为$i$的奇数条边有$j$条)： $2^j \times j!$
偶数条边的链(设长度为$i$的奇数条边有$j$条)：$ j!$

　　对于环，无需分奇数偶数讨论。

设长度为$i$的环有$j$个：$j! \times i^j$

设有$k$个孤立点，显然这些孤立点可以任意排列：$k!$

将上述情况相乘就是合法的答案，如果用$n!$减去就是不合法的答案。

　　复杂度是$O(n)$

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int N=2e5+,mo=1e9+;

struct rec{  int pre,to,w; rec() { w=-; } }a[N<<];

bool vis[N];

int du[N],head[N],jc[N],Pow2[N];

int tot,n,m1,m2,cnt;

bool flag;

int col;

map<int,int>circle,chain_even;

map<pair<int,int>,int>chain_odd;

int Pow(int x,int n)

{

    int ans=;

    while (n) {

        if (n&) ans=ans*x%mo;

        x=x*x%mo;

        n>>=;

    }

    return ans%mo;

}

void adde(int u,int v,int w)

{

    a[++tot].pre=head[u];

    a[tot].to=v;

    a[tot].w=w;

    head[u]=tot;

}

void dfs1(int u)

{

    vis[u]=;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to; if (vis[v]) continue;

        if (!flag) col=a[i].w,flag=;

        cnt++; dfs1(v);

    }

}

void dfs2(int u)

{

    vis[u]=;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to; if (vis[v]) continue;

        cnt++; dfs2(v);

    }

}

signed main()

{

    int num; scanf("%lld",&num);

    scanf("%lld%lld%lld",&n,&m1,&m2);

    for (int i=;i<=m1;i++) {

        int u,v; scanf("%lld%lld",&u,&v);

        adde(u,v,); adde(v,u,);

        du[u]++; du[v]++;

    }

    for (int i=;i<=m2;i++) {

        int u,v; scanf("%lld%lld",&u,&v);

        adde(u,v,); adde(v,u,);

        du[u]++; du[v]++;

    }

    jc[]=; for (int i=;i<=;i++) jc[i]=jc[i-]*i%mo;

    Pow2[]=; for (int i=;i<=;i++) Pow2[i]=Pow2[i-]*%mo; 

    for (int i=;i<=n;i++) if (!vis[i] && du[i]==) {

        cnt=; col=-; flag=false; dfs1(i);

        if (cnt&) chain_odd[make_pair(cnt,col)]++;

        else chain_even[cnt]++;

    }

    for (int i=;i<=n;i++) if (!vis[i] && du[i]==) {

        cnt=; dfs2(i);  circle[cnt]++;

    }

    int res=;

    for (int i=;i<=n;i++) if (!vis[i]) res++;

    int ret=jc[res]; map<int,int>::iterator it;

    for (it = circle.begin() ; it != circle.end() ; ++it) {

        int i=it->first,j=it->second;

        ret=ret*jc[j]%mo*Pow(i,j)%mo;

    }

    for (it = chain_even.begin(); it!=chain_even.end() ; ++it) {

        int i=it->first,j=it->second;

        ret=ret*jc[j]%mo;

    }

    map<pair<int,int>,int>::iterator it2;

    for (it2 = chain_odd.begin() ; it2 != chain_odd.end() ; ++it2) {

        pair<int,int> p=it2->first; int i=p.first,j=it2->second;

        ret=ret*jc[j]%mo*Pow2[j]%mo;

    }

    int ans = ((jc[n] - ret) % mo + mo) % mo;

    printf("%lld\n",ans); 

    return ;

}

B.cpp

　　Problem C 曾有两次

给出无向连通图$G$,有$n$个点和$m$条边，

对于每一个点，求删除一条边后这个点到$1$节点的距离可能的最大值

对于$100\%$的数据满足，$n\leq 2\times 10^5 , m \leq 5 \times 10^5$

Sol: 删除的边一定是最短路树上该点和其父节点的连边。

　　于是直接建出最短路树，然后依次考虑每一条非树边$(u,v)$

　　对于链$u -> lca(u,v) $ 不含lca的所有点都可以先最短路树的叶子节点走，经过枚举的这一条边，然后从$v$节点走到根。

　　对于链$v -> lca(u,v) $ 不含lca的所有点同理。

　　这样对于在链上的一个节点$k$，那么对其用$dist(k,u) + w(u,v) + dist(1,v)$更新即可。

注意到$dist(k,u)$ 这个可以表示为$dist(1,u) - dist(1,k)$ 原来的式子可以化为 $dist(1,u) - dist(1,k) + w(u,v) + dist(1,v) $

　　只有$dist(1,k)$是定值，所以我们可以最后统一处理，我们只需要使用$dist(1,u) + w(u,v) + dist(1,v) $来更新每个节点的答案即可。

　　这就变成了在树上维护区间更新一个min值然后单点查询，直接使用树链剖分维护即可。

　　复杂度是$O(m { log_2 }^2n )$

# pragma GCC optimize()

# include <bits/stdc++.h>

# define int long long

# define inf (1e14)

using namespace std;

const int N=2e5+;

const int M=5e5+;

struct rec{ int pre,to,w;}a[M<<];

struct edge{ int u,v,w;}rec[M<<];

int n,m,tot=;

int head[N],d[N],e[N],f[N],dep[N],size[N];

int dfn[N],top[N],g[N][];

bool b[M<<];

vector<int>E[N];

pair<int,int>pre[N];

inline int read()

{

    int X=,w=; char c=;

    while(c<''||c>'') {w|=c=='-';c=getchar();}

    while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    return w?-X:X;

}

void write(int x)

{

    if (x>) write(x/);

    putchar(''+x%);

}

void adde(int u,int v,int w)

{

    a[++tot].pre=head[u];

    a[tot].to=v;

    a[tot].w=w;

    head[u]=tot;

}

struct node {

    int id,len;

};

struct cmp {

    bool operator () (node x,node y) {

        return x.len > y.len ;

    }

};

priority_queue<node,vector<node>,cmp>q;

bool vis[N];

void dijkstra(int s)

{

    memset(vis,false,sizeof(vis));

    memset(d,0x3f,sizeof(d));

    d[s]=; q.push((node){s,});

    while (!q.empty()) {

        node u=q.top();q.pop();

        if (vis[u.id]) continue;

        vis[u.id]=;

        for (int i=head[u.id];i;i=a[i].pre) {

            int v=a[i].to,w=a[i].w;

            if (d[v]-w>d[u.id]) {

                e[v]=i; pre[v]=make_pair(u.id,w); d[v]=d[u.id]+w;

                q.push((node){v,d[v]});

            }

        }

    }

}

void dfs1(int u,int fa)

{

    f[u]=fa; dep[u]=dep[fa]+; size[u]=;

    for (int i=;i<E[u].size();i++) {

        int v=E[u][i]; if (v==fa) continue;

        dfs1(v,u); size[u]+=size[v];

    }

}

void dfs2(int u,int fa,int tp)

{

    dfn[u]=++dfn[]; top[u]=tp;

    int son=-;

    for (int i=;i<E[u].size();i++) {

        int v=E[u][i]; if (v==fa) continue;

        if (son==-||size[v]>size[son]) son=v;

    }

    if (son!=-) dfs2(son,u,tp);

    for (int i=;i<E[u].size();i++) {

        int v=E[u][i]; if (v==fa) continue;

        if (v!=son) dfs2(v,u,v);

    }

}

# define ls (x<<)

# define rs (x<<|)

# define lson ls,l,mid

# define rson rs,mid+,r

# define mid (l+r>>)

struct Segmengt_Tree{

    int tag,ret;

    Segmengt_Tree() { tag=-; ret=inf;}

}tr[N<<];

void down(int x)

{

    if (tr[x].tag==-) return;

    tr[ls].ret=min(tr[ls].ret,tr[x].tag);

    tr[rs].ret=min(tr[rs].ret,tr[x].tag);

    tr[ls].tag=(tr[ls].tag==-)?tr[x].tag:min(tr[x].tag,tr[ls].tag);

    tr[rs].tag=(tr[rs].tag==-)?tr[x].tag:min(tr[x].tag,tr[rs].tag);

    tr[x].tag=-;

}

void update(int x,int l,int r,int opl,int opr,int d)

{

    if (opl<=l &&r<=opr) {

        if (tr[x].tag==-) tr[x].tag=d;

        else tr[x].tag=min(tr[x].tag,d);

        tr[x].ret=min(tr[x].ret,d);

        return;

    }

    down(x);

    if (opl<=mid) update(lson,opl,opr,d);

    if (opr>mid) update(rson,opl,opr,d);

    tr[x].ret=min(tr[ls].ret,tr[rs].ret);

}

int query(int x,int l,int r,int opl,int opr)

{

    if (opl<=l&&r<=opr) return tr[x].ret;

    down(x);

    int ret=inf;

    if (opl<=mid) ret=min(ret,query(lson,opl,opr));

    if (opr>mid) ret=min(ret,query(rson,opl,opr));

    return ret;

}

int lca(int u,int v)

{

    if (dep[u]<dep[v]) swap(u,v);

    for (int i=;i>=;i--)

     if (dep[g[u][i]]>=dep[v]) u=g[u][i];

    if (u==v) return u;

    for (int i=;i>=;i--)

     if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i];

    return g[u][];

}

void update(int u,int v,int d)

{

    int f1=top[u],f2=top[v];

    while (f1!=f2) {

        if (dep[f1]<dep[f2]) swap(f1,f2);

        update(,,n,dfn[f1],dfn[u],d);

        u=f[f1]; f1=top[u];

    }

    if (dep[u]<dep[v]) swap(u,v);

    update(,,n,dfn[v]+,dfn[u],d);

}

int query(int x){

    return query(,,n,dfn[x],dfn[x]);

}

main()

{

    int num=read();

    n=read();m=read();

    for (int i=;i<=m;i++) {

        int u=read(),v=read(),w=read();

        adde(u,v,w); rec[tot]=(edge){u,v,w}; adde(v,u,w);

    }

    dijkstra();

    for (int i=;i<=n;i++) {

        b[e[i]]=b[e[i]^]=;

        E[i].push_back(pre[i].first);

        E[pre[i].first].push_back(i);

    }

    dfs1(,); dfs2(,,);

    for (int i=;i<=n;i++) g[i][]=f[i];

    for (int i=;i<=;i++) for (int j=;j<=n;j++) g[j][i]=g[g[j][i-]][i-];

    for (int i=;i<=tot;i+=)

     if (!b[i]) {

        int u=rec[i].u,v=rec[i].v,w=rec[i].w,l=lca(u,v);

        update(u,l,d[v]+w+d[u]); update(v,l,d[u]+w+d[v]);

     }

    putchar(''); putchar(' ');

    for (int i=;i<=n;i++) {

        int t=query(i);

        if (t>=inf) putchar('-'),putchar('');

        else write(t-d[i]);

        putchar(' ');

    }

    putchar('\n');

    return ;

}

C.cpp

巴特西

HGOI20190809 省常中互测2

最新文章

热门文章