hdu5820

官方题解：http://www.cnblogs.com/duoxiao/p/5777700.html

1 #include
      
        2  3 using namespace std; 4 struct node{
    int l,r,s;} tr[500010*40]; 5 vector
       
         g[50010]; 6 int pre[50010],h[50010],n,t; 7 int build(int l,int r) 8 { 9     ++t; tr[t].s=0;10     if (l==r) return t;11     int m=(l+r)>>1,q=t;12     tr[t].l=build(l,m);13     tr[t].r=build(m+1,r);14     return q;15 }16 17 int ask(int i,int l,int r,int x,int y)18 {19     if (x>y) return 0;20     if (x<=l&&y>=r) return tr[i].s;21     else {22         int m=(l+r)>>1,s=0;23         if (x<=m) s+=ask(tr[i].l,l,m,x,y);24         if (y>m) s+=ask(tr[i].r,m+1,r,x,y);25         return s;26     }27 }28 29 int add(int i,int l,int r,int x)30 {31     ++t;32     if (l==r)33     {34         tr[t].s=tr[i].s+1;35         return t;36     }37     int m=(l+r)>>1,q=t;38     if (x<=m)39     {40         tr[q].r=tr[i].r;41         tr[q].l=add(tr[i].l,l,m,x);42     }43     else {44         tr[q].l=tr[i].l;45         tr[q].r=add(tr[i].r,m+1,r,x);46     }47     tr[q].s=tr[tr[q].l].s+tr[tr[q].r].s;48     return q;49 }50 51 52 bool check()53 {54     memset(pre,0,sizeof(pre));55     for (int i=1; i<=50000; i++)56     {57         h[i]=h[i-1];58         for (int j=0; j
       
      

 

hdu5788

官方题解：http://www.cnblogs.com/duoxiao/p/5777661.html

其实有个简单的方法求子树的[t/2]名次：直接在dfs序上建立可持久化线段树查询即可

1 #include
      
         2   3 using namespace std;  4 typedef long long ll;  5 struct way{
    int po,next;} e[100010];  6 struct node{
    int s,l,r;} tr[100010*40];  7 int p[100010],l[100010],h[100010],w[100010],cur[100010],a[100010],r[100010],len,n,tot,t;  8 ll c[100010],ans;  9 void add(int x,int y) 10 { 11     e[++len].po=y; 12     e[len].next=p[x]; 13     p[x]=len; 14 } 15  16 int build(int l,int r) 17 { 18     ++t; tr[t].s=0; 19     if (l==r) return t; 20     int m=(l+r)>>1,q=t; 21     tr[t].l=build(l,m); 22     tr[t].r=build(m+1,r); 23     return q; 24 } 25  26 int mid(int a,int b,int l,int r,int k) 27 { 28     if (l==r) return l; 29     else { 30         int m=(l+r)>>1,s=tr[tr[b].l].s-tr[tr[a].l].s; 31         if (k<=s) return mid(tr[a].l,tr[b].l,l,m,k); 32         else return mid(tr[a].r,tr[b].r,m+1,r,k-s); 33     } 34 } 35  36 int add(int i,int l,int r,int x) 37 { 38     ++t; 39     if (l==r) 40     { 41         tr[t].s=tr[i].s+1; 42         return t; 43     } 44     int m=(l+r)>>1,q=t; 45     if (x<=m) 46     { 47         tr[q].r=tr[i].r; 48         tr[q].l=add(tr[i].l,l,m,x); 49     } 50     else { 51         tr[q].l=tr[i].l; 52         tr[q].r=add(tr[i].r,m+1,r,x); 53     } 54     tr[q].s=tr[tr[q].l].s+tr[tr[q].r].s; 55     return q; 56 } 57  58 void dfs1(int x) 59 { 60     l[x]=++tot; h[tot]=add(h[tot-1],1,100000,a[x]); 61     for (int i=p[x]; i; i=e[i].next) 62     { 63         int y=e[i].po; 64         dfs1(y); 65     } 66     w[x]=mid(h[l[x]-1],h[tot],1,100000,(tot-l[x]+2)/2); 67     if (l[x]==tot) cur[x]=0; else cur[x]=mid(h[l[x]-1],h[tot],1,100000,(tot-l[x]+2)/2+1)-w[x]; 68 } 69  70 void work(int x,int w) 71 { 72     for (int i=x; i; i-=i&(-i)) c[i]+=w; 73 } 74  75 ll ask(int x) 76 { 77     ll s=0; 78     for (int i=x; i<=100000; i+=i&(-i)) s+=c[i]; 79     return s; 80 } 81  82 void dfs2(int x) 83 { 84     ll wh=(p[x]==0)?100000-a[x]:cur[x]-w[x]; 85     ans=max(ans,ask(a[x])+wh); 86     if (cur[x]) work(w[x],cur[x]); 87     for (int i=p[x]; i; i=e[i].next) 88     { 89         int y=e[i].po; 90         dfs2(y); 91     } 92     if (cur[x]) work(w[x],-cur[x]); 93 } 94  95 int main() 96 { 97     t=0; h[0]=build(1,100000); 98     int tmp=t; 99     while (scanf("%d",&n)!=EOF)100     {101         t=tmp;102         len=0; memset(p,0,sizeof(p));103         for (int i=1; i<=n; i++) scanf("%d",&a[i]);104         for (int i=2; i<=n; i++)105         {106             int fa;107             scanf("%d",&fa);108             add(fa,i);109         }110         tot=0; h[1]=h[0]; dfs1(1);111         ll s=0;112         for (int i=1; i<=n; i++) s+=w[i];113      //   for (int i=1; i<=n; i++) cout <<"*"<
       
        <<" "<
        
         <
        
       
      

 

hdu3605

把n按照可选择方案二进制状态压缩，建图最大流即可

1 #include
      
         2   3 using namespace std;  4 const int inf=1e9+7;  5 struct way{
    int po,flow,next;} e[2400010];  6 int t,n,p[2010],pre[2010],numh[2010],cur[2010],h[2010],d[2010],b[2010],m,len;  7   8 void add(int x,int y,int f)  9 { 10      e[++len].po=y; 11      e[len].flow=f; 12      e[len].next=p[x]; 13      p[x]=len; 14 } 15 void build(int x, int y, int f) 16 { 17      add(x,y,f); 18      add(y,x,0); 19 } 20 int sap() 21 { 22     memset(numh,0,sizeof(numh)); 23     memset(h,0,sizeof(h)); 24     numh[0]=t+1; 25     for (int i=0; i<=t; i++) cur[i]=p[i]; 26     int j,u=0,s=0,neck=inf; 27     while (h[0]
       
        0&&h[u]==h[j]+1) 35               { 36                  neck=min(neck,e[i].flow); 37                  cur[u]=i; 38                  pre[j]=u;  u=j; 39                  if (u==t) 40                  { 41                     s+=neck; 42                     while (u) 43                     { 44                           u=pre[u]; 45                           j=cur[u]; 46                           e[j].flow-=neck; 47                           e[j^1].flow+=neck; 48                     } 49                     neck=inf; 50                  } 51                  ch=0; 52                  break; 53               } 54           } 55           if (ch) 56           { 57              if (--numh[h[u]]==0) return s; 58              int q=-1,tmp=t; 59              for (int i=p[u]; i!=-1; i=e[i].next) 60              { 61                  j=e[i].po; 62                  if (e[i].flow&&h[j]
        
         >j)&1) build(i+m+1,j+1,b[i]);102             build(0,i+m+1,b[i]);103         }104         for (int i=1; i<=m; i++)105         {106             int x;107             scanf("%d",&x);108             build(i,t,x);109         }110         if (sap()==n) puts("YES"); else puts("NO");111     }112 }
        
       
      

 

hdu5988

费用取对数，简单的费用流

1 #include
      
         2   3 using namespace std;  4   5 using namespace std;  6 struct way{
    int po,next,flow; double cost;} e[200010];  7 const int inf=100000007;  8 const double eps=1e-7;  9 int pre[110],p[110],cur[110],q[4000010]; 10 double d[110]; 11 bool v[110]; 12 int len,n,m,t,k; 13  14 void add(int x,int y,int f,double c) 15 { 16      e[++len].po=y; 17      e[len].flow=f; 18      e[len].cost=c; 19      e[len].next=p[x]; 20      p[x]=len; 21 } 22  23 void build(int x,int y, int f, double c) 24 { 25      add(x,y,f,c); 26      add(y,x,0,-c); 27 } 28  29 bool spfa() 30 { 31      int f=1,r=1; 32      for (int i=1; i<=t; i++) d[i]=inf; 33      memset(v,0,sizeof(v)); 34      d[0]=0; q[1]=0; 35      while (f<=r) 36      { 37            int x=q[f++]; 38            v[x]=0; 39            for (int i=p[x]; i!=-1; i=e[i].next) 40            { 41                int y=e[i].po; 42                if (e[i].flow&&d[x]+e[i].cost+eps
       
        0) build(0,i,x-y,0); 93             else if (x-y<0) build(i,t,y-x,0); 94         } 95         for (int i=1; i<=m; i++) 96         { 97             int x,y,f; double c; 98             scanf("%d%d%d%lf",&x,&y,&f,&c); 99             c=-log2(1.0-c);100             if (f) build(x,y,1,0);101             if (f>1) build(x,y,f-1,c);102         }103         double ans=mincost();104         ans=pow(2,-ans);105         printf("%.2lf\n",1.0-ans);106     }107 }
       
      

 

hdu5985

无穷项一般要么高斯消元要么取有限项保留对应精度即可，这里只要求出h[i][k]表示第i个在第k次操作后被全部移走的概率就可以轻易计算出答案

1 #include
      
        2  3 using namespace std; 4 double h[15][80],ans[15],p[15]; 5 int a[15],n; 6 int main() 7 { 8     int cas; 9     scanf("%d",&cas);10     while (cas--)11     {12         scanf("%d",&n);13         for (int i=1; i<=n; i++)14             scanf("%d%lf",&a[i],&p[i]);15         if (n==1)16         {17             printf("%.6lf\n",1.0);18             continue;19         }20         for (int i=1; i<=n; i++)21         {22             double tmp=1.0;23             for (int j=1; j<=76; j++)24             {25                 tmp*=p[i];26                 h[i][j]=pow(1-tmp,a[i]);27             }28         }29         for (int i=1; i<=n; i++)30         {31             ans[i]=0;32             for (int k=1; k<=75; k++)33             {34                 double tmp=1.0;35                 for (int j=1; j<=n; j++)36                     if (j!=i) tmp*=h[j][k];37                 ans[i]+=(h[i][k+1]-h[i][k])*tmp;38             }39         }40         for (int i=1; i<=n; i++)41         {42             printf("%.6lf",ans[i]);43             if (i==n) puts(""); else printf(" ");44         }45     }46 }