A93159.「NOIP2022」种花
2026-04-08 20:59:07
发布于:广东
团队招人,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;
}
注意:这个代码在有一些编译器上无法运行
全部评论 2

2026-04-08 来自 浙江
1我去经典套题。题解不应该发题解区吗,ACGO 好像有这题吧
2026-04-08 来自 广东
1这样发有什么问题吗?
2026-04-08 来自 广东
0我不知道欸
2026-04-08 来自 广东
0是新来的?可以在题库里搜索这道题然后点进题解区发题解,这样就可以让做这题的人看到题解
2026-04-08 来自 广东
1

























有帮助,赞一个