文档章节

【BZOJ2727】双十字(动态规划,树状数组)

o
 osc_odyg6b92
发布于 2018/07/13 11:25
字数 927
阅读 16
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

#【BZOJ2727】双十字(动态规划,树状数组) ##题面 BZOJ 洛谷 ##题解 我们去年暑假的时候考试考过。 我当时写了个大暴力混了$70$分。。。。 大暴力是这么写的: 预处理每个位置向左右/上/下能够拓展的最多的长度(左右相当于分别求然后取$min$) 接着枚举双十字的中轴线,所在的列 然后枚举上面那一行,枚举下面那一行。 那么,贡献显然是上面选择的左右长度$$下面可以选择的左右长度$$上下两行分别向上/下拓展的长度。 发现复杂度瓶颈在于枚举完上面那一行之后又去枚举下面那一行。 这个东西显然可以前缀和优化,那么每次修改都是一个区间加法,并且还是加等差数列。 线段树或者树状数组就好啦? 线段树怎么维护可以参考洛谷上那道无聊的数列 树状数组的做法,首先要知道怎么维护区间加法 核心思想是差分。 我们要加一个等差数列,如果只进行一次差分,那么就是给差分数组做区间加法。 这样显然还不行,所以我们对于差分数组再差分一次,假设得到的数组是$c_i$,原数组是$a_i$,差分一次的结果是$b_i$ 那么 $$\begin{aligned} \sum_{i=1}^xa_i&=\sum_{i=1}^x\sum_{j=1}^ib[i]\ &=\sum_{i=1}^x(x-i+1)b[i]\ &=\sum_{i=1}^x(x-i+1)\sum_{j=1}^ic[i]\ &=\sum_{i=1}^xc[i]\sum_{j=i}^x(x-j+1)\ &=\sum_{i=1}^xc[i]\times\frac{1}{2}(n-i+2)(n-i+1)\ &=\frac{1}{2}\sum_{i=1}^xci \end{aligned} $$ 用树状数组维护$c[i],ic[i],i^2c[i]$即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define RG register 
#define MAX 1500000
#define MOD 1000000009
#define inv2 500000005
#define id(x,y) ((x-1)*m+y)
inline int read()
{
	RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
bool vis[MAX];
int n,m,L[MAX],U[MAX],D[MAX],ans,K;
int c1[MAX],c2[MAX],c3[MAX];
inline int lb(int x){return x&(-x);}
void modify(int x,int w)
{
	for(int i=x;i<=m;i+=lb(i))
	{
		add(c1[i],w);
		add(c2[i],1ll*x*w%MOD);
		add(c3[i],1ll*x*x%MOD*w%MOD);
	}
}
int getsum(int x)
{
	int s1=0,s2=0,s3=0,ret=0;
	for(int i=x;i;i-=lb(i))
		add(s1,c1[i]),add(s2,c2[i]),add(s3,c3[i]);
	add(ret,(1ll*(x+3)*x%MOD+2)*s1%MOD);add(ret,s3);
	add(ret,MOD-1ll*(x+x+3)*s2%MOD);
	ret=1ll*ret*inv2%MOD;
	return ret;
}
void modify(int l,int r,int w){modify(l,w);modify(r+1,MOD-w);}
void init(){for(int i=1;i<=m;++i)c1[i]=c2[i]=c3[i]=0;}
int main()
{
	n=read();m=read();K=read();
	for(int i=1;i<=n*m;++i)vis[i]=true;
	while(K--)vis[id(read(),read())]=false;
	for(int i=1;i<=n;++i)//Left
	{
		int s=0,now=(i-1)*m+1;
		for(int j=1;j<=m;++j,++now)
		{
			s=vis[now]?s+1:0;
			L[now]=s;
		}
	}
	for(int i=1;i<=n;++i)//Right
	{
		int s=0,now=i*m;
		for(int j=m;j>=1;--j,--now)
		{
			s=vis[now]?s+1:0;
			L[now]=min(L[now],s);if(L[now])--L[now];			
		}
	}
	for(int j=1;j<=m;++j)//Up
	{
		int s=0,now=j;
		for(int i=1;i<=n;++i,now+=m)
		{
			s=vis[now]?s+1:0;
			U[now]=s;if(U[now])--U[now];
		}
	}
	for(int j=1;j<=m;++j)//Down
	{
		int s=0,now=id(n,j);
		for(int i=n;i>=1;--i,now-=m)
		{
			s=vis[now]?s+1:0;
			D[now]=s;if(D[now])--D[now];
		}
	}
	for(int j=2;j<m;++j,init())
		for(int i=3;i<n;++i)
		{
			int u=id(i,j);
			if(!vis[u]){init();continue;}
			if(L[u])add(ans,1ll*D[u]*getsum(L[u]-1)%MOD);
			modify(1,L[u-m],U[u-m]);
		}
	printf("%d\n",ans);
	return 0;
}

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.1K
1
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
最短路径计算--A-STAR

A-STAR 寻找一种静态路网(本算法中为二维数组)中求解最短路径的解决办法 我们可以通过: var element = new Element(); 来创建二维数组的一个节点。 element自身包含了一些方法: element....

前叔
2012/12/14
1.8K
0
基于JavaScript的ES6虚拟机--Continuum

ECMAScript6(ES6)规范计划在今年正式发布,作为JavaScript的核心,新版本的一些特性可能会让目前的开发方式发生巨大的变化。目前一些现代浏览器(如Chrome、Firefox等)中已经逐步实现了E...

匿名
2013/01/06
1.9K
0
疯狂Spring Cloud连载(29)微服务跟踪概述

本文节选自《疯狂Spring Cloud微服务架构实战》 京东购买地址:https://item.jd.com/12256011.html 当当网购买地址:http://product.dangdang.com/25201393.html Spring Cloud教学视频:htt...

杨大仙的程序空间
2018/01/09
524
0

没有更多内容

加载失败,请刷新页面

加载更多

如何使用pip升级所有Python软件包? - How to upgrade all Python packages with pip?

问题: Is it possible to upgrade all Python packages at one time with pip ? 是否可以通过pip一次升级所有Python软件包? Note : that there is a feature request for this on the off......

法国红酒甜
12分钟前
0
0
活体检测+合成图鉴别面前,人脸“照片活化”黑产攻击一秒被擒

本文作者:y****n 如今,随着人脸技术的日趋成熟,新兴娱乐文化得到了极大的推动,尤其是随着 DeepFake、FaceSwap 等人脸编辑及生成技术的发展,虚拟主播、人脸合成带给人们全新的体验,但同...

百度开发者中心
昨天
0
0
如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
42分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
今天
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部