Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

算起来也写了一天多,虽然写的很搓,也算是AC了!

Posted by xinshengzzy at 2016-03-16 21:38:27 on Problem 1009
//problem 1009
#include <iostream>
#include <vector>
using namespace std;

struct rle
{
	int value;
	int length;
	int index;
};

vector<rle> v_in;
vector<rle> v_out;

void update_output(int value, int len)
{
	if(v_out.empty() || value != v_out[v_out.size() - 1].value)
	{
		rle item;
		item.value = value;
		item.length = len;
		v_out.push_back(item);
	}
	else v_out[v_out.size() - 1].length += len;
}

int find_pre(int i, int k, int width)
{
	int pre = i;
	int index = v_in[i].index + k - width;
	if(index >= 0)
	{
		while(v_in[pre].index > index) --pre;
		while(v_in[pre].index + v_in[pre].length <= index) ++pre;
	}
	else pre = -1;
	return pre;
}

int find_post(int i, int k, int width)
{
	int post = i;
	int index = v_in[i].index + k + width;
	int n = v_in[v_in.size() - 1].index + v_in[v_in.size() - 1].length;
	if(index < n)
	{
		while(v_in[post].index > index) --post;
		while(v_in[post].index + v_in[post].length <= index) ++post;
	}
	else post = -1;
	return post;
}

int find_edge(int i, int k, int width)
{
	int res = 0;
	int index = v_in[i].index + k;
	if(0 != index%width && index - 1 < v_in[i].index)
	{
		res = max(res, abs(v_in[i].value - v_in[i - 1].value));
	}
	if(width - 1 != index%width && index + 1 >= v_in[i].index + v_in[i].length)
	{
		res = max(res, abs(v_in[i].value - v_in[i + 1].value));
	}
	int pre = find_pre(i, k, width);
	int post = find_post(i, k, width);

	if(pre >= 0)
	{
		res = max(res, abs(v_in[i].value - v_in[pre].value));
		if(0 != index%width && index - width - 1 < v_in[pre].index)
			res = max(res, abs(v_in[i].value - v_in[pre - 1].value));
		if(width - 1 != index%width && index - width + 1 >= v_in[pre].index + v_in[pre].length)
			res = max(res, abs(v_in[i].value - v_in[pre + 1].value));
	}

	if(post >= 0)
	{
		res = max(res, abs(v_in[i].value - v_in[post].value));
		if(0 != index%width && index + width - 1 < v_in[post].index)
			res = max(res, abs(v_in[i].value - v_in[post - 1].value));
		if(width - 1 != index%width && index + width + 1 >= v_in[post].index + v_in[post].length)
			res = max(res, abs(v_in[i].value - v_in[post + 1].value));
	}
	return res;
}

int main()
{
	int width;
	while(cin >> width && width)
	{
		v_in.clear();
		v_out.clear();
		int value, len;
		int index = 0;
		while(cin >> value >> len)
		{
			if(0 == value && 0 == len) break;
			rle item;
			item.value = value;
			item.length = len;
			item.index = index;
			v_in.push_back(item);
			index += len;
		}

		for(int i = 0; i < v_in.size(); ++i)
		{
			int lower = 0;
			int higher;
			int res;
			while(lower <= min(width - 1, v_in[i].length - 1))
			{
				higher = min(width - 1, v_in[i].length - 1);
				int pre = find_pre(i, lower, width);
				int post = find_post(i, lower, width);
				if(pre < 0)
					higher = min(higher, width - 1 - v_in[i].index);
				else
					higher = min(higher, 
						v_in[pre].index + v_in[pre].length - 1 + width - v_in[i].index);
				if(post >= 0)
					higher = min(higher, 
						v_in[post].index + v_in[post].length - 1 - width - v_in[i].index);

				res = find_edge(i, lower, width);
				update_output(res, 1);

				if(higher > lower + 1)
				{
					res = find_edge(i, lower + 1, width);
					update_output(res, higher - lower - 1);
				}

				if(higher > lower)
				{
					res = find_edge(i, higher, width);
					update_output(res, 1);
				}
				lower = higher + 1;
			}

			if(lower < v_in[i].length)
			{
				res = find_edge(i, lower, width);
				update_output(res, 1);
				++lower;
			}

			higher = v_in[i].length - 1 - width - 1;
			if(lower <= higher) 
			{
				update_output(0, higher - lower + 1);
				lower = higher + 1;
			}

			while(lower < v_in[i].length)
			{
				higher = v_in[i].length - 1;
				int pre = find_pre(i, lower, width);
				int post = find_post(i, lower, width);
				if(pre < 0)
					higher = min(higher, width - 1 - v_in[i].index);
				else
					higher = min(higher, 
						v_in[pre].index + v_in[pre].length - 1 + width - v_in[i].index);
				if(post >= 0)
					higher = min(higher, 
						v_in[post].index + v_in[post].length - 1 - width - v_in[i].index);

				res = find_edge(i, lower, width);
				update_output(res, 1);

				if(higher > lower + 1)
				{
					res = find_edge(i, lower + 1, width);
					update_output(res, higher - lower - 1);
				}

				if(higher > lower)
				{
					res = find_edge(i, higher, width);
					update_output(res, 1);
				}
				lower = higher + 1;				
			}
		}
		cout << width << endl;
		for(int i = 0; i < v_out.size(); ++i)
			cout << v_out[i].value << " " << v_out[i].length << endl;
		cout << "0 0" << endl;
	}
	cout << "0" << endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator