[关闭]
@01010101 2018-11-05T21:37:26.000000Z 字数 5043 阅读 866

noip2016

noip

DAY1T1玩具谜题

按题意模拟即可。

DAY1T2天天爱跑步

开始少考虑了一种情况。
确实是需要树上差分的。

少的情况：
s和t都在以fa[lca]为根的子树中。但此时s和t不能对fa[lca]产生贡献。
这就是树上差分和树上直接用桶维护的区别。
桶的要求是子树中的每个值都能对答案产生贡献。
树上差分:只对u到v的路径上的点有贡献。（对lca以上的点没有贡献）。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. using namespace std;
  6. int read(){
  7.     char ch;int op=1;
  8.     while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
  9.     int ret=ch-'0';
  10.     while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
  11.     return ret*op;
  12. }
  13. void write(int x){
  14.     if(x<0) putchar('-'),x=-x;
  15.     if(x>=10) write(x/10);
  16.     putchar('0'+x%10);
  17. }
  18. const int N=300000+10;
  19. const int D=25;
  20. int n,m,kk;
  21. int s[N],t[N],w[N],vis[N],val[N],dep[N],head[N],A[N<<1],B[N<<1],f[N][D+2];
  22. struct edge{
  23.     int v,nxt;
  24. }e[N<<1];
  25. void adde(int u,int v){
  26.     e[kk].v=v;
  27.     e[kk].nxt=head[u];
  28.     head[u]=kk++;
  29. }
  30. vector <int> v[N];
  31. vector <int> vec[N];
  32. vector <int> vst[N];
  33. void dfs(int u,int fa){
  34.     dep[u]=dep[fa]+1;f[u][0]=fa;
  35.     for(int i=1;i<=D;++i)
  36.         f[u][i]=f[f[u][i-1]][i-1];
  37.     for(int i=head[u];i!=-1;i=e[i].nxt)
  38.         if(e[i].v!=fa)  
  39.             dfs(e[i].v,u);
  40. }
  41. int lca(int u,int v){
  42.     if(dep[u]<dep[v]) swap(u,v);
  43.     for(int i=D;i>=0;--i)
  44.         if(dep[f[u][i]]>=dep[v])
  45.             u=f[u][i];
  46.     if(u==v) return u;
  47.     for(int i=D;i>=0;--i)
  48.         if(f[u][i]!=f[v][i]){
  49.             u=f[u][i];
  50.             v=f[v][i];
  51.         }
  52.     return f[u][0];
  53. }
  54. void dfs1(int u,int fa){
  55.     int tmpa=A[dep[u]+w[u]];
  56.     int tmpb=B[w[u]-dep[u]+n];
  57.     for(int i=head[u];i!=-1;i=e[i].nxt){
  58.         int v=e[i].v;
  59.         if(v!=fa){
  60.             dfs1(v,u);
  61.         }
  62.     }
  63.     if(vis[u]) A[dep[u]]+=vis[u];
  64.     int sz=v[u].size();
  65.     for(int i=0;i<sz;++i){
  66.         B[v[u][i]+n]++;
  67.     }
  68.     val[u]+=A[dep[u]+w[u]]-tmpa;
  69.     val[u]+=B[w[u]-dep[u]+n]-tmpb;
  71.     sz=vec[u].size();   
  72.     for(int i=0;i<sz;++i){
  73.         B[vec[u][i]+n]--;
  74.     }
  75.     sz=vst[u].size();
  76.     for(int i=0;i<sz;++i){
  77.         A[vst[u][i]]--;
  78.     }
  79. }
  80. int main(){
  81. //  freopen("test.in","r",stdin);
  82. //  freopen("test.out","w",stdout);
  83.     int a,b,l;
  84.     memset(head,-1,sizeof(head));
  85.     n=read();m=read();
  86.     for(int i=1;i<n;++i){
  87.         a=read();b=read();
  88.         adde(a,b);adde(b,a);
  89.     }
  90.     for(int i=1;i<=n;++i){
  91.         w[i]=read();
  92.     }
  93.     dfs(1,0);
  94.     for(int i=1;i<=m;++i){
  95.         s[i]=read();t[i]=read();
  96.         l=lca(s[i],t[i]);
  97.         if(l!=s[i]&&l!=t[i]){
  98.             vis[s[i]]++;
  99.             vst[l].push_back(dep[s[i]]);
  100.             v[t[i]].push_back(dep[s[i]]-2*dep[l]);
  101.             vec[l].push_back(dep[s[i]]-2*dep[l]);
  102.             if(dep[l]+w[l]==dep[s[i]]) val[l]--;
  103.         }
  104.         else {
  105.             if(l==s[i]&&l!=t[i]){
  106.                 v[t[i]].push_back(-dep[s[i]]);
  107.                 vec[l].push_back(-dep[s[i]]);
  108.             }
  109.             else if(l==t[i]&&l!=s[i]){
  110.                 vis[s[i]]++;
  111.                 vst[l].push_back(dep[s[i]]);
  112.             }
  113.             else{
  114.                 if(w[s[i]]==0) val[s[i]]++;
  115.             }
  116.         }
  117.     }
  118.     dfs1(1,0);
  119.     for(int i=1;i<=n;++i){
  120.         write(val[i]);putchar(' ');
  121.     }
  122.     return 0;
  123. }

DAY1T3换教室

相对简单的概率dp，一定要把所有情况列举出来

dp[i][j][1/0] 表示到第i节课，换了j节课,1表示当前申请了换课，0表示当前没申请换课

1.当前的课不换的情况：(1)上一节课也没换；(2)上一节课换了----成功or不成功；
2.当前的课换的情况:
(1)当前课成功换了：a.上一节课换了----上一节课成功or不成功b.上一节课没换；
(2)当前的课换了失败：a.上一节课换了----上一节课成功or不成功b.上一节课没换；

DAY2T1组合数问题

法一：先把K分解质因数，然后二维递推每个组合数中含这些因子的情况。（先处理每个数，在处理组合数），最后O(1)查询。（主要是观察到K最大为21，质因数就2个）
法二：预处理杨辉三角（模k），然后处理出二维前缀和，最后O(1)查询。

DAY2T2蚯蚓

关键是要发现强制增长的性质。一段蚯蚓在切断后之前的增长就没有了，然后就开始想取维护一个标记，表示在什么时候开始增长。可是这样就不能保证用优先队列找出的最大值准确。（好像也可以，在重定义小于符号的时候用（当前时刻-开始累计的时刻）*系数+开始长度）。所以就让每个蚯蚓强制从时刻1开始增长，所以最开始的长度可能是负数。
最开始想用线段树求第K大。但是高达1e8就没有办法了，而且如果强制增长会出现负数。也没有办法离散化。
开始没注意数据范围就用优先队列了，TLE了3个点。
看了题解发现就是一个小性质。维护3个队列。第一个是原队列，第二个是切后长蚯蚓队列，第三个是切后短蚯蚓队列。这三个队列分别满足单调性。

  1. queue <int> q[3];
  2. int main(){
  3. //  freopen("a.txt","r",stdin);
  4.     n=read();m=read();qq=read();
  5.     u=read();v=read();t=read();
  6.     p=(double)u/v;
  7.     for(int i=1;i<=n;++i) a[i]=read();
  8.     sort(a+1,a+n+1);
  9.     for(int i=1;i<=n;++i) q[0].push(a[n-i+1]);
  10.     while(m--){
  11.         A=-INF;B=-INF;C=-INF;
  12.         if(!q[0].empty())A=q[0].front();
  13.         if(!q[1].empty())B=q[1].front();
  14.         if(!q[2].empty())C=q[2].front();
  16.         if(A>=B&&A>=C){ps=A;q[0].pop();}
  17.         else if(B>=A&&B>=C){ps=B;q[1].pop();}
  18.         else {ps=C;q[2].pop();}
  20.         ps+=delta;
  21.         if(++cnt==t){
  22.             cnt=0;
  23.             write(ps);putchar(' ');
  24.         }
  25.         nw1=ps*p,nw2=ps-nw1;
  26.         delta+=qq;
  27.         nw1-=delta;
  28.         nw2-=delta;
  29.         if(nw1>=nw2){
  30.             q[1].push(nw1);
  31.             q[2].push(nw2);
  32.         }
  33.         else{
  34.             q[1].push(nw2);
  35.             q[2].push(nw1);
  36.         }
  37.     }
  38.     putchar('\n');
  39.     cnt=0;
  40.     while(!q[0].empty()||!q[1].empty()||!q[2].empty()){
  41.         A=-INF;B=-INF;C=-INF;
  42.         if(!q[0].empty())A=q[0].front();
  43.         if(!q[1].empty())B=q[1].front();
  44.         if(!q[2].empty())C=q[2].front();
  45.         if(A>=B&&A>=C){ps=A;q[0].pop();}
  46.         else if(B>=A&&B>=C){ps=B;q[1].pop();}
  47.         else {ps=C;q[2].pop();}
  49.         if(++cnt==t){
  50.             ps+=delta;
  51.             cnt=0;
  52.             write(ps);putchar(' ');
  53.         }
  54.     }
  55.     return 0;
  56. }

DAY2T3愤怒的小鸟

状压。没有想象中的难。
关键在于要发现三点可以确定一条抛物线。一点是起点，所以我们定义一条抛物线就是cover[i][j]就是经过i点和j点的那条抛物线经过的点的集合（状压）。

  1. int main(){
  2.     T=read();
  3.     while(T--){
  4.         n=read();m=read();
  5.         t=(1<<n)-1;
  6.         for(int i=1;i<=n;++i)
  7.             scanf("%lf%lf",&a[i].x,&a[i].y);
  8.         memset(cover,0,sizeof(cover));
  9.         for(int i=1;i<=n;++i){
  10.             cover[i][i]=(1<<(i-1));
  11.             double xi=a[i].x,yi=a[i].y;
  12.             for(register int j=1;j<=n;++j){
  13.                 if(fabs(a[i].x-a[j].x)<eps) continue;
  14.                 double xj=a[j].x,yj=a[j].y;
  15.                 double B=(yj*xi*xi-yi*xj*xj)/(xi*xi*xj-xi*xj*xj);
  16.                 double A=(yi-xi*B)/(xi*xi);
  17.                 if(A>-eps) continue;
  18.                 for(register int k=1;k<=n;++k)
  19.                     if(fabs(a[k].y-A*a[k].x*a[k].x-B*a[k].x)<eps)
  20.                         cover[i][j]|=(1<<(k-1));
  21.             }
  22.         }
  23.         memset(dp,INF,sizeof(dp));
  24.         dp[0]=0;
  25.         for(register int i=1;i<=n;++i)
  26.             for(register int j=0;j<=t;++j)
  27.                 if(dp[j]<INF)
  28.                 for(register int k=1;k<=n;++k)
  29.                     dp[(j|cover[i][k])]=min(dp[(j|cover[i][k])],dp[j]+1);
  30.         printf("%d\n",dp[t]);       
  31.     }
  32.     return 0;
  33. }

由此，noip2016所有题就写完了。
模拟
树上差分
概率dp
数学
数据结构（队列）+思维
状压dp

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注