[关闭]
@ysner 2018-05-08T21:56:15.000000Z 字数 1351 阅读 1973

LuoguP3621 [APIO2007]风铃

搜索


题面

题面复杂,戳我

解析

看着这道题。。。
似乎与[HNOI/AHOI2018]道路有不可言妙的相似之处。
题面吓人,但是题本身很水)
首先明确每个交汇处只能转一次。
那转还是不转呢?
只要转了能使状态更优,就转嘛。。。
设每个子树有三种状态:为只有高玩具,为只有低玩具,为两者兼备。
于是:

枚举一下,发现其它情况都不转就可以了,但也是一种无解情况。
然后考虑边界:

该题于是变成递归题,复杂度

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1e5+100;
  14. int n,s[N][2],d[N],f[N],mn=1e9,mx=-1e9;
  15. ll ans;
  16. bool flag=1;
  17. il int gi()
  18. {
  19. re int x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void dfs(re int u,re int dep)
  27. {
  28. if(u==-1) return;
  29. if(s[u][0]==-1||s[u][1]==-1) mn=min(mn,dep+1),mx=max(mx,dep+1);
  30. dfs(s[u][0],dep+1);dfs(s[u][1],dep+1);
  31. }
  32. il int work(re int u,re int dep)
  33. {
  34. if(u==-1) return (dep==mn?0:1);
  35. re int l=work(s[u][0],dep+1),r=work(s[u][1],dep+1);
  36. if(l==2&&r==2) flag=0;
  37. if((l==2&&r==1)||(l==0&&r==1)||(l==0&&r==2)) ans++;
  38. if(l==2||r==2||l!=r) return 2;
  39. if(l==r) return l;
  40. }
  41. int main()
  42. {
  43. n=gi();
  44. fp(i,1,n) s[i][0]=gi(),s[i][1]=gi();
  45. dfs(1,0);
  46. if(mx>mn+1) {puts("-1");return 0;}
  47. if(mx==mn) {puts("0");return 0;}//两极
  48. work(1,0);
  49. if(!flag) {puts("-1");return 0;}
  50. printf("%lld\n",ans);
  51. return 0;
  52. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注