LuoguP3621 [APIO2007]风铃

https://zybuluo.com/ysner/note/1140124

题面

解析

看着这道题。。。

似乎与[HNOI/AHOI2018]道路有不可言妙的相似之处。

（题面吓人，但是题本身很水)

首先明确每个交汇处只能转一次。

那转还是不转呢？

只要转了能使状态更优，就转嘛。。。

设每个子树有三种状态：\(0\)为只有高玩具，\(1\)为只有低玩具，\(2\)为两者兼备。

于是：

当\(l=2,r=1\)时，转
当\(l=0,r=1\)时，转
当\(l=0,r=2\)时，转(特么一开始漏了）

枚举一下，发现其它情况都不转就可以了，但\(l=2,r=2\)也是一种无解情况。

然后考虑边界：

\(max=min\)，输出\(0\)
\(max>min+1\)，输出\(-1\)

该题于是变成递归题，复杂度\(O(2n)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e5+100;

int n,s[N][2],d[N],f[N],mn=1e9,mx=-1e9;

ll ans;

bool flag=1;

il int gi()

{

  re int x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void dfs(re int u,re int dep)

{

  if(u==-1) return;

  if(s[u][0]==-1||s[u][1]==-1) mn=min(mn,dep+1),mx=max(mx,dep+1);

  dfs(s[u][0],dep+1);dfs(s[u][1],dep+1);

}

il int work(re int u,re int dep)

{

  if(u==-1) return (dep==mn?0:1);

  re int l=work(s[u][0],dep+1),r=work(s[u][1],dep+1);

  if(l==2&&r==2) flag=0;

  if((l==2&&r==1)||(l==0&&r==1)||(l==0&&r==2)) ans++;

  if(l==2||r==2||l!=r) return 2;

  if(l==r) return l;

}

int main()

{

  n=gi();

  fp(i,1,n) s[i][0]=gi(),s[i][1]=gi();

  dfs(1,0);

  if(mx>mn+1) {puts("-1");return 0;}

  if(mx==mn) {puts("0");return 0;}//两极

  work(1,0);

  if(!flag) {puts("-1");return 0;}

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

  return 0;

}

巴特西

LuoguP3621 [APIO2007]风铃

https://zybuluo.com/ysner/note/1140124

题面

解析

最新文章

热门文章