[GXOI/GZOI2019]与或和(单调栈)
2024-09-02 09:01:34
想了想决定把这几题也随便水个解题报告...
思路:
首先肯定得拆成二进制30位啊
此后每一位的就是个01矩阵
Q1就是全是1的矩阵个数
Q2就是总矩阵个数减去全是0的矩阵个数
玉蟾宫警告
就是单调栈乱搞对吧
本题完结
事实上有了思路其他的都是多余的对吧所以就不要介意代码了
#include<cstdio> #define mo 1000000007 ; template<typename tp>inline void read(tp &tar) { tp ret=,f=;char ch=getchar(); ;ch=getchar();} +ch-';ch=getchar();} tar=ret*f; } int n,ai[N][N],a1[N][N],a0[N][N]; int ans1,ans0; int sta1[N],sta0[N]; int main() { read(n); ;i<=n;i++) { ;j<=n;j++) { read(ai[i][j]); } } ,o=;k<;k++,o<<=) { ;i<=n;i++) { ;j<=n;j++) { if(ai[i][j]&o) a1[i][j]=a1[i-][j]+,a0[i][j]=; else a0[i][j]=a0[i-][j]+,a1[i][j]=; } } ;i<=n;i++) { ,hop0=,tmp1=,tmp0=; ;j<=n;j++) { tmp1+=a1[i][j]; while(hop1&&a1[i][j]<a1[i][sta1[hop1]]) { tmp1+=(sta1[hop1]-sta1[hop1-])*(a1[i][j]-a1[i][sta1[hop1]]); hop1--; } ans1=(ans1+((1ll*tmp1)<<k)%mo)%mo; sta1[++hop1]=j; tmp0+=a0[i][j]; while(hop0&&a0[i][j]<a0[i][sta0[hop0]]) { tmp0+=(sta0[hop0]-sta0[hop0-])*(a0[i][j]-a0[i][sta0[hop0]]); hop0--; } ans0=(ans0+((1ll*(i*j-tmp0))<<k)%mo)%mo; sta0[++hop0]=j; } } } printf("%d %d\n",ans1,ans0); ; }
我又被卡常了啊啊啊
最新文章
- redis 配置
- ios CoreData NSManagedObject 生命周期
- remount failed: Operation not permitted ,怎么办呢?
- memcache的一致性hash算法使用
- 使用Spring整合Hibernate,并实现对数据表的增、删、改、查的功能
- mssql查找备注(text,ntext)类型字段为空的方法
- android判断当前应用程序处于前台还是后台
- nls_sort和nlssort 排序功能介绍
- jquery禁用右键、文本选择功能、刷新
- 发起SSH攻击主机IP地址列表
- MocorDroid编译工程快速建立编译环境
- 基础-Servlet
- 谈谈分布式版本管理工具Git
- HDU 5060
- 中文代码示例之5分钟入门TypeScript
- Tensorflow --BeamSearch
- python---web框架本质(2)
- springBoot springSecurty: x-frame-options deny禁止iframe调用
- python实现排序算法三:插入排序
- matlab生成滤波器系数组
热门文章
- Python科学计算工具包
- Ubuntu12.04中新的快捷键(转载)
- Spring Shell简单应用
- html5 canvas+js实现ps钢笔抠图(速抠图 www.sukoutu.com)
- J20170520-ts
- 【插件开发】—— 14 Site is incorrect!编辑器启动报错!
- infuxdb时序数据库的下载(windows)一
- 【爬坑系列】之docker的overlay网络配置(未完,待续)
- Django中的cookie和session实现
- 如何用C#动态编译、执行代码[转]