「BZOJ3702」「FJ互测」二叉树
Description(tree.c/.cpp/.pas)
现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。
Input Format(tree.in)
第一行n
下面每行，一个数x
如果x==0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，
如果x!=0，表示这个节点是叶子节点，权值为x。
Output Format(tree.out)
一行，最少逆序对个数。
Sample Input
3
0
0
3
1
2
Sample Output
1
Hint
对于30%的数据：2<=n<=5000。
对于100%的数据：2<=n<=200000。
由于评测机的系统栈实在呵呵……不想写人工栈而爆栈的神犇可以脑补一下你AC的场景
题解
先打了个暴力2333
对于一个非叶子节点，是否交换它的儿子对它之后的统计没有影响
统计每个点左右儿子是否交换，并暴力求出每个节点贡献的逆序对数Sum[i],求∑Sum[i] (30分)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,sz,ans; int v[400005],l[400005],r[400005],size[400005]; void readtree(int x) { v[x]=read(); if(!v[x]) { l[x]=++sz; readtree(l[x]); r[x]=++sz; readtree(r[x]); } size[x]=size[l[x]]+size[r[x]]+1; } void solve(int x) { if(!x)return; solve(l[x]);solve(r[x]); int cnt1=0,cnt2=0; for(int i=x+1;i<=x+size[l[x]];i++) if(v[i]) for(int j=x+size[l[x]]+1;j<=x+size[x]-1;j++) if(v[j]) { if(v[i]>v[j])cnt1++; if(v[j]>v[i])cnt2++; } ans+=min(cnt1,cnt2); } int main() { //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); n=read();++sz; readtree(1); solve(1); printf("%d",ans); return 0; } |
考虑每个点维护一棵线段树，在每个非叶子结点直接合并线段树，然后顺便统计答案，动态开空间
这个合并怎么这么像左偏树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<iostream> #include<cstdio> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,sz,seg; ll ans,cnt1,cnt2; int v[400005],l[400005],r[400005],root[400005]; int sum[4000005],ls[4000005],rs[4000005]; void readtree(int x) { v[x]=read(); if(!v[x]) { l[x]=++sz; readtree(l[x]); r[x]=++sz; readtree(r[x]); } } void pushup(int k) { sum[k]=sum[ls[k]]+sum[rs[k]]; } void build(int &k,int l,int r,int val) { if(!k)k=++seg; if(l==r){sum[k]=1;return;} int mid=(l+r)>>1; if(val<=mid)build(ls[k],l,mid,val); else build(rs[k],mid+1,r,val); pushup(k); } int merge(int x,int y) { if(!x)return y; if(!y)return x; cnt1+=(ll)sum[rs[x]]*sum[ls[y]]; cnt2+=(ll)sum[ls[x]]*sum[rs[y]]; ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); pushup(x); return x; } void solve(int x) { if(!x)return; solve(l[x]);solve(r[x]); if(!v[x]) { cnt1=cnt2=0; root[x]=merge(root[l[x]],root[r[x]]); ans+=min(cnt1,cnt2); } } int main() { //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); n=read();++sz; readtree(1); for(int i=1;i<=sz;i++) if(v[i])build(root[i],1,n,v[i]); solve(1); printf("%lld",ans); return 0; } |
计数器 9856725
OI 课件=>
OI 课件=>
orzhzw