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

POJ 3484 Showstopper 题解 《挑战程序设计竞赛》

目录

POJ 3484 Showstopper

句柄:N个等差数列,初项X_i,末项Y_i,公差Z_i,求出现奇数次的数?

3.1不光是查找值!“二分搜索”

其他

这题的难点在于……IO,数据集之间可能有多个空行,而且也没指定数据的上限,全靠瞎猜,欧洲人都这么散漫?

假设所有数的出现次数分别为C_1、C_2……C_n,题目中还规定次数为奇数的只有一个,那么假定C_x为奇数,其他都为偶数。设数列T为{T_i, T_i = C_1 + … + C_i},如果i>=x则T_i一定为奇数,否则一定为偶数。这就是二分的单调性,通过判断此奇偶性就可以推断x与i的位置关系。

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
#define MAX_CASE 1000000
typedef unsigned long long ULL;
ULL X[MAX_CASE], Y[MAX_CASE], Z[MAX_CASE];
ULL C[MAX_CASE];	// 每个数列中有几个数
int N;

ULL count_sum(const ULL& limit)
{
	ULL sum = 0;
	for (int i = 0; i < N; ++i)
	{
		if (limit >= Y[i])
		{
			sum += C[i];
		}
		else if (limit >= X[i])
		{
			sum += (limit - X[i]) / Z[i] + 1;
		}
	}
	return sum;
}

char buf[1024];
bool input()
{
	int f = 0;
	N = 0;
	while ((f = ((gets(buf) != NULL))) && strlen(buf) > 2)
	{
		sscanf(buf, "%I64d %I64d %I64d", &X[N], &Y[N], &Z[N]);
		N++;
	}

	return f || N;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	string line;
	while (input())
	{
		if (!N)
		{
			continue;
		}
		ULL last_bit = 0;						// 判断奇数的个数的奇偶性,只有最后一位有用
		for (int i = 0; i < N; ++i)
		{
			C[i] = (Y[i] - X[i]) / Z[i] + 1;	// 初项减末项除公差
			last_bit ^= C[i];					// 奇数的最后一位是1,两个奇数异或之后变为0,一奇一偶还是1
		}
		if (!(last_bit & 1))
		{
			cout << "no corruption" << endl;
		}
		else
		{
			ULL lb = 0, ub = 0xffffffff;
			while (ub - lb > 0)
			{
				ULL mid = (ub + lb) >> 1;
				if (count_sum(mid) & 1)
				{
					// 还在前面
					ub = mid;
				}
				else
				{
					lb = mid + 1;
				}
			}
			cout << lb << ' ' << count_sum(lb) - count_sum(lb - 1) << endl;
		}

	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

唉,本来想用我优雅的stream的,但是就是TLE,留个纪念:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
#define MAX_CASE 1000000
typedef unsigned long long ULL;
ULL X[MAX_CASE], Y[MAX_CASE], Z[MAX_CASE];
ULL C[MAX_CASE];	// 每个数列中有几个数
int N;

ULL count_sum(const ULL& limit)
{
	ULL sum = 0;
	for (int i = 0; i < N; ++i)
	{
		if (limit >= Y[i])
		{
			sum += C[i];
		}
		else if (limit >= X[i])
		{
			sum += (limit - X[i]) / Z[i] + 1;
		}
	}
	return sum;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	string line;
	while (getline(cin, line) || N)
	{
		if (line.length())
		{
			stringstream sstream;
			sstream << line;
			sstream >> X[N] >> Y[N] >> Z[N];
			++N;
			line.clear();
		}
		else
		{
			if (!N)
			{
				continue;
			}
			ULL last_bit = 0;						// 判断奇数的个数的奇偶性,只有最后一位有用
			for (int i = 0; i < N; ++i)
			{
				C[i] = (Y[i] - X[i]) / Z[i] + 1;	// 初项减末项除公差
				last_bit ^= C[i];					// 奇数的最后一位是1,两个奇数异或之后变为0,一奇一偶还是1
			}
			if (!(last_bit & 1))
			{
				cout << "no corruption" << endl;
			}
			else
			{
				ULL lb = 0, ub = 0xffffffff;
				while (ub - lb > 0)
				{
					ULL mid = (ub + lb) >> 1;
					if (count_sum(mid) & 1)
					{
						// 还在前面
						ub = mid;
					}
					else
					{
						lb = mid + 1;
					}
				}
				cout << lb << ' ' << count_sum(lb) - count_sum(lb - 1) << endl;
			}
			N = 0;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

12852969 hankcs 3484 Accepted 832K 94MS C++ 1741B 2014-05-08 18:29:34

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

分享到:更多 ()

评论 欢迎留言

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

我的开源项目

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