A.Graph

因为点可以随便走，所以对于每个联通块，答案为边数/2向下取整。

用类似Tarjan的方式，对于每个联通块建立一棵搜索树，尽量让每一个节点的儿子两两配对，如果做不到就用上头顶的天线。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

const int N=2e5+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,m;

int to[N<<1],head[N],nxt[N<<1],tot=1,vis[N],yet[N<<1];

vector<int> ans;

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

void dfs(int x,int f,int e)

{

    if(vis[x])return ;

    vis[x]=1;

    vector<int> son;

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        dfs(y,x,i);

    }

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f||yet[i])continue;

        son.push_back(i);

        yet[i^1]=1;

    }

    for(int i=0;i<son.size();i++)

    {

        if(i&1)ans.push_back(x);

        ans.push_back(to[son[i]]);

    }

    if(son.size()%2)

    {

        if(e)

        {

            ans.push_back(x);

            ans.push_back(f);

            yet[e]=1;

        }

        else ans.pop_back();

    }

}

int main()

{

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

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

    {

        int x=read(),y=read();

        add(x,y);add(y,x);

    }

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

        if(!vis[i])dfs(i,0,0);

    cout<<ans.size()/3<<endl;

    int now=0;

    for(int i=1;i<=ans.size()/3;i++)

        printf("%d %d %d\n",ans[now++],ans[now++],ans[now++]);

    return 0;

}

B.Permutatin

从原排列入手比较困难，我们求出这个排列的$pos$数组($pos[a[i]]=i$)，那么问题转化为相邻项且绝对值之差$\ge K$的可以交换。最后实际上还是让字典序最小，因为让前面的权值尽量小和权值小的尽量靠前是一样的。

如果在这个序列上有$|pos_i-pos_j|<K,i<j$，那么$pos_i$和$pos_j$的相对位置就已经确定了，相当于是一种限制。不妨把这种限制当作一条有向边，建图跑优先队列拓扑得到结果。

但这样建边时空双炸，因为如果存在$i \rightarrow j, i \rightarrow k,j \rightarrow k$，那么$i \rightarrow k$的边就是无用的。真正需要建的是在两端值域符合条件的下标最小的那两个点。(两段值域分别为$[pos_i-K+1,pos_i-1]$和$[pos_i+1,pos_i+K-1]$)

所以维护一棵权值线段树，每次查询符合条件的最小下标即可。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=5e5+5,M=2e6+2,inf=0x3f3f3f3f;

int n,a[N],pos[N],K,deg[N];

int abss(int x){return x>0?x:-x;}

int to[M],head[N],nxt[M],tot;

priority_queue<int,vector<int>,greater<int> > q;

int ans[N],cnt;

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

    deg[y]++;

}

#define ls(k) (k)<<1

#define rs(k) (k)<<1|1

int minx[N<<2];

void build(int k,int l,int r)

{

    minx[k]=inf;

    if(l==r)return ;

    int mid=l+r>>1;

    build(ls(k),l,mid);

    build(rs(k),mid+1,r);

    minx[k]=min(minx[ls(k)],minx[rs(k)]);

}

void update(int k,int l,int r,int pos,int val)

{

    if(l==r){minx[k]=val;return ;}

    int mid=l+r>>1;

    if(pos<=mid)update(ls(k),l,mid,pos,val);

    else update(rs(k),mid+1,r,pos,val);

    minx[k]=min(minx[ls(k)],minx[rs(k)]);

}

int ask(int k,int l,int r,int L,int R)

{

    if(L>R)return inf;

    if(L<=l&&R>=r)return minx[k];

    int res=inf;

    int mid=l+r>>1;

    if(L<=mid)res=min(res,ask(ls(k),l,mid,L,R));

    if(R>mid)res=min(res,ask(rs(k),mid+1,r,L,R));

    return res;

}

int main()

{

    n=read();K=read();

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

        a[i]=read(),pos[a[i]]=i;

    build(1,1,n);

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

    {

        int res=ask(1,1,n,pos[i]+1,min(pos[i]+K-1,n));

        if(res!=inf)add(pos[i],pos[res]);

        res=ask(1,1,n,max(1,pos[i]-K+1),pos[i]-1);

        if(res!=inf)add(pos[i],pos[res]);

        update(1,1,n,pos[i],i);

    }

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

        if(!deg[i])q.push(i);

    while(!q.empty())

    {

        int x=q.top();q.pop();

        ans[x]=++cnt;

        for(int i=head[x];i;i=nxt[i])

        {

            int y=to[i];

            deg[y]--;

            if(!deg[y])q.push(y);

        }

    }

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

        printf("%d\n",ans[i]);

    return 0;

}

C.Tree

sb题。答案为边权和。

#include<bits/stdc++.h>

using namespace std;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

const int N=1e5+5;

typedef long long ll;

int n;

ll ans=0;

int main()

{

	n=read();

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

	{

		read();read();ans+=read();

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

[CSP-S模拟测试62]题解

A.Graph

B.Permutatin

C.Tree

最新文章

热门文章