P3017 [USACO11MAR]Brownie Slicing G 题解
2021/7/29 23:07:56
本文主要是介绍P3017 [USACO11MAR]Brownie Slicing G 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CSDN同步
原题链接
这题做法还算比较明显,\(500\) 的数据范围也暗示了做法。
考虑直接二分所求答案,在 \(\mathcal{O}(n^2)\) 的时间内进行验证。如何验证 \(x\) 的合法性?
可以逐行操作。比如先考虑把第一行分成 \(\geq x\) 的 \(b\) 块。如果不可以,那么就加上第二行再分,一直叠加直到可以分出这样的 \(b\) 块为止,假设叠加到了第 \(p\) 行,那么 \([1,p]\) 就作为横向切的第一刀(即切在 \(p\) 行处),然后再对 \(p+1\) 行进行同样的操作。最后判断能否切到 \(a\) 刀即可。这个过程做 \(n\) 次。
如何验证能否把若干行分成 \(\geq x\) 的 \(b\) 块?要求线性做法,你有可能会想到再次二分?那 \(2\) 个 \(\text{log}\) 当然也可以。但不如考虑直接 \(1 - n\) 枚举列的切法,维护二维前缀和,扫到当前和 \(\geq x\) 那么就清空和,扫到最后一列看有没有 \(b\) 块。这个过程也要做 \(n\) 次。
其实说白了,就是先操作列切,合法了再操作行切,行列枚举法。加上二分,复杂度没炸,这题就轻松过了。
时间复杂度:\(\mathcal{O}(n^2 \log \sum a_{i,j})\).
注意:二分不知道怎么写 l<r
和 r=mid
的写法炸了,只能换了一种。
#include<bits/stdc++.h> using namespace std; const int N=5e2+1; inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();} int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;} inline void write(int x) { if(x<0) {putchar('-');write(-x);return;} if(x<10) {putchar(char(x%10+'0'));return;} write(x/10);putchar(char(x%10+'0')); } int r,c,a,b,s[N][N]; inline int Sum(int a,int b,int c,int d) {return s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];} inline bool check(int x) { int ans=0,st=1; for(int i=1;i<=r;i++) { int p=0,q=1; for(int j=1;j<=c;j++) if(Sum(st,q,i,j)>=x) p++,q=j+1; if(p>=b) st=i+1,ans++; } return ans>=a; } int main() { r=read(),c=read(),a=read(),b=read(); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+read(); int l=1,r=4000*500*500; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } printf("%d\n",l-1); return 0; }
这篇关于P3017 [USACO11MAR]Brownie Slicing G 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解