ZROI2018.8.9 玄学数据结构

数据结构模拟赛

题面 A B C

A. 黑桃城

直接 DFS 遍历树。子树的 DFN 序是连续的,因此转化为区间上维护,线段树即可。

B. 红五月

树剖,详细毒瘤的分类讨论

C. 海棠溪

Subtask1-3

  • 动态规划,定义 f[i,j] 表示两朵花分别位于选择的第 i,j 个人手中(令 i>j)
  • 使用滚动数组优化空间。
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF=999999999;
    const int N=200005;
    int n,t,a,b;
    int p[N];
    int f[2][N];
    int mabs(int x){return x<0?0-x:x;}
    int main(){
      scanf("%d%d%d%d",&n,&t,&a,&b);
      p[0]=a,p[1]=b;
      for(int i=2;i<=t+1;i++)scanf("%d",&p[i]);
      for(int i=0;i<=1;i++)
          for(int j=0;j<=t+1;j++)
              f[i][j]=INF;
      f[1][0]=0;
      for(int i=1;i<=t+1;i++){
          for(int j=0;j<=t+1;j++)f[(i+1)&1][j]=INF;
          for(int j=0;j<=i;j++){
              f[(i+1)&1][i]=min(f[(i+1)&1][i],f[i&1][j]+mabs(p[i+1]-p[j]));
              f[(i+1)&1][j]=min(f[(i+1)&1][j],f[i&1][j]+mabs(p[i+1]-p[i]));
          }
      }
      int ans=INF;
      for(int i=0;i<=t+1;i++)ans=min(ans,f[(t+1)&1][i]);
      printf("%d",ans);
      return 0;
    }
    

 上一篇
ZROI 提高组 Day5 ZROI 提高组 Day5
小结:暴力 & 优化 心态不能炸,暴力不能丢 对于每一个数据范围都要思考,从算法复杂度猜测入手,直到确定完整算法 对于下一个数据范围,考虑能否对上一个范围的算法做优化(比如 DP 优化) 优化大多数时候建立在基础算法上 不能放弃任
2018.10.01
下一篇 
毒瘤 % 你赛 -byGLX 毒瘤 % 你赛 -byGLX
毒瘤 % 你赛 -byGLX题面A.pdfB.pdfC.pdf 总结两次的比赛的小结: 勤写暴力 稳打模板 数组开大 心态不炸 A. 吉吉买铅笔 dijkstra 分别以 1,n 为源结点走两次最短路 注意输出边的时候要取最优解```c
2018.10.01
  目录