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
",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 ightarrow j, i ightarrow k,j ightarrow k$，那么$i ightarrow 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
",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;
}