专栏文章

2025_7_10 T3

EEvan_Leo_Azir
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miox06pi
此快照首次捕获于
2025/12/03 02:31
3 个月前
此快照最后确认于
2025/12/03 02:31
3 个月前
查看原文
标准的紫，合格的NOIP T3，考场没想出来也挺正常
首先发现，每次将 [l,r][l,r] 区间内的数取反，完全不会影响其内部 aia_i 与 ai+1a_{i+1} 的值，唯一会改变的只有两组，即 al−1a_{l-1} 与 ala_l 和 ara_r 与 ar+1a_{r+1} （如果 l−1l-1 与 r+1r+1 存在）
据此得出，每回操作，本质上就是选择 22 组 aia_i 与 ai+1a_{i+1}，如果是减就改为加，反之改为减，因为对于一组数，只有 ∣ai−ai+1∣|a_i-a_{i+1}| 和 ∣ai+ai+1∣|a_i+a_{i+1}| 两种形式互相变化，不妨考虑建图
具体的，我们设 ∣ai−ai+1∣=x|a_i-a_{i+1}|=x,∣ai+ai+1∣=y|a_i+a_{i+1}|=y
连一条边 xx 到 yy，权值为 11，再连一条边 yy 到 xx,权值为 00（如果为自环就不连前者)
注意到，我们每次可以将两对边的权值异或 11，且希望最终通过一系列操作，在只考虑权值为 11 的边的条件下，让每一个点的入度小于或等于 11
对于每一个联通块单独计算（以下，对于每个联通块的边数，我们以无向边统计）

1.边数大于点数

根据抽屉原理，肯定有一个点的入度大于 11 ，故此时无解，输出 −1-1 即可

2.边数等于点数

此时，联通块为基环树，因为点数=边数，所以每个点的入度必须正好为 11
对于非环上的边，它的方向是一定的，只能向外
对于环上边，方向只有顺时针或逆时针，两者都试试，取 min⁡\min 就行

3.边数+1=点数

此时，联通块为树，显然，只有一个点的入度为 00，其余为 11，我们现在称这个入度为 00 的点为根
注意到，当根的位置确定时，树上的边也就定向了，我们直接 换根DP就行
综上，我们统计需要修改的边的数量，记为 ansans，答案便是 ⌈ans2⌉\lceil\frac{ans}{2}\rceil（因为每次可以修改两对边，而且如果 ansans 为奇数，可以通过 l=1l=1 或 r=nr=n 的情况来只修改一对边）
CPP
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=1e5+10,inf=0x3f3f3f3f;
int n,len,cnte=0,cntn,ans,lc,res;
int a[maxn],b[maxn<<1],head[maxn<<1],fa[maxn<<1],numn[maxn<<1],nume[maxn<<1],dfn[maxn<<1],cro[maxn<<1],g[maxn<<1];
bool in[maxn<<1];
pii cir[maxn<<1],lst[maxn<<1];
struct EDGE{
	int v,nxt,w,id;
}e[maxn<<1];
void adde(int u,int v,int w,int id)
{
	e[cnte]={v,head[u],w,id};
	head[u]=cnte++;
}
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
int read()
{
	int ret=0,w=1;char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
	return ret*w;
}
void dfs1(int u)
{
	dfn[u]=++cntn;
	for(int i=head[u],to;i!=-1;i=e[i].nxt)
	{
		to=e[i].v;
		if(cro[u]==e[i].id)  continue;
		if(!dfn[to])
		{
			cro[to]=e[i].id;
			lst[to]={u,e[i].w};
			dfs1(to);
		}else if(dfn[to]<=dfn[u])
		{
			for(int j=u;j!=to;j=lst[j].first) cir[++lc]={j,lst[j].second};
			cir[++lc]={to,e[i].w};
		}
	}
}
void dfs2(int u,int fat)
{
	for(int i=head[u],to;i!=-1;i=e[i].nxt) if(!in[to=e[i].v]&&to!=fat)
	{
		ans+=e[i].w;
		dfs2(to,u);
	}
}
void cal1(int x)
{
	cntn=lc=0;
	dfs1(x);
	int res1=0,res2=0;
	for(int i=1;i<=lc;i++) res1+=cir[i].second==1,res2+=cir[i].second==0,in[cir[i].first]=1;
	ans+=min(res1,res2);
	for(int i=1;i<=lc;i++) dfs2(cir[i].first,0);
}
void dfs3(int u,int fat)
{
	for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fat)
	{
		dfs3(to,u);
		g[u]+=g[to]+e[i].w;
	}
}
void dfs4(int u,int fat,int wgc)
{
	res=min(res,wgc);
	for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fat) dfs4(to,u,wgc-e[i].w+(!e[i].w));
}
void cal2(int x)
{
	dfs3(x,0);
	res=inf;
	dfs4(x,0,g[x]);
	ans+=res;
}
void inpu()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
}
void build()
{
	int cnt=0;
	for(int i=1;i<n;i++) b[++cnt]=abs(a[i]-a[i+1]),b[++cnt]=abs(a[i]+a[i+1]);
	sort(b+1,b+cnt+1);
	len=unique(b+1,b+cnt+1)-b-1;
	for(int i=1;i<=len;i++) numn[i]=1,fa[i]=i;
	memset(head,-1,sizeof(head));
	for(int i=1,x,y,fa1,fa2;i<n;i++)
	{
		x=lower_bound(b+1,b+len+1,abs(a[i]-a[i+1]))-b,y=lower_bound(b+1,b+len+1,abs(a[i]+a[i+1]))-b;
		adde(y,x,0,i);
		if(x!=y) adde(x,y,1,i);
		fa1=find(x),fa2=find(y);
		if(fa1!=fa2) fa[fa2]=fa1,numn[fa1]+=numn[fa2],nume[fa1]+=nume[fa2];
		nume[fa1]++;
	}
}
bool check()
{
	for(int i=1;i<=len;i++) if(find(i)==i) if(numn[i]<nume[i]) return true;
	return false;
}
void deal()
{
	for(int i=1;i<=len;i++) if(find(i)==i)
	{
		if(numn[i]==nume[i]) cal1(i);
		else cal2(i);
	}
}
void solve()
{
	inpu();
	build();
	if(check()) ans=-1;
	else deal();
	printf("%d",ans==-1?ans:(ans+1)/2);
}
int main()
{
	int t=1;
	while(t--) solve();
	return 0;
}
时间复杂度 O(nlog⁡n)O(n \log n)，瓶颈在于离散化

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...