A93159.「NOIP2022」种花
2026-04-08 20:59:07
发布于：广东
42阅读
0回复
0点赞
团队招人，https://www.acgo.cn/application/1811737919264829440
好啦，步入正题。
思路：
大概就是手画一下找性质，对于 C 型来说，当我们固定其上下两行之后，若最左侧列从上至下都是 0，那么这样的方案书就是上端横行向右最大延申的 0 乘上下端延伸的。
然后枚举每个点然后再枚举竖直能延申多少。
然后我们发现这东西实际上是可以优化的，也就是说当我们确定一个竖直部分上端点所在行为 i 的时候，如果这个点竖直向下最长可以延申 ξ，那么我们要的就是行数为 i+2,i+ξ之间的所有可能水平延伸的长度之和。
这样的话我们就随便做一个竖直方向上的前缀和即可优化 O(n^3 )⟶O(n ^2 )，则对于 C 型的就过了。
对于维护最长能延申的距离，随便写一个 队列 即可，也就是双端队列，里面存下标，对于每个值如果为 0 那么直接插进去，如果为 1 那么更新队列里所有的下标的值即可，具体可看代码，很好理解。
然后考虑 F 型，这个需要想一下，发现对于一个确定的 C 型，变成 F 型就是乘上其下端点能够延伸的距离。这个正常做还是 O(n ^3 ) 的，优化方式也类似，类比之前的方式，维护水平延申长度的时候直接乘上竖直延申长度，然后再做个前缀和便可。
代码自己写。
有不会的，自己去看一下概念，这里提供一些网址：
1.双端队列 ： https://oi-wiki.org/ds/queue/,在下面
2.前缀和： https://oi-wiki.org/basic/prefix-sum/
是本蒟蒻发的第一次贴，不死勿喷
换个思路，其实，我这个代码会更好一些（刚刚写的）：
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
void solve(){
int t,id;
cin >> t >> id;
while(t -- ){
int n,m,c,f;
cin >> n >> m >> c >> f;
vector<string> garden(n);
for(auto &x : garden){
cin >> x;
}
vector<vector<int>> right = vector(n , vector(m + 1, 0));
for(int i = 0; i < n;i++){
for(int j = m - 1;j >= 0;j --){
if(garden[i][j] == '0'){
right[i][j] = right[i][j + 1] + 1;
}
}
}
vector<vector<int>> up = vector(n , vector(m , 0));
for(int i = 0; i< n; i++){
for(int j = 0; j < m; j++){
if(garden[i][j] == '0'){
if(i) up[i][j] = up[i - 1][j];
up[i][j] += right[i][j] - 1;
}
}
}
vector<vector<int>> down = vector(n + 1,vector(m , 0));
for(int i = n - 1; i >= 0 ;i --){
for(int j = 0;j < m; j++){
if(garden[i][j] == '0'){
down[i][j] = down[i + 1][j] + 1;
}
}
}
long long cntc = 0,cntf = 0;
for(int x = 2;x < n;x ++){
for(int y = 0; y < m - 1;y ++){
if(garden[x][y] == '1' || garden[x - 1][y] == '1'){
continue;
}
cntc += up[x - 2][y] * (right[x][y] - 1);
cntf += (long long) up[x - 2][y] * (right[x][y] - 1)*(down[x][y] - 1);
cntc %= mod;
cntf %= mod;
}
}
cout << cntc * c << ' ' << cntf * f << endl;
}
}
int main(){
solve();
return 0;
}
注意：这个代码在有一些编译器上无法运行
有帮助，赞一个