题解：P15093 [UOI 2025 II Stage] Odd Rows

cwxcplh · 2026-04-17 11:45:10 · 题解

竞选全场第一篇 DP 题解（不会只有我一个人想的 DP 吧）。

首先啊，我们看到这个 n\cdot m\le10^6 就很不对劲，因为它没给你限制 n 和 m 的大小，反而给你限制了整个图的大小（其实主要是怕输出超时），也就是说：我们可以在时间复杂度为 O(nm) 的情况下飞过去。

然后我们来思考怎么解决这道题啊。首先第一眼是构造，不过作者太菜了，没瞪出来构造方法。所以选择了 DP。

现在我们不考虑怎么构造这个东西，而是思考最多有多少行这个问题。你很容易发现我们可以直接 DP：设 f_{j,i} 表示考虑到第 j 列，有 i 行是偶数行，剩下的全是奇数行，这种方案是否可行。空间复杂度 O(nm)，用一下 vector 就行。

然后转移就很显然了：我们枚举一个 k 表示在当前这一列中取出 k 个 1 放在偶数行上（也就是有 k 个偶数行变成了奇数行），剩下 a_j-k 个 1 放在奇数行上（也就是有 a_j-k 个奇数行变成了偶数行），很容易想到当 f_{j-1,i}=1 时 f_{j,i-k+a_j-k} 也肯定等于 1。反之不改变值（其实就是做或运算）。

最后枚举一下最少有多少个偶数行时能够成立，那么剩下的就全是奇数行。

这里重点说一下这个 k：因为 k 的枚举显然是有限制的，首先我们要满足 k\le i，也就是我放 1 的偶数行个数必然不会超过原本有的偶数行个数；其次是 k\le a_j，也就是我这一列最多放 a_j 个 1；然后是 a_j-k\le n-i，也就是我放 1 的奇数行的个数不会超过原本有的奇数行个数；最后是 i-k+a_j-k\le n，也就是我之后的变的偶数行数不能比总行数还大。汇总在一起就是下面这一坨：

我猜你没看到下限中间的那一个限制完全没用。

这个东西因为包含 a_j，所以如果你直接这么写就相当于看脸吃饭了：运气好你能飞过去，运气不好直接卡回 O(n^2m)（其实跑不到）。

现在我们来考虑怎么构造这个矩阵。我们考虑我们从哪个状态转移到的 f_{j,i}（这里是说让 f_{j,i} 变成 1 的上一步状态），因为我们知道第一维一定是 j-1，所以我们可以单独设一个 g_{j,i} 表示上一个转移的位置是 f_{j-1,g_{j,i}}。

那么我们构造的时候只需要 dfs 一下，从 (x,y) 跳到 (x-1,g_{x,y})，如果 x=0 就返回。然后根据转移方程，我们可以得到当前这一列有 \frac{g_{x,y}+a_x-y}{2} 这么多个 1 被放在了偶数行上，剩下的在奇数行上（你把 y 看做 i-k+a_j-k，g_{x,y} 看做 i，那么只需要算出 k 就知道有多少个 1 在偶数行上了，这几个式子的来源参见转移方程），然后用 set 一通处理就行。

构造代码：

void print(int x,int y)
{
    if(x==0)
    {
        return;
    }
    print(x-1,g[x][y]);
    set<int>ss0,ss1;
    int num=(a[x]+g[x][y]-y)/2;
    int cnt=num;
    for(auto i:s0)//原本有的偶数行
    {
        if(!cnt)
        {
            break;
        }
        mp[i][x]=1;
        ss0.insert(i);
        cnt--;
    }
    cnt=a[x]-num;
    for(auto i:s1)//原本有的奇数行
    {
        if(!cnt)
        {
            break;
        }
        mp[i][x]=1;
        ss1.insert(i);
        cnt--;
    }
    for(auto i:ss0)
    {
        s0.erase(i);
        s1.insert(i);
    }
    for(auto i:ss1)
    {
        s1.erase(i);
        s0.insert(i);
    }
}

放一下暴力代码：

f[0][n]=1;
for(int j=1;j<=m;j++)
{
  for(int i=0;i<=n;i++)
  {
    if(f[j-1][i])
    {
      int l=max({0ll,(i+a[j]-n+1)/2,a[j]-n+i}),r=min(i,a[j]);
      for(int k=l;k<=r;k++)
      {
        f[j][i-k+a[j]-k]=1;
        g[j][i-k+a[j]-k]=i;
      }
    }
  }
}

现在我们考虑如何优化这个转移：我们会发现主要问题就在 k 的枚举上，那有没有什么办法把 k 的枚举变成 O(1) 或者 O(\log n) 呢？

仔细看转移方程：我们实际上就是把 [i+a_j-r\times 2,i+a_j-l\times 2] 之间与 i+a_j-r\times 2 奇偶性相同的所有位置的 f 全赋为 1，g 全赋为 i。这很像区间赋值操作，因此可以用线段树，但是我觉得线段树太麻烦了，于是我们可以用另一个方法：差分。

好吧这个差分有点诡异：因为我们要分奇偶性来考虑，那么在构造差分时，我们只需要在 i+a_j-r\times 2 的位置推入一个三元组 (1,i,1)，表示从这个位置开始将 f 赋值为 1，g 赋值为 i，在 i+a_j-l\times 2+2 的位置推入一个三元组 (1,i,-1) 表示从这个位置开始停止将 f 赋值为 1，g 赋值为 i（其实这么说不太准确，更准确的说应该是存在和不存在）。不过我们完全可以把第一个 1 省去，因为如果 g 能赋值，那么 f 就必然是 1。因为要支持快速插入和删除操作，所以我们选择使用 multiset。

当然因为奇偶性的问题，我们要设两个 multiset（虽然差分只需要一个就行）。然后维护一下就行。

放一下主要代码：

f[0][n]=1;
for(int j=1;j<=m;j++)
{
  for(int i=0;i<=n;i++)
  {
    v[i].clear();
  }
  for(int i=0;i<=n;i++)
  {
    if(f[j-1][i])
    {
      int l=max({0ll,(i+a[j]-n+1)/2,a[j]-n+i}),r=min(i,a[j]);
      v[i+a[j]-2*r].push_back(make_pair(i,1));
      v[i+a[j]-2*l+2].push_back(make_pair(i,-1));
    }
  }
  multiset<int>ms0,ms1;
  for(int i=0;i<=n;i++)
  {
    if(i&1)
    {
      for(auto k:v[i])
      {
        if(k.second==1)
        {
          ms1.insert(k.first);
        }
        else
        {
          ms1.erase(ms1.find(k.first));
        }
      }
    }
    else
    {
      for(auto k:v[i])
      {
        if(k.second==1)
        {
          ms0.insert(k.first);
        }
        else
        {
          ms0.erase(ms0.find(k.first));
        }
      }
    }
    if(i&1)
    {
      if(ms1.empty())
      {
        f[j][i]=0;
        g[j][i]=0;
      }
      else
      {
        f[j][i]=1;
        g[j][i]=(*ms1.begin());
      }
    }
    else
    {
      if(ms0.empty())
      {
        f[j][i]=0;
        g[j][i]=0;
      }
      else
      {
        f[j][i]=1;
        g[j][i]=(*ms0.begin());
      }
    }
  }
}

完结撒花！