P8865 [NOIP2022] 种花题解

FFTotoro · 2022-12-05 20:40:13 · 题解

前言

第一次参加 NOIp，赛时这一题特判 c=0 且 f=0 时每组数据只输出一个 0，惨痛爆成 99\ \text{pts}……

解法

对于每一行字符，我们首先预处理出其中 0 的“连通块”。

这里 0 的“连通块”的定义如下：

例如一个字符串 01100010100，那么它中间 0 的“连通块”就是：[1],[4,6],[8],[10,11]。预处理时可以使用 std::vector 存储。

定义一个 \texttt{C} 型的三条“边”分别为“上底”、“下底”和“高”，那么每一次统计时，我们只用枚举“高”所在的列和“下底”所在的行即可。

具体做法如下：

例如图形：

其中标记为 \texttt{*} 的地方是确定的“高”所在的列。

假设现在我们的“下底”安排在第五行，那么有如下几种情况：

“上底”在第一行：只能在 (1,2) 的位置种花，而“下底”的方案共有 3 种，根据乘法原理，共有 1\times 3=3 种方法；
“上底”在第二行：没法种花；
“上底”在第三行：本行最后一朵花的位置可以在 (3,2),(3,3),(3,4),(3,5) 上种花，有 4 中方案，结合“下底”，共有 4\times 3=12 种方法；

所以，确定好“高”所在的列后，对于第 i 行，我们只需要用 lower_bound 函数，从预处理的“连通块”数组中找到当前行高所在的列从左往右数的第一个 1，设高所在的列为 w_1，这个 1 所在的列为 w_2，那么这一行就有 w_2-w_1-1 种种花的方法。记这个值为 c_i；

那么，对于第 i 行，确定“高”后，以这一行为“下底”的种花总的方案即为（设“上底”能达到的最上方的位置为 k）：

\left(\sum\limits_{j=k}^{i-2}c_j\right)c_i

用前缀和维护即可。

同理，\texttt{F} 型就是 \texttt{C} 型的“下底”“延伸”出去。每次统计时乘一下能延伸的“空间”即可，这里不多做赘叙。

放代码：

#include<bits/stdc++.h>
#define int long long // 记得开 long long
using namespace std;
const int mod=998244353;
main(){
  ios::sync_with_stdio(false);
  int t,id; cin>>t>>id;
  while(t--){
    int n,m,c,f,sc=0,sf=0; cin>>n>>m>>c>>f;
    vector<string> a(n);
    vector<vector<int>> hr(n);
    for(auto &i:a)cin>>i;
    if(!c&&!f){cout<<"0 0\n"; continue;}
    // 被这儿的特判坑掉了一分……当时只 cout<<"0\n"，现在就是后悔，非常后悔
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++){
        if(a[i][j]==49){
          if(j&&a[i][j-1]==48)hr[i].emplace_back(j-1);
        }
        else if(j==m-1)hr[i].emplace_back(j);
      } // “连通块”预处理
    for(int i=0;i<m;i++){
      vector<int> r,v; int s0=0,s1=0;
      for(int j=0;j<=n;j++){
        if(j==n||a[j][i]==49){
          if(r.size()<3){r.clear(); continue;} // 特判，不够种花
          if(!j||a[j-1][i]==49)continue;
          v.resize(r.size()); v[0]=r[0];
          for(int k=1;k<r.size();k++)v[k]=(v[k-1]+r[k])%mod; // 前缀和操作
          for(int k=0;k<r.size();k++){
            int p=(r[k]%mod*(k>1?v[k-2]:0)%mod)%mod; // 乘法原理统计
            s0=(s0+p%mod)%mod; s1=(s1+p%mod*(r.size()-k-1)%mod)%mod; // 计数变量加上答案
          }
          r.clear(); v.clear(); continue; // 记得清空
        }
        r.emplace_back(*lower_bound(hr[j].begin(),hr[j].end(),i)-i); // 找到第一个 1 的位置
      }
      sc=(sc+s0%mod)%mod; sf=(sf+s1%mod)%mod; // 时刻谨防模溢出
    }
    cout<<sc*c<<' '<<sf*f<<endl;
  }
  return 0;
}

P8865 [NOIP2022] 种花 题解

前言

解法

P8865 [NOIP2022] 种花题解