BZOJ做题记录[0512~?]-白红宇

BZOJ做题记录[0512~?]

阅读量：5248 次

发布时间：2019-06-14

本文共 24525 字，大约阅读时间需要 81 分钟。

　　觉得做一道开一篇真不好...好多想找的东西都被刷下去了...

　　至于?的日期究竟到什么时候...还是看心情...但是估计不会超过七天吧

　　最后更新时间：05/19 10:42

　　[05/14 10:56]我要哭了！！！一会儿再写题解吧去吃个饭压压惊...

　　[05/14 20:57]一天只做了2道题我在干什么啊...明天早上又是原题大赛..看来又可以早早弃疗了...

　　[05/15 11:20]果然啊..码完T1就滚去做其他事情了...

　　[05/16 20:31]早上模拟赛打了三个暴力...值得开心的是都没写挂..但还是不可避地垫底了..

　　　　　　　　 准备回寝室发现电脑在对面机房然后去拿，拿回来之后发现手机又在对面然后又去拿

　　　　　　　　 回到寝室之后发现充电器又在机房..然后跑到机房拿...

　　　　　　　　 晚上在寝室里调了1h+的热点...白天改了一些东西居然就不能用了呢..　　　　

　　　　　　　　 后来神奇地连上了..但那已经是BC开始很久之后了...

　　　　　　　　 在ideone里敲代码，但是网中途挂了，后退的时候代码没了..然后又重新敲..

　　　　　　　　 重新敲的过程中把之前代码里的一处忘写了..爆了一发OJ...

　　　　　　　　 人生好艰难啊..

　　　　　　　　 就当是攒RP好了...

　　[05/17 07:44]攒RP失败...记得昨天连上网的时候A已经好几十个人过了...等我写完两遍交上去的时候已经230+人过了

看了半个多小时B的题意等看懂的时候已经170+人过了

　　　　　　　　 结果最后他们都FST了...打得如此艰难的一场比赛居然能涨一股浓浓的省选考跪预感...

　　[05/17 14:34]好像没睡醒的时候考的试都会成绩比较好...?

　　　　　　　　 看到T2题面的时候整个人都兴奋起来了...

　　　　　　　　 初一的时候在绍一做过..当时我是全场为数不多的拿50的人呢！...

　　　　　　　　 然后啊..只有天哥一个人拿了100 ..讲题的时候他上去写了一黑板的推导...

　　　　　　　　 后来啊..每隔几个月就会自己再去推一次...所以印象不能更深刻...

　　　　　　　　 后来去看T3 打算直接暴搜搞一点部分分，先写了一个，大概能过n<=20的数据

　　　　　　　　 后来又写了一个...调了半天之后发现可以过n<=32的数据

　　　　　　　　 然后在调的过程中又想到一个..然后又写了一个..最后能跑到n<=39...

　　　　　　　　 成就感爆棚啊...但是最后发现...数据的梯度从15是直接上升到50的...三个程序无论交哪个都是30分...

　　　　　　　　　T1...刚开始发现自己不会背e..后来想了想可以算出来于是就改用pas了...

　　　　　　　　 然后卡了好久...不停地输出结果想找到一些神奇的规律...最后发现这是等比数列啊...!

　　　　　　　　　然后成功地把20分暴力优化成了40分暴力...（本地测了一些极限数据以后还以为可以>=70的好忧伤...

　　　　　　　　 今天做的人好多啊居然有70+（看到Gromah PoPoQQQ 甚至还有黄学长膜膜膜^

　　　　　　　　　感谢叉大爷出原题送温暖感觉RP--不能更爽...

　　[05/18 14:38]这种比赛一点都不有趣...看了A题想到网络流做法写了一个估计能拿40分

　　　　　　　　 第二题觉得太奇怪了...这个概率算不出来的啊..然后去看第三题...

　　　　　　　　 toptree...肯定不会写啊...然后敲了一个30分暴力...

　　　　　　　　 过了很久很久以后突然第二题有了一点思路..尽管算不出来..但是最后接近0就可以不去管了嘛...

　　　　　　　　 然后写了一个过了样例和自己造的数据..为了不超时把答案卡到0.0001...

　　　　　　　　　最后成绩是 50 50 25..

　　　　　　　　　T2时限2s我卡到0.0001只用了0.02s然后就WA了...T3标准n^2暴力居然T掉了一个点..数据的锅...

　　05.12

　　当然是用刷水题来开启新的一天><

　　感觉啊...这道题怎么做都可以..所以索性不说了

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define INF 1000000007 6 #define maxn 150010 7 struct node{ 8     int x,y; 9 }a[maxn];10 int n,f[maxn][25],m;11 void swap(int &x,int &y){12     int tmp=x;x=y;y=tmp;13 }14 int getl(int x){15     int l=1,r=n,ans=0;16     while (l<=r){17         int mid=(l+r) >> 1;18         if (a[mid].x
         
          >1;26         if (a[mid].x>x) ans=mid,r=mid-1;else l=mid+1;27     }28     return ans;29 }30 int find(int x){31     int l=1,r=n;32     while (l<=r){33         int mid=(l+r)>>1;34         if (a[mid].x==x) return mid;35         if (x
          
           b) return a;41 return b;42 }43 int getmax(int x,int y){44 if (x>y) return -INF;45 int tmp=(int)(log(y-x+1)/log(2));46 return max(f[x][tmp],f[y-(1<
           
            0&&ly==-1){60 if (getmax(getr(x),getl(y))
            
             0){63 if (getmax(getr(x),getl(y))
             
              =a[ly].y){66 if (ly-lx==y-x) printf("true");else printf("maybe");67 }else printf("false");68 }69 printf("\n");70 }71 return 0;72 }

　　由于一个下标写错调了好久..对拍出错的数据还因为脑抽手算不出正解..　

1 #include
     
       2 #include
      
        3 #include
       
         4 char s[110]; 5 int n,g[110][110]; 6 int min(int a,int b){ 7     if (a
        
         r2) j=l2;15     }16     return true;17 }18 int calc(int l,int r){19     if (g[l][r]) return g[l][r];20     int f[110];21     f[0]=0;22     for (int i=1;i<=r-l+1;i++){23         f[i]=f[i-1]+1;24         for (int j=1;j<=i;j++)25             for (int k=1;(1<
         
          <=i;k++) if (comp(l-1+i-(1<
          
           <<(k-1)),l-1+i-j+1,l-1+i)){26 if (i-(1<

　　然后啊..就去跟随wjz、qwer、yu990601等大爷的步伐去做TJOI啦

　　好像是SAM比较简单的应用，但是做的过程中还是发现自己对于算法本身有些地方理解得不够

　　感谢黄学长的解答

　　还是意料之内地TLE了几发...想起JYW一周前给我提的建议啊

　　由于很多以前的习惯导致随手memset，然后数组喜欢开大好几倍，看着不大顺眼的数组就开long long...

　　上次HNOI的两道题好像JYW就是帮我改了这样几个地方然后过掉的呢...

1 #include
     
       2 #include
      
        3 #include
       
         4 #define maxn 1000010 5 #define ll long long 6 int cnt,root,fail[maxn],a[maxn][26],v[maxn/2],q[maxn],mx[maxn],t,k,n; 7 char s[maxn/2]; 8 int sum[maxn],val[maxn]; 9 int insert(int p,int c){10     int np=++cnt;mx[np]=mx[p]+1;val[np]=1;11     while (p!=0&&a[p][c]==0) a[p][c]=np,p=fail[p];12     if (p==0) fail[np]=root;else13     {14         int q=a[p][c];15         if (mx[q]==mx[p]+1) fail[np]=q;else{16             int nq=++cnt;mx[nq]=mx[p]+1;17             for (int i=0;i<26;i++) a[nq][i]=a[q][i];fail[nq]=fail[q];18             fail[np]=fail[q]=nq;19             while (a[p][c]==q) a[p][c]=nq,p=fail[p];20         }21     }22     return np;23 }24 void pre(){25     for (int i=1;i<=cnt;i++) v[mx[i]]++;26     for (int i=1;i<=n;i++) v[i]+=v[i-1];27     for (int i=1;i<=cnt;i++) q[v[mx[i]]--]=i;28     for (int i=cnt;i;i--){29         int p=q[i];30         if (t==1) val[fail[p]]+=val[p];else val[p]=1;31     } 32     val[root]=0;33     for (int i=cnt;i;i--){34         int p=q[i];sum[p]=val[p];35         for (int j=0;j<26;j++) sum[p]+=sum[a[p][j]];36     }37 }38 void dfs(int p){39     if (val[p]>=k) return;40     k-=val[p];41     for (int i=0;i<26;i++) if (a[p][i]){42         int u=a[p][i];      43         if (sum[u]

　　Dilworth定理：DAG的最小链覆盖=最大点独立集

[05/14 15:04]杜老师的教导：

　　然后就很水辣

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define maxn 1010  6 using namespace std; 7 int T,n,m,f[maxn][maxn],a[maxn][maxn]; 8 int main(){ 9     scanf("%d",&T);10     while (T--){11         scanf("%d%d",&n,&m);12         for (int i=1;i<=n;i++)13             for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);14         memset(f,0,sizeof(f));15         for (int i=1;i<=n;i++)16             for (int j=m;j;j--) f[i][j]=max(max(f[i-1][j+1]+a[i][j],f[i][j+1]),f[i-1][j]);17         printf("%d\n",f[n][1]);18     }19 }

　　题目中的式子最终可以化成这个样子

　　（我不会用编辑器啊...

　　然后A是一行01的数组，就可以很容易地想到是代表取与不取的状态

　　也就是bij表示第i件物品与第j件物品都取能获得的收益

　　然后ci表示第i件物品的价格

　　然后用网络流做...

　　但是看了几个人的blog（

　　为什么他们的点数都是n^2的呢...?

　　先说下我的做法吧

　　点数(2n+2) 边数（n^2+2n）

　　把每个点拆成代表取与不取两个状态的两个点，之间连上容量为正无穷的边

　　对于代表不取的边，很显然，向汇点连一条容量为价格的边

　　然后考虑bij的处理方法看这样三种情况

　　第一种就是都取..这个和b无关..

　　第二种是都不取，这个时候我们需要减掉的是（b[a,b]+b[b,a]）（于是悲伤地重名了..不过没关系

　　也就是我们要令叉掉的两条边容量=这个数

　　第三种是取其中一个，图中画的是取a的示意，与t相连的已经考虑过了

　　这个时候需要减掉的依然是（b[a,b]+b[b,a]），然后叉掉的也是两条边...

　　然后做法好像就很显然了...把(b[a,b]+b[b,a])/2的容量分给每一条与s相连，以及两点之间相连的边

　　为了方便处理我们把它乘上2，然后最后答案除以2

　　然而啊由于边数比较大，刚开始较是T掉的

　　本地自己造了一组极限数据，发现要跑4s左右

　　加了当前弧优化之后还是要3s

　　然后在dfs结束之后如果流量为0就把dis修改掉

　　居然眨眼就出解了呢...

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define maxn 1010 6 #define maxm 520010 7 #define INF 1000000007 8 using namespace std; 9 int link[maxn],ter[maxm],next[maxm],w[maxm],rec[maxm],cur[maxn],opt[maxn],dis[maxn],n,e,s,t,b[maxn],a[maxn][maxn],c[maxn];10 bool vis[maxn];11 void add(int x,int y,int z){12     ter[++e]=y;next[e]=link[x];link[x]=e;w[e]=z;rec[e]=e+1;13     ter[++e]=x;next[e]=link[y];link[y]=e;w[e]=0;rec[e]=e-1;14 }15 bool spfa(){16     memset(vis,true,sizeof(vis));17     memset(dis,INF,sizeof(dis));18     int head=0,tail=1;opt[1]=s;dis[s]=0;vis[s]=false;19     while (head!=tail){20         int x=opt[head=(head+1)%maxn];21         for (int i=link[x];i;i=next[i]) if (w[i]>0&&dis[x]+1
         
          0){34         int x=dfs(ter[i],min(w[i],sum-tmp));35         w[i]-=x;w[rec[i]]+=x;tmp+=x;    36         if (w[i]>0) cur[p]=i;37         if (tmp==sum) return sum;38     }39     if (tmp==0) dis[p]=-2;40     return tmp;41 }42 int dinic(){43     int sum=0;44     while (spfa()){45         for (int i=s;i<=t;i++) cur[i]=link[i];46         sum+=dfs(s,INF);47     }48     return sum;49 }50 int main(){51     scanf("%d",&n);52     int ans=0;53     for (int i=1;i<=n;i++) 54         for (int j=1;j<=n;j++) scanf("%d",&a[i][j]),ans+=a[i][j];55     for (int i=1;i<=n;i++)56         for (int j=1;j<=n;j++) b[i]+=a[i][j]+a[j][i];57     for (int i=1;i<=n;i++) scanf("%d",&c[i]);58     s=0;t=2*n+1;e=0;59     for (int i=1;i<=n;i++){60         add(s,i,b[i]);add(n+i,t,c[i]*2);61         for (int j=1;j<=n;j++) if (i!=j) add(i,n+j,a[i][j]+a[j][i]);62         add(i,n+i,INF);63     }64     ans=ans*2;65     ans-=dinic();66     printf("%d\n",ans/2);67     return 0;68 }

05.13

　　早上发现下一场cf居然隔了12天，再下一场只隔3天...真是不科学啊...

　　建图还是比较简单的费用流...

　　平均等待时间最小也就是总等待时间最小，把每个技术人员修车的时间看做花费

　　把每个顾客当做一个点，每个技术人员拆成n个点，分别代表该技术人员修的倒数第i辆车

　　因为等待时间乘以的人数只和排在它后面的人数有关，所以用倒数定义就简单多了

　　然后就去学了ZKW费用流

　　好有趣啊^w^ 就是用KM算法的修改顶标思想来替代每次重新spfa

　　的模板自己比较喜欢

1 #include
     
       2 #include
      
        3 #include
       
         4 #define INF 1000007 5 #define maxn 1010 6 #define maxm 70000 7 int fa[maxm],next[maxm],link[maxn],w[maxm],cst[maxm],rec[maxm]; 8 int dis[maxn],a[100][10],ans,e,s,t,n,m; 9 bool vis[maxn];10 int min(int a,int b){11     if (a

　　枚举minH,然后求出对于每一个满足h[i]>=minH的球员在确定minH情况下对minV的限制minv>=vx

　　如果vx<=v[i]则说明当minv取在[vx,v[i]]时该球员是可取的，然后区间答案+1

　　第1次WA:第一次用sort，最后检查了很久才发现原来是[l,r)的！

　　第2次WA:a,b,c是长整型...解不等式的过程中会爆掉...然后我把那些数组和变量开成了long long

　　第3次TLE:long long运算太慢啦...然后又开回int

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define maxn 5010 6 #define maxm 10010 7 #define ll long long 8 int ans,s[maxm]; 9 using namespace std;10 struct point{11     int x,y;12 }p[maxn];13 bool cmp(point a,point b){14     return a.x
         
          ans) ans=s[j];    31     }32     printf("%d\n",ans);33     return 0;34 }

　　水水的状压DP

　　但是被C++的运算优先级坑了好久...

1 #include
     
       2 #include
      
        3 #include
       
         4 #define maxn 1100 5 int T,d,n,f[maxn][maxn],bin[15],fac[15],hash[15]; 6 char s[20]; 7 void pre(){ 8     fac[0]=1;for (int i=1;i<=10;i++) fac[i]=fac[i-1]*i; 9     bin[0]=1;for (int i=1;i<=10;i++) bin[i]=bin[i-1] << 1;10 }11 int main(){12     pre();13     scanf("%d",&T);14     while (T--){15         scanf("%s%d",s+1,&d);16         int n=strlen(s+1);17         for (int i=0;i<=(1<
        
         0)          22                 for (int k=1;k<=n;k++) if (((i/bin[k-1])&1)==0)                              23                     f[i+bin[k-1]][(j*10+s[n-k+1]-48)%d]+=f[i][j];                           24         int ans=f[(1<

　　不知道从哪里看到“异或”两个字...然后就想起若干月前A掉的这几道题..发现可能并不会做了啊

　　然后就跑去复习可持久化trie啦

　　又写了一遍这道题..但是怎么也过不了样例呢..最后发现啊...

　　1）insert(root[n],root[++n]...)

　　　这种时候好像root[n]会传进去一个神奇的0...

　　　　int x=root[n];

　　　　insert(x,root[++n]...)

　　2）query(tr[x].son[p^1],tr[y].son[p^1],ave,v-1)+1<<v

　　　居然先算了加法！！！

　　　　query(tr[x].son[p^1],tr[y].son[p^1],ave,v-1)+(1<<v)

1 #include
     
       2 #include
      
        3 #include
       
         4 #define maxn 600010 5 struct node{ 6     int sum,son[2]; 7 }tr[maxn*25]; 8 int n,m,cnt,root[maxn]; 9 char ch[100];10 void insert(int x,int &y,int ave,int v){11     y=++cnt;12     tr[y].sum=tr[x].sum+1;13     if (v<0) return;14     int p=((ave>>v)&1);15     tr[y].son[p^1]=tr[x].son[p^1];16     insert(tr[x].son[p],tr[y].son[p],ave,v-1);17 }18 int query(int x,int y,int ave,int v){    19     if (v<0) return 0;20     int p=((ave>>v)&1);    21     if (tr[tr[x].son[p^1]].sum==tr[tr[y].son[p^1]].sum) return query(tr[x].son[p],tr[y].son[p],ave,v-1);else22     return query(tr[x].son[p^1],tr[y].son[p^1],ave,v-1)+(1<

　　做完这道题我好开心啊...>_<

　　恩我们假设b[i]代表1~i元素的异或和,然后区间[l,r]中所有元素的异或和=b[r]^b[l-1]

　　用可持久化trie只能得到一个固定的数与一段区间的数字的异或最大值

　　如果要挑两个数的话最暴力的做法就是枚举其中一个数...这样的时间复杂度是O（nm*31）

　　考虑预处理，先不去想n的范围，我们想要得到一个数组f[i][j]表示区间[i,j]的答案

　　我们用query(x,y,z)表示区间[x,y]中的数与数z的最大异或和

　　那么从f[i][j]显然可以推出f[i][j+1]：f[i][j+1]=max(f[i][j],query(i-1,j,b[j]))

　　(至于为什么要减1和上一道题是一样的~

　　然而n的范围有12000，这样的预处理肯定是不可行的

　　考虑分块，f[i][j]的含义转变为第i块的开头（设为pos[i]）到j这个数的区间中的答案

　　一样可以用上面的转移方程，这样预处理的时间复杂度是（n^1.5*求query的复杂度）

　　能够承受~

　　对于一个询问[l,r]，先找到第一个下标>=l的块开头我们设它为k，f[k,r]作为一部分答案累计

　　如果f[k,r]并不是最终答案，那么一定会取[l-1,pos[k]-1]中的至少一个数

　　另一个数的范围呢？当然是[l-1,r]了（至于这里为什么是r不是r-1，因为我们要求的是max(b[r]^x[l-1])）

　　这样的枚举不会超过根号n个，所以询问的时间也是根号级别

　　能够承受~

　　来说说为什么WA吧~注意到刚刚”那么一定会取[l-1,pos[k]-1]中的至少一个数“

　　然后就理所当然地for (int i=l-1;i<=pos[k]-1;i++)

　　但是忘记了很重要的一个条件：i<=r

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define maxn 22010 7 #define ll long long 8 #define smaxn 415 9 using namespace std;10 struct node{11     int sum,son[2];12 }tr[maxn*40];13 int n,m,cnt,pos[smaxn+2],root[maxn];14 ll f[smaxn+2][maxn],b[maxn];15 void insert(int x,int &y,int ave,int v){16     y=++cnt;tr[y].sum=tr[x].sum+1;17     if (v<0) return;18     int p=(ave>>v)&1;19     tr[y].son[p^1]=tr[x].son[p^1];20     insert(tr[x].son[p],tr[y].son[p],ave,v-1);21 }22 ll query(int x,int y,int ave,int v){23     if (v<0) return 0;24     int p=(ave>>v)&1;25     if (tr[tr[x].son[p^1]].sum==tr[tr[y].son[p^1]].sum) return query(tr[x].son[p],tr[y].son[p],ave,v-1);else26     return query(tr[x].son[p^1],tr[y].son[p^1],ave,v-1)+(1<
          
           =x) {k=j;break;} 51 ll ans=f[k][y];52 for (int j=x-1;j
           
            <=y;j++) {53 if (x==1) ans=max(ans,query(0,root[y],b[j],31));else ans=max(ans,query(root[x-2],root[y],b[j],31));54 }55 printf("%lld\n",ans);las=ans;56 }57 }

05.14

　　今天啊早上有模拟赛（明明就是扔来一套TJOI2015 day2题...

　　并不想去做啊..然后7:30的比赛就被我拖到8:30才去开题...

　　发现BZ上T3过的人数最多..然后就去看T3

　　刚开始推出一个错的式子幸好测了一下大一点的数据。。居然能算出<1

　　后来玩了一下n=4的答案..然后找到规律了/w\

　　（膜Ginger88895推出的答案

　　虽然现在并不打算去看..但是贴在这里以后补吧

　　T2什么的一定是窝脑子坏掉了..题目都看不懂

　　题中说p<=m但是样例m=2 p=3..

　　题中说保证第一行第k列位置上是1但是样例并不啊..

　　就算这些都不管我样例算出来是6但是答案是7

　　（摔！

　　然后去看T1...比较明显的树链剖分

　　但是这个答案要怎么算啊...在纸上画了一下之后好像想到要怎么搞了

　　可是方向要换来换去好麻烦啊！

　　然而这个时候距离结（chi）束(fan)时间还有2h+

　　毕竟也是模拟赛啊..就这样不去写岂不是显得我一点救都没有了？　　

　　然后开始敲...30min后编译通过

　　测了样例居然过了，但毕竟是3个点的小样例然后自己造了一个数据也过了

　　交到BZ上发现一直在Running感觉人生真是圆满了！

　　虽然显然最后会T掉但是至少到目前为止答案是对的！不能更感动啊！

　　然后刷出了这个

　　试试新的代码高亮（被原来的丑哭了...然而感觉和想象的不大一样啊

　　[05/14 14:17]保存前后发现HTML源代码有一部分被吞掉...试了好多次都这样..

　　　　　　　　 然而突然发现那串码好眼熟啊..然后脑洞大开贴到页首HTML里去居然就可以了呢/w\

　　　　　　　　 但是行标号没有对齐字也太大了...先这样吧..总比原来自带的好多了

　　[05/14 14:33]改了blog的皮肤之后好像就可以了呢...

                      
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 50010
#define maxm 100010
#define INF 1000000007
struct
tnode{ 
    
int
l,r,wa,mx,mn,ans1,ans2;
}tr[maxn*5];
int
ter[maxm],next[maxm],link[maxn],e,cnt,sz[maxn],deep[maxn],fa[maxn][20],pos[maxn],belong[maxn],v[maxn],n,m;
using
namespace
std;
int
lca(
int
x,
int
y){ 
    
if
(deep[x]<deep[y]) swap(x,y);
    
int
i;
    
if
(deep[x]>deep[y]){ 
        
i=(
int
)(log(deep[x]-deep[y])/log(2));
        
while
(deep[x]>deep[y]){ 
            
while
(deep[x]-deep[y]>=(1<<i)) x=fa[x][i];
            
i--;
        
}
    
}
    
if
(x==y) 
return
x;
    
i=(
int
)(log(n)/log(2));
    
while
(fa[x][0]!=fa[y][0]){ 
        
while
(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        
i--;
    
}
    
return
fa[x][0];
}
void
add(
int
x,
int
y){ 
    
ter[++e]=y;next[e]=link[x];link[x]=e;
    
ter[++e]=x;next[e]=link[y];link[y]=e;
}
void
dfs1(
int
p){ 
    
sz[p]=1;
    
for
(
int
i=1;i<20&&deep[p]>(1<<i);i++) fa[p][i]=fa[fa[p][i-1]][i-1];
    
for
(
int
i=link[p];i;i=next[i]) 
if
(deep[ter[i]]==0){ 
        
fa[ter[i]][0]=p;
        
deep[ter[i]]=deep[p]+1;
        
dfs1(ter[i]);
        
sz[p]+=sz[ter[i]];
    
}
}
void
dfs2(
int
p,
int
chain){ 
    
pos[p]=++cnt;belong[p]=chain;
    
int
k=0;
    
for
(
int
i=link[p];i;i=next[i]) 
if
(deep[ter[i]]==deep[p]+1&&sz[ter[i]]>sz[k]) k=ter[i];
    
if
(!k) 
return
;
    
dfs2(k,chain);
    
for
(
int
i=link[p];i;i=next[i]) 
if
(deep[ter[i]]==deep[p]+1&&ter[i]!=k) dfs2(ter[i],ter[i]);
}
void
build(
int
p,
int
l,
int
r){ 
    
tr[p].l=l;tr[p].r=r;tr[p].mx=0;tr[p].mn=0;tr[p].ans1=0;tr[p].ans2=0;tr[p].wa=0;
    
if
(l==r) 
return
;
    
int
mid=(l+r) >> 1;
    
build(p<<1,l,mid);build((p<<1)+1,mid+1,r);
}
void
push(
int
p){ 
    
if
(!tr[p].wa) 
return
;
    
int
x=tr[p].wa,u=p<<1;
    
tr[u].mx+=x;tr[u].mn+=x;tr[u].wa+=x;
    
u=(p<<1)+1;
    
tr[u].mx+=x;tr[u].mn+=x;tr[u].wa+=x;
    
tr[p].wa=0;
}
void
update(
int
p){ 
    
int
x=p<<1,y=(p<<1)+1;
    
tr[p].mx=max(tr[x].mx,tr[y].mx);
    
tr[p].mn=min(tr[x].mn,tr[y].mn);
    
tr[p].ans1=max(max(tr[x].ans1,tr[y].ans1),tr[y].mx-tr[x].mn);
    
tr[p].ans2=max(max(tr[x].ans2,tr[y].ans2),tr[x].mx-tr[y].mn);
}
void
add(
int
p,
int
l,
int
r,
int
ave){ 
    
if
(tr[p].l==l&&tr[p].r==r){ 
        
tr[p].mx+=ave;tr[p].mn+=ave;tr[p].wa+=ave;
        
return
;
    
}
    
push(p);
    
int
mid=(tr[p].l+tr[p].r)>>1;
    
if
(r<=mid) add(p<<1,l,r,ave);
else
        
if
(l>mid) add((p<<1)+1,l,r,ave);
else
        
{ 
            
add(p<<1,l,mid,ave);
            
add((p<<1)+1,mid+1,r,ave);
        
}
    
update(p);
}
int
query_max(
int
p,
int
l,
int
r){ 
    
if
(tr[p].l==l&&tr[p].r==r) 
return
tr[p].mx;
    
push(p);
    
int
mid=(tr[p].l+tr[p].r)>>1;
    
if
(r<=mid) 
return
query_max(p<<1,l,r);
else
        
if
(l>mid) 
return
query_max((p<<1)+1,l,r);
else
            
return
max(query_max(p<<1,l,mid),query_max((p<<1)+1,mid+1,r));
    
update(p);
}
int
query_min(
int
p,
int
l,
int
r){ 
    
if
(tr[p].l==l&&tr[p].r==r) 
return
tr[p].mn;
    
push(p);
    
int
mid=(tr[p].l+tr[p].r)>>1;
    
if
(r<=mid) 
return
query_min(p<<1,l,r);
else
        
if
(l>mid) 
return
query_min((p<<1)+1,l,r);
else
                
return
min(query_min(p<<1,l,mid),query_min((p<<1)+1,mid+1,r));
    
update(p);
}
int
query_ans1(
int
p,
int
l,
int
r){ 
    
if
(tr[p].l==l&&tr[p].r==r) 
return
tr[p].ans1;
    
push(p);
    
int
mid=(tr[p].l+tr[p].r)>>1;
    
if
(r<=mid) 
return
query_ans1(p<<1,l,r);
else
        
if
(l>mid) 
return
query_ans1((p<<1)+1,l,r);
else
            
return
max(max(query_ans1(p<<1,l,mid),query_ans1((p<<1)+1,mid+1,r)),query_max((p<<1)+1,mid+1,r)-query_min(p<<1,l,mid));        
    
update(p);
}
int
query_ans2(
int
p,
int
l,
int
r){ 
    
if
(tr[p].l==l&&tr[p].r==r) 
return
tr[p].ans2;
    
push(p);
    
int
mid=(tr[p].l+tr[p].r)>>1;
    
if
(r<=mid) 
return
query_ans2(p<<1,l,r);
else
        
if
(l>mid) 
return
query_ans2((p<<1)+1,l,r);
else
            
return
max(max(query_ans2(p<<1,l,mid),query_ans2((p<<1)+1,mid+1,r)),query_max(p<<1,l,mid)-query_min((p<<1)+1,mid+1,r));        
    
update(p);
}
int
solve_max(
int
x,
int
y,
int
t){ 
    
int
ans=0;
    
while
(belong[x]!=belong[t]){ 
        
ans=max(ans,query_max(1,pos[belong[x]],pos[x]));
        
x=fa[belong[x]][0];
    
}
    
ans=max(ans,query_max(1,pos[t],pos[x]));
    
while
(belong[y]!=belong[t]){ 
        
ans=max(ans,query_max(1,pos[belong[y]],pos[y]));
        
y=fa[belong[y]][0];
    
}
    
ans=max(ans,query_max(1,pos[t],pos[y]));
    
return
ans;
}
int
solve_min(
int
x,
int
y,
int
t){ 
    
int
ans=INF;
    
while
(belong[x]!=belong[t]){ 
        
ans=min(ans,query_min(1,pos[belong[x]],pos[x]));
        
x=fa[belong[x]][0];
    
}
    
ans=min(ans,query_min(1,pos[t],pos[x]));
    
while
(belong[y]!=belong[t]){ 
        
ans=min(ans,query_min(1,pos[belong[y]],pos[y]));
        
y=fa[belong[y]][0];
    
}
    
ans=min(ans,query_min(1,pos[t],pos[y]));
    
return
ans;
}
void
solve(
int
x,
int
y,
int
z){ 
    
int
t=lca(x,y),xx=x,yy=y,mn=INF,ans=0;
    
while
(belong[x]!=belong[t]){ 
        
mn=min(mn,query_min(1,pos[belong[x]],pos[x]));
        
ans=max(ans,solve_max(fa[belong[x]][0],yy,t)-mn);
        
ans=max(ans,query_ans2(1,pos[belong[x]],pos[x]));
        
x=fa[belong[x]][0];
    
}
    
mn=min(mn,query_min(1,pos[t],pos[x]));
    
ans=max(ans,solve_max(t,yy,t)-mn);
    
ans=max(ans,query_ans2(1,pos[t],pos[x]));
    
int
mx=0;
    
while
(belong[y]!=belong[t]){ 
        
mx=max(mx,query_max(1,pos[belong[y]],pos[y]));
        
ans=max(ans,mx-solve_min(xx,fa[belong[y]][0],t));
        
ans=max(ans,query_ans1(1,pos[belong[y]],pos[y]));
        
y=fa[belong[y]][0];
    
}   
    
mx=max(mx,query_max(1,pos[t],pos[y]));
    
ans=max(ans,mx-solve_min(xx,t,t));
    
ans=max(ans,query_ans1(1,pos[t],pos[y]));
    
printf(
"%d\n"
,ans);
    
x=xx;
    
while
(belong[x]!=belong[t]){      
        
add(1,pos[belong[x]],pos[x],z);
        
x=fa[belong[x]][0];
    
}
    
add(1,pos[t],pos[x],z);
    
y=yy;
    
while
(belong[y]!=belong[t]){ 
        
add(1,pos[belong[y]],pos[y],z);
        
y=fa[belong[y]][0];
    
}
    
add(1,pos[t],pos[y],z);
    
add(1,pos[t],pos[t],-z);
}
int
main(){ 
    
scanf(
"%d"
,&n);
    
for
(
int
i=1;i<=n;i++) scanf(
"%d"
,&v[i]);
    
e=0;
    
int
x,y,z;
    
for
(
int
i=1;i<=n-1;i++) scanf(
"%d%d"
,&x,&y),add(x,y);
    
deep[1]=1;dfs1(1);cnt=0;dfs2(1,1);  
    
build(1,1,n);
    
for
(
int
i=1;i<=n;i++) add(1,pos[i],pos[i],v[i]);
    
scanf(
"%d"
,&m);
    
for
(
int
i=1;i<=m;i++) scanf(
"%d%d%d"
,&x,&y,&z),solve(x,y,z); 
}
       
     

4027: [HEOI2015]兔子与樱花

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 247 Solved: 140
[Submit][Status][Discuss]

Description

很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成，编号从0到n-1，这n个分叉点由n-1个树枝连接，我们可以把它看成一个有根树结构，其中0号节点是根节点。这个树的每个节点上都会有一些樱花，其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m，对于每一个节点i，它的儿子节点的个数和i节点上樱花个数之和不能超过m，即son(i) + c_i <= m，其中son(i)表示i的儿子的个数，如果i为叶子节点，则son(i) = 0

现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。

现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。

注意根节点不能被删除，被删除的节点不被计入载重。

Input

第一行输入两个正整数，n和m分别表示节点个数和最大载重

第二行n个整数c_i，表示第i个节点上的樱花个数

接下来n行，每行第一个数k_i表示这个节点的儿子个数，接下来k_i个整数表示这个节点儿子的编号

Output

一行一个整数，表示最多能删除多少节点。

　　首先可以看出来一个东西：是不存在将一个节点删除后再将其儿子删除的情况的或者说一定存在一种最优解不包含这种情况　

　　因为限制都是m，而将u删除之后它的樱花数和儿子节点数都会累计到w上

　　所以v如果能在删除了u之后删除，那现在也一定能删除

　　因为最终求的是节点个数的最大值，所以可以考虑贪心

　　我们是不是可以对于每个节点u，都删掉尽可能多的儿子？

　　如果不是这样的话，对答案唯一的好处就是让u上的樱花数少一些，从而能把u删掉...

　　或者是本来就能删掉u，会让u到根的路径上某一点从不能删到能删

　　而无论如何，这样牺牲子树至少1个节点所换来的收益不会超过1..所以显然不需要这样

　　然后就来想想如何删掉尽可能多的儿子

　　从限制中可以看出和点上的樱花数和儿子数两个量有关

　　然而我们可以知道如果删掉一个点，它对父亲的贡献为该点上的樱花数+它的儿子数量

　　由于自身被删掉所以还要-1

　　我们考虑这样一个数组a[i]，表示i点上的樱花数+i点未删去的儿子-1

　　所以按照a从小到大排序，能取则取就可以了

　　然后要怎么更新当前节点的a值呢，首先樱花数部分，增加的樱花数就是所有的取的点上的樱花数

　　增加的儿子就是所有取的点的儿子数量-1，所以只要把所有取的儿子节点的a加起来然后加上该点原来的樱花数和儿子数量然后-1就可以啦

                      
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 2000010
using
namespace
std;
int
ter[maxn],next[maxn],link[maxn],e,n,m,a[maxn],c[maxn],ans;
void
add(
int
x,
int
y){ 
    
ter[++e]=y;next[e]=link[x];link[x]=e;
}
void
dfs(
int
p){ 
    
if
(link[p]==0) { 
        
a[p]--;
return
;
    
}
    
int
sz=0;   
    
for
(
int
i=link[p];i;i=next[i]) dfs(ter[i]);
    
for
(
int
i=link[p];i;i=next[i]) c[++sz]=a[ter[i]];
    
sort(c+1,c+sz+1);
    
for
(
int
i=2;i<=sz;i++) c[i]+=c[i-1];
    
int
k=0;
    
for
(
int
i=sz;i;i--) 
if
(c[i]+sz+a[p]<=m){k=i;
break
;}
    
ans+=k;a[p]+=c[k]+sz-1;
}
int
main(){ 
    
scanf(
"%d%d"
,&n,&m);
    
for
(
int
i=0;i<n;i++) scanf(
"%d"
,&a[i]);
    
e=0;
int
x,y;ans=0;
    
for
(
int
i=0;i<n;i++){ 
        
scanf(
"%d"
,&x);
        
while
(x--) scanf(
"%d"
,&y),add(i,y);
    
}
    
dfs(0);
    
printf(
"%d\n"
,ans);
}
       
     

　05/17

　　看了今天的题解觉得T3的打表做法真好啊...

　　首先其实刚开始自己手算样例的时候就可以发现那些>n/2的数的分组对它以后的数是没有影响的

　　也就是说可以直接累计答案，dfs只需要搜n/2个数就可以了...

　　然后是题目说n<=100000我就真的相信真是傻...

　　稍微认真一点就会发现n一旦大了根本是不存在可行解的啊，最后限制可以变成n<=95

　　然后打个表就可以啦

　05/19

　　模拟赛打完不想订正不想做题更不想去看算法

　　前天晚上和YDC说了他建议我去学splay...

　　是啊..省选不过是一场考试而已...没必要被它打乱之前学习的计划

　　然后到现在A掉了一道..并不知道有没有写对就这样吧

                      
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 100010
using
namespace
std;
struct
T{ 
    
int
s,l,r,fa,va;
}tr[maxn];
int
delta,m,mn,root,cnt,tot;
char
ch[100];
void
update(
int
p){ 
    
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}
void
rotate(
int
x){ 
    
int
y=tr[x].fa,z=tr[y].fa;
    
if
(y==tr[z].l) tr[z].l=x;
else
tr[z].r=x;tr[x].fa=z;
    
if
(tr[y].l==x){ 
        
tr[y].l=tr[x].r;tr[tr[x].r].fa=y;   
        
tr[x].r=y;tr[y].fa=x;
    
}
else
{ 
        
tr[y].r=tr[x].l;tr[tr[x].l].fa=y;
        
tr[x].l=y;tr[y].fa=x;
    
}
    
update(y);update(x);
    
if
(y==root) root=x;
}
void
splay(
int
x){    
    
while
(tr[x].fa!=root&&x!=root){ 
        
int
y=tr[x].fa,z=tr[y].fa;     
        
if
(!((x==tr[y].l)^(y==tr[z].l))) 
        
rotate(y),rotate(x);        
        
else
rotate(x),rotate(x);
    
}
    
if
(x!=root) rotate(x);
}
void
insert(
int
p,
int
ave){ 
    
    
if
(!root) {      
        
root=++cnt;tr[cnt].va=ave;tr[cnt].s=1;
return
;
    
}   
    
int
las;   
    
while
(p!=0){ 
        
las=p;tr[p].s++;
if
(ave<=tr[p].va) p=tr[p].l;
else
p=tr[p].r;
    
} 
    
if
(ave<=tr[las].va) tr[las].l=++cnt;
else
tr[las].r=++cnt;
    
tr[cnt].fa=las;tr[cnt].s=1;tr[cnt].va=ave;
    
splay(cnt);
}
int
find(
int
p,
int
k){ 
    
if
(tr[tr[p].l].s+1==k) 
return
tr[p].va;
    
if
(tr[tr[p].l].s>=k) 
return
find(tr[p].l,k);
else
    
return
find(tr[p].r,k-tr[tr[p].l].s-1);
}
int
del(
int
&p,
int
fa){ 
    
if
(!p) 
return
0;
    
int
k;
    
if
(tr[p].va+delta<mn){ 
        
k=del(tr[p].r,p)+tr[tr[p].l].s+1;
        
tr[tr[p].r].s=tr[p].s-k;
        
p=tr[p].r;tr[p].fa=fa;
    
}
else
{ 
        
k=del(tr[p].l,p);
        
tr[p].s-=k;
    
}
    
return
k;
}
int
main(){ 
    
scanf
(
"%d%d"
,&m,&mn);
    
root=0;cnt=0;tot=0;delta=0;
int
x;
    
for
(
int
i=1;i<=m;i++){ 
        
scanf
(
"%s%d"
,ch,&x);
        
if
(ch[0]==
'I'
){ 
            
if
(x>=mn) insert(root,x-delta);
        
}
else
        
if
(ch[0]==
'A'
) delta+=x;
else
        
if
(ch[0]==
'S'
){ 
         
delta-=x;
         
tot+=del(root,0);
        
}
         
else
{ 
           
if
(x>tr[root].s) 
printf
(
"-1\n"
);
           
else
printf
(
"%d\n"
,find(root,tr[root].s-x+1)+delta);
         
}     
    
}
    
printf
(
"%d\n"
,tot);
    
return
0;
}
       
     