放牧代码和思想
专注自然语言处理、机器学习算法

POJ 3109 Inner Vertices 题解 《挑战程序设计竞赛》

目录

POJ 3109 Inner Vertices

黑白棋・改:无限大的棋盘上,在横向和纵向上被包围的白子会变成黑子,求最终黑子个数?

3.3活用各种数据结构

Binary Indexed Tree

首先需要了解一下扫描线算法,扫描线算法是计算几何学上对多边形染色的算法。

如图,扫描线算法的目标是计算黄颜色多边形内部的像素点,最终将其涂色。怎么知道哪些点在内部呢?首先从顶点中y轴最小坐标出发,到最大坐标为止,画一条条水平的扫描线,扫描线必然与多边形有多个交点。第一个与第二个,第三个与第四个……之间的点就是内部点。

用严密的语言描述如下:

基本思想

        按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的象素,即完成填充工作。

对于一条扫描线填充过程可以分为四个步骤:

    (1)  求交:计算扫描线与多边形各边的交点

    (2)  排序:把所有交点按 x 坐标递增顺序来排序

    (3)  配对:确定扫描线与多边形的相交区间,第一个与第二个,第三个与第四个等等,每对交点代表扫描线与多边形的一个相交区间

    (4)  填充:显示相交区间的象素

回到题目,题目给的是一张无限大的棋盘,所以需要先进行坐标压缩,压缩之后采取扫描线法计算内部点数即可。


上图红色方格即为要染色的点,计算两个交点之间的空白点的数量的时候,由于它们的Y坐标肯定相等,那么问题转化为统计两个交点x坐标之间的点的个数。涉及到累积和,轮到树状数组出场了。

统计x的时候,需要将一个区间[交点n的x + 1,交点n+1的x – 1]的个数统统加一,树状数组本身做加法的话是logn,做n次的话是nlogn,太浪费了,BIT可以高效地求一段区间和,以及更新单个元素的值,但是无法高效地更新一个区间的值。

于是可以用双BIT来实现,一个维护初始个数,一个维护累加值,可以将复杂度控制在logn。

具体说来,可以用如下方式定义这两个BIT:bit0和bit1

其中bit1表示增量的累计和,如图:

对区间[l,r]增加x之后,前缀和的增量如上图所示。我们用bit1来维护每个元素的增加量,当然,执行add(i,x)后并不是每个元素都会改变,所以还需要用sum(bit0,i)来维护初始值的修正值。准确来说,只有l和r之间的元素才会+x,所以表示增加量的bit1[l] += x,bit1[r + 1] += -x(这里的思想和imos法是一致的,记录变化量,然后累加),假设i<l,这次add不影响sum。假设i位于l和r之间,sum(bit1,i)*i = xi,xi的意思是前i个元素每个都+x,看起来比正确答案多加了(1-l)*x的样子,所以修正值bit0必须执行bit0[l]=-(l-1)*x。假设i>r,表示增加量的sum(bit1,i)根本没发生变化(因为l位置的x和r+1位置的-x抵消掉了),这时候就得依靠bit0在r+1位置的xr减去l位置的x(l-1)得出正确答案x(r-l+1)作为最终的结果了。

这样子就可以理解上面的4个操作的由来了。嘛,尽量理解吧。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 100000 + 16
typedef long long LL;

LL bit0[MAX_N], bit1[MAX_N];	// 双BIT实现O(logn)区间加法
int N, X[MAX_N], Y[MAX_N];
vector<int> line[MAX_N];	// 每个黑子构成的一条条水平线,y坐标作为下标
bool visited[MAX_N];		// 是否已经算过了


// 求和sum{a[t], 0 <= t <= i}
LL sum(LL *b, int i)
{
	int s = 0;
	while (i > 0) 
	{
		s += b[i];
		i -= (i & -i);
	}
	return s;
}

// 求和a[from, to)
LL sum(LL* bit, int from, int to)
{
	return sum(bit, to - 1) - sum(bit, from - 1);
}

// 执行 a[i] += v
void add(LL *b, int i, LL v)
{
	while (i <= MAX_N)
	{
		b[i] += v;
		i += (i & -i);
	}
}
// 基础bit结束

// 双BIT

//[0,n]
LL sum(int i)
{
	return sum(bit1, i) * i + sum(bit0, i);
}

//(from, to]
LL sum(int from, int to)
{
	return sum(to) - sum(from);
}

// [from, to]
void add(int from, int to, LL x)
{
	add(bit0, from, -x * (from - 1));
	add(bit1, from, x);
	add(bit0, to, x * to);
	add(bit1, to, -x);
}

// 压缩坐标,将坐标的值变成“这是第几种值”,返回一共有几种坐标
// x为坐标数组,长度为N
int compress(int *p)
{
	vector<int> ps(N);

	for (int i = 0; i < N; ++i)
	{
		ps[i] = p[i];
	}

	sort(ps.begin(), ps.end());
	ps.erase(unique(ps.begin(), ps.end()), ps.end());
	for (int i = 0; i < N; ++i)
	{
		p[i] = 1 + distance(ps.begin(), lower_bound(ps.begin(), ps.end(), p[i]));	// 此处加1为了防止 i += (i & -i); 永远为0
	}
	return ps.size();
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
	{
		scanf("%d%d", X + i, Y + i);
	}
	int w = compress(X);
	int h = compress(Y);

	for (int i = 0; i < N; ++i)
	{
		line[Y[i]].push_back(X[i]);	// 一条条扫描线
	}

	LL result = N;
	for (int y = 1; y <= h; ++y)
	{
		// 对每条扫描线,计算上面空白点的个数
		vector<int>& xs = line[y];	// 纵坐标为y的那些点的横坐标,一条扫描线
		sort(xs.begin(), xs.end());
		
		for (vector<int>::iterator i = xs.begin(); i != xs.end(); ++i)
		{
			int x = *i;
			LL s = sum(x - 1, x);	// 横坐标为x的空白点个数

			if (visited[x])
			{
				result += s;		// 就是要染色的像素点
			}
			else
			{
				visited[x] = true;
			}
			add(bit0, x, -s);		// 等同于add(x, x, -s);即对count[x] -= s;这是一个复位操作,为下次统计做准备
			if (i + 1 != xs.end())
			{
				// 到下一个黑点之间空白点的个数
				// 这两个分支合并起来就是 add(x + 1, next_x - 1, 1);的意思
				if (x + 1 < *(i + 1) - 1)			// 下一个黑子
				{
					add(x + 1, *(i + 1) - 1, 1);	// 遇到了空白
				}
				else if (x + 1 == *(i + 1) - 1)
				{
					add(bit0, x + 1, 1);			// 遇到了空白,此时等同于add(x + 1, x + 1, 1);
				}
			}
		}
	}
	cout << result << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
12956715 hankcs 3109 Accepted 7328K 3469MS C++ 2599B 2014-06-07 23:22:36

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3109 Inner Vertices 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机