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//////////////////////////////////

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