首页 > 代码库 > BZOJ 刷题记录 PART 3

BZOJ 刷题记录 PART 3

2024-07-07 17:41:31   229人阅读

【前言】还是强调要少看题解。

【BZOJ1090】简单的区间DP。值得注意的是：在压缩的时候，如果是10个A压缩，那么化成（10）A后有5个字符而不是4个！（我在这里被坑了好长时间！）以下是核心代码：

for (len=2;len<=L;len++)
    for (i=1;i<=L-len+1;i++)
    {
      j=i+len-1;
      for (k=i;k<j;k++)
        f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
      for (l=1;l<=len/2;l++)
      {
        if (len%l) continue;
        flag=1;q=i;
        for (p=i+l;p<=j;p++)
        {
          if (s[p]!=s[q]) {flag=0;break;}
          q++;if (q==i+l) q=i;
        }
        if (flag) f[i][j]=min(f[i][j],f[i][i+l-1]+3+(len/l>9)+(len/l>99));
      }
    }

【BZOJ3373】很有趣的一道题。我是用N^4低飞的，枚举没一头牛，然后floyed验证是否说谎。值得注意的是，USACO上的最后一个数据（很小）我一直过不去，原来题意有点不太清楚。“可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾”。如果一头牛说谎了，我开始是把他所说的边给去掉，但其实是反向（因为他说谎了）。

【BZOJ3400】把取模后的值当做DP的下标进行处理。要开滚存。

for (i=1;i<=n;i++)
  {
    memcpy(f,g,sizeof(g));
    for (j=0;j<s;j++)
      if (g[j]) up(f[(j+a[i])%s]+=g[j]);
    up(++f[a[i]]);
    memcpy(g,f,sizeof(f));
  }
【BZOJ3401】维护一个应该叫做“单调栈”的东东。水题放松心情！

for (i=n;i;i--)
  {
    while (t&&a[q[t]]<=a[i]) t--;
    if (t) ans[i]=q[t];else ans[i]=0;
    q[++t]=i;
  }
【BZOJ1416】据XXX证明，摸球顺序可以无视。也就是可以理解为：小球是按顺序摸的。高精度模拟。

【BZOJ1150】就是在一堆数中选M组相邻的数，不能重复选，使距离和最小。有一个方法可以避免重复。比如间隔是3,2,3，你选了间隔2后显然不能选旁边的两个3了，但是要反悔怎么办？可以把这条线段的值改为左面的线段的值+右面的线段的值-自己的值。这样，如果你后来又选了这个数，表明你是选择了两个3的。

【BZOJ2660】神奇的DP。如果用01表示第I项是否选，我们可以发现100和011是相等的。根据这个来DP。

【BZOJ3370】我用n^2logN使过的，但是其实可以用N^2。

sort(a+1,a+n+1,cmp);
  for (i=1;i<=n;i++)
  {
    Miny=a[i].y;
    while (!q.empty()) q.pop();
    for (k=1;k<=n;k++)
    {
      Minx=a[k].x;
      if (a[k].y<Miny) continue;
      q.push(a[k].z);
      while (!q.empty()&&q.top()-Minx-Miny>C) q.pop();
      ans=max(ans,(int)q.size());
    }
  }

【BZOJ2657】ZJOI的水题。这可以描述成一棵树，然后求树的直径。

【BZOJ3208】开始还以为是二维树状数组，看到数据范围果断开始打暴力。T T


联系
我们