HNOI2012 双十字 DP+树状数组优化

2/10/2017来源:ASP.NET技巧人气:783

题目链接:bzoj点我:-) 洛谷点我:-) 题目描述: 在C 部落,双十字是非常重要的一个部落标志。所谓双十字,由两条水平的和一条竖直的”1“线段组成,要求满足以下几个限制: ·两条水平的线段不能在相邻的两行。 ·竖直线段上端必须严格高于两条水平线段,下端必须严格低于两条水平线段。 ·竖直线段必须将两条水平线段严格划分成相等的两半。 ·上方的水平线段必须严格短于下方的水平线段。 现在给定一个 R*C的01 矩阵,要求计算出这个 01 矩阵中有多少个双十字。注意最终的结果可能很大,只要求输出双十字的个数 mod 1,000,000,009 的值

输入格式: 第一行为用空格隔开的两个正整数 R和C,分别表示01矩阵的行数和列数。输入文件第二行是一个非负整数N,表示01矩阵中”0“的个数。接下来的N行,每行为用空格隔开的两个正整数x和y(1<=x<=R,1<=y<=C),表示(x,y)是一个”0“。数据保证N个”0“的坐标两两不同。数据保证R,C,N<=10,000,R*C<=1,000,000.(事实上R*C可能稍大于原设定)

输出格式: D mod 1,000,000,009 的结果,其中D 为要求的 01矩阵中双十字的个数。

思路: 首先因为R与C不确定,所以我们需要将点们放在一个一维数组中,算算编号就好了 接下来记录lr[i]down[i]分别表示点i最多可以向左右延伸和向下延伸多少个1(不包括自己)

然后我们枚举双十字的下面那个交点,推一推公式:

{注:len是下面横线的长度,top表示能到达的最上的位置(连续的1),j是上面的横线的中心位置} 对于一个点i,它对答案的贡献是: ∑lr[i]len=1min(lr[j],len−1)×down[i]×(j−top) 显然这个min非常恶心,我们考虑把它拆开成下面的样子: 1.当(lr[j] <= len-1) 贡献是∑lr[i]len=1lr[j]×down[i]×(j−top) 2.当(lr[j] > len-1) 贡献是∑lr[i]len=1(len−1)×down[i]×(j−top)

再进一步变形: 1.当(lr[j] <= lr[i]) 贡献是(lr[i]×lr[j]−lr[j]×(lr[j]+1)/2)×down[i]×(j−top) 2.当(lr[j] > lr[i]) 贡献是lr[i]×(lr[i]−1)/2×down[i]×(j−top) (对于1的解释: lr[i]×lr[j]是总方案数,lr[j]×(lr[j]+1)/2是不合法方案数)

现在,需要解决的是所有带j的式子,我们定义3个树状数组t1, t2, t3,分别记录: 1.−lr[j]∗(lr[j]+1)/2)×(j−top) 2.lr[j]×(j−top) 3.(j−top) 把lr[i]作为位置插入,先枚举列再枚举行,每次注意清空。 并且因为两根横线不能挨在一起,所以枚举点(i, j)插入(i-1, j)的值

感想: 啊我是湖南的为什么这么难qwq 这题我初一的时候抄了一遍题解,然后高一又抄了一遍题解。。 比较怀疑小时候到底看懂了没。。 其实也不是特别难吧,还是可以想一想推一推的 下方程序中的top与解释有一点点不一样,是解释的top-1

代码

//miaomiao 2017.2.7 #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define Set(a, v) memset(a, v, sizeof(a)) #define For(i, a, b) for(int i = (a); i <= (int)(b); i++) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--) #define N (10000+5) #define NM (1200000+5) const LL MOD = 1e9+9; int n, m, lr[NM], L[NM], R[NM], down[NM]; bool is0[NM]; struct Tbit{ LL c[N]; void clear(){Set(c, 0);} int lowbit(int x){return x&(-x);} void add(int x, LL v){ while(x < N){c[x] = (c[x]+v)%MOD; x += lowbit(x);} } LL query(int x){ LL ret = 0; while(x > 0){ret = (ret+c[x])%MOD; x -= lowbit(x);} return ret; } }t1, t2, t3; int ID(int x, int y){return m*(x-1)+y;} inline void init(){ For(i, 1, n){ L[ID(i,1)] = !is0[ID(i,1)]; R[ID(i,m)] = !is0[ID(i,m)]; For(j, 2, m) if(!is0[ID(i,j)]) L[ID(i,j)] = L[ID(i,j-1)]+1; Forr(j, m-1, 1) if(!is0[ID(i,j)]) R[ID(i,j)] = R[ID(i,j+1)]+1; For(j, 1, m) if(!is0[ID(i,j)]) lr[ID(i,j)] = min(L[ID(i,j)], R[ID(i,j)])-1; } For(i, 1, m){ down[ID(n,i)] = !is0[ID(n,i)]; Forr(j, n-1, 1) if(!is0[ID(j,i)]) down[ID(j,i)] = down[ID(j+1,i)]+1; Forr(j, n, 1) if(down[ID(j,i)]) down[ID(j,i)]--; } } inline void work(){ int top, now; LL ans = 0; For(j, 1, m){ top = 0; t1.clear(); t2.clear(); t3.clear(); For(i, 1, n){ if(is0[ID(i,j)]){top=i; t1.clear(); t2.clear(); t3.clear(); continue;} now = ID(i,j); ans += t1.query(lr[now])*down[now]%MOD; ans += t2.query(lr[now])*down[now]*lr[now]%MOD; ans += (t3.query(m)-t3.query(lr[now]))*lr[now]*(lr[now]-1)/2*down[now]%MOD; ans %= MOD; if(i==1) continue; now = ID(i-1,j); if(lr[now]){ t1.add(lr[now], -lr[now]*(lr[now]+1)/2%MOD*(i-1-top-1)%MOD); t2.add(lr[now], lr[now]*(i-1-top-1)%MOD); t3.add(lr[now], i-1-top-1); } } } PRintf("%lld\n", (ans+MOD)%MOD); } int main(){ #ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif int cnt1, x, y; scanf("%d%d%d", &n, &m, &cnt1); For(i, 1, cnt1){scanf("%d%d", &x, &y); is0[ID(x, y)] = true;} init(); work(); return 0; }