2025_7_10 T3

· · 题解

标准的紫，合格的NOIP T3，考场没想出来也挺正常

首先发现，每次将 [l,r] 区间内的数取反，完全不会影响其内部 a_i 与 a_{i+1} 的值，唯一会改变的只有两组，即 a_{l-1} 与 a_l 和 a_r 与 a_{r+1} （如果 l-1 与 r+1 存在）

据此得出，每回操作，本质上就是选择 2 组 a_i 与 a_{i+1}，如果是减就改为加，反之改为减，因为对于一组数，只有 |a_i-a_{i+1}| 和 |a_i+a_{i+1}| 两种形式互相变化，不妨考虑建图

具体的，我们设 |a_i-a_{i+1}|=x,|a_i+a_{i+1}|=y

连一条边 x 到 y，权值为 1，再连一条边 y 到 x,权值为 0（如果为自环就不连前者)

注意到，我们每次可以将两对边的权值异或 1，且希望最终通过一系列操作，在只考虑权值为 1 的边的条件下，让每一个点的入度小于或等于 1

对于每一个联通块单独计算（以下，对于每个联通块的边数，我们以无向边统计）

1.边数大于点数

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

2.边数等于点数

此时，联通块为基环树，因为点数=边数，所以每个点的入度必须正好为 1

对于非环上的边，它的方向是一定的，只能向外

对于环上边，方向只有顺时针或逆时针，两者都试试，取 \min 就行

3.边数+1=点数

此时，联通块为树，显然，只有一个点的入度为 0，其余为 1，我们现在称这个入度为 0 的点为根

注意到，当根的位置确定时，树上的边也就定向了，我们直接 换根DP就行

综上，我们统计需要修改的边的数量，记为 ans，答案便是 \lceil\frac{ans}{2}\rceil（因为每次可以修改两对边，而且如果 ans 为奇数，可以通过 l=1 或 r=n 的情况来只修改一对边）

#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(n \log n)，瓶颈在于离散化