首页 > ACM题库 > HDU-杭电 > HDU 1156 Brownie Points II-线段树-[解题报告] C++
2013
12-03

HDU 1156 Brownie Points II-线段树-[解题报告] C++

Brownie Points II

问题描述 :

Stan and Ollie play the game of Odd Brownie Points. Some brownie points are located in the plane, at integer coordinates. Stan plays first and places a vertical line in the plane. The line must go through a brownie point and may cross many (with the same x-coordinate). Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line.
Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.

The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn’t count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.

Stan and Ollie each try to maximize his own score. When Stan plays, he considers the responses, and chooses a line which maximizes his smallest-possible score.

输入:

Input contains a number of test cases. The data of each test case appear on a sequence of input lines. The first line of each test case contains a positive odd integer 1 < n < 200000 which is the number of brownie points. Each of the following n lines contains two integers, the horizontal (x) and vertical (y) coordinates of a brownie point. No two brownie points occupy the same place. The input ends with a line containing 0 (instead of the n of a test).

输出:

For each input test, print a line of output in the format shown below. The first number is the largest score which Stan can assure for himself. The remaining numbers are the possible (high) scores of Ollie, in increasing order.

样例输入:

11
3 2
3 3
3 4
3 6
2 -2
1 -3
0 0
-3 -3
-3 -2
-3 -4
3 -7
0

样例输出:

Stan: 7; Ollie: 2 3;

        hdu 1156 Color the ball

        直接拿数组来做的话会超时…… 

        那就线段树吧,这道题主要是线段树的更新啦, 只要树上的某个节点的区间符合需要更新的区间,OK,那就只更新该节点就i行了, 而不用一直更新到叶子结点,不然的话效率就降到到O(n^2)了…

         

#include <stdio.h>
#include <string.h>

#define MAX 100005
#define NODE_NUM 450000

struct node {
	int l, r;
	int val;
};

node tree[NODE_NUM];
int m;
int ans[MAX];

void buildTree(int l, int r, int n) {
	tree[n].l = l;
	tree[n].r = r;
	tree[n].val = 0;

	if (l == r)
		return ;

	int mid = (l + r)>>1;
	buildTree(l, mid, n<<1);
	buildTree(mid + 1, r, n<<1|1);
}

void query(int l, int r, int n) {
	if (tree[n].l == l && tree[n].r == r) {
		tree[n].val++;
		return ;
	} else {
		int mid = (tree[n].l + tree[n].r)>>1;
		if (r <= mid) {
			query(l, r, n<<1);
		} else if (l > mid) {
			query(l, r, n<<1|1);
		} else {
			query(l, mid, n<<1);
			query(mid + 1, r, n<<1|1);
		}
	}
}

void getResult(int n) {
	if (tree[n].l == tree[n].r) {
		ans[m] = tree[n].val;
		++m;

		return ;
	} else {
		tree[n<<1].val += tree[n].val;
		tree[n<<1|1].val += tree[n].val;

		getResult(n<<1);
		getResult(n<<1|1);
	}
}

int main() {
	int n;
	int a, b;
	int i;

	while (scanf("%d", &n) == 1 && n) {
		m = 0;
		buildTree(1, n, 1);

		for (i = 0; i < n; i++) {
			scanf("%d%d", &a, &b);
			query(a, b, 1);
		}

		getResult(1);
		printf("%d", ans[0]);
		for (i = 1; i < m; i++) {
			printf(" %d", ans[i]);
		}
		printf("\n", m);
	}

	return 0;
}


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。