第一题
一个裸裸的树形DP。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5; 4 int n,t,tot,s,a[N],h[N]; 5 int cnt,fro[N],to[N],nxt[N]; 6 inline int read() { 7 int x=0; char c=getchar(); 8 while(c<'0'||c>'9') c=getchar(); 9 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 10 return x; 11 } 12 void add(int x,int y) { 13 to[++cnt]=y,nxt[cnt]=fro[x]; fro[x]=cnt; 14 } 15 16 void DP(int u) { 17 if(fro[u]==0) {a[u]=1; return ;} 18 for(int i=fro[u];i;i=nxt[i]) DP(to[i]); 19 tot=0; memset(h,0,sizeof(h)); 20 for(int i=fro[u];i;i=nxt[i]) h[++tot]=a[to[i]]; 21 sort(h+1,h+tot+1); 22 for(int j=1;j<=ceil((double)tot*t/100);j++) a[u]+=h[j]; 23 } 24 25 int main() { 26 // freopen("pa.in","r",stdin); 27 // freopen("pa.out","w",stdout); 28 n=read(),t=read(); 29 for(int i=1;i<=n;i++) {int x=read(); add(x,i);} 30 DP(0); 31 printf("%d",a[0]); 32 }
第二题
理一理思路
1）将人按身高从矮到高排序，按这个顺序处理时无论当前怎么放，都不会对后面更高的产生影响。
2）线段树：统计当前答案序列$1$~$x$的位置有几个未确定的 (即有几个更高的)。
3）字典序最小：在处理时，尽量把当前数往左放。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5; 4 int n,ans[N]; 5 struct node {int h,x;}a[N]; 6 struct tree {int l,r,s;}f[N*3]; 7 inline int read() { 8 int x=0; char c=getchar(); 9 while(c<'0'||c>'9') c=getchar(); 10 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 11 return x; 12 } 13 bool cmp(node x1,node x2) {return x1.h<x2.h;} 14 15 void build(int p,int l,int r) { 16 f[p].l=l,f[p].r=r; 17 if(l==r) {f[p].s=1; return ;} 18 int Mid=(l+r)>>1; 19 build(p*2,l,Mid); 20 build(p*2+1,Mid+1,r); 21 f[p].s=f[p*2].s+f[p*2+1].s; 22 } 23 24 void find(int p,int num,int h) { 25 f[p].s--; 26 if(f[p].l==f[p].r) {ans[f[p].l]=h; return ;} 27 if(num<f[p*2].s) find(p*2,num,h); 28 else find(p*2+1,num-f[p*2].s,h); 29 } 30 31 int main() { 32 // freopen("pb.in","r",stdin); 33 // freopen("pb.out","w",stdout); 34 n=read(); 35 for(int i=1;i<=n;i++) 36 a[i].h=read(),a[i].x=read(); 37 sort(a+1,a+n+1,cmp); 38 for(int i=1;i<=n;i++) 39 if(a[i].x>n-i) return printf("impossible"),0; 40 build(1,1,n); 41 for(int i=1;i<=n;i++) 42 find(1,min(a[i].x,n-i-a[i].x),a[i].h); 43 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 44 }