首页 > ACM题库 > HDU-杭电 > HDU 3972-1 M possible[解题报告]HOJ
2015
04-14

HDU 3972-1 M possible[解题报告]HOJ

1 M possible

问题描述 :

There are 3*N+2 nonnegative integers. Except two special integers, the rest 3*N integers can form N triple groups: { Vi, Vj, Vk| Vi=Vj=Vk}, each integer are at most in one triple group.

Your task is to find the two special integers.

Now, suneast is so boring. He wants to compete with you. As there is no computer available for him, he has to find the integers use his eyes! Unbelievable! So just for fairness, your program can access ONLY 1MB memory!

Tips: Impossible itself says 1 M possible —— Tourist’s quote (a topcoder target member)

输入:

The first line of the input contains an integer T(T<=3), indicating the number of test cases.

Each case begin with a line containing an integers N(2<=N<=300000, N=2(mod3) ).

The second lines contains N nonnegative integers Vi (1<=Vi<=2147483647).

输出:

The first line of the input contains an integer T(T<=3), indicating the number of test cases.

Each case begin with a line containing an integers N(2<=N<=300000, N=2(mod3) ).

The second lines contains N nonnegative integers Vi (1<=Vi<=2147483647).

样例输入:

2 
2 
1 2 
23 
1 3 1 4 5 2 1 1 3 1 4 5 2 1 1 3 1 4 5 2 1 2 1

样例输出:

1 2 
1 2

http://acm.hdu.edu.cn/showproblem.php?pid=3972
题意:输入n(300000),然后输入n个数4字节以内的正整数,输入保证每次取掉3个相同的数之后剩下2个数。。。从小到大输出这两个。。。问题的关键在于内存限制在1M以内,也就是意味着你不能全部保存下来。。。悲剧。。。

分析:喵呜大神就是牛逼啊。。。记录32位每一位出现的次数,以及每两位之间对应出现的次数a[i][j]。。。求完后都对3取余,很明显,为2的就是分给这剩下的两个数,而为1的就不好分了,这时候就要通过a[][]数组来看对应关系了,如果mod3之后为1说明这两位是对应出现的。。。
网上有人记录了每个x的各位,每个x^2的各位,最后通过a+b和a^2+b^2来求。。。牛逼 啊。。

代码:

#include<iostream>
using namespace std;

const int N=35;
int n, cn;
int a[N][N], b[N], c[N];

void cal(int k)
{
	
	int i, j;
	for(i=0, cn=0; k>0; i++, k/=2)
	{
		if(k%2==1)
		{
			b[i]++;
			c[cn++] = i;
		}
	}
	for(i=0; i<cn; i++)
		for(j=i+1; j<cn; j++)
		{
			a[c[i]][c[j]]++;
			a[c[j]][c[i]]++;
		}
}

int main()
{
	int i, j, k, cas, x, y, flag;
	scanf("%d", &cas);
	while(cas--)
	{
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		scanf("%d", &n);
		for(i=0; i<n; i++)
		{
			scanf("%d", &k);
			cal(k);
		}
		for(i=0; i<32; i++)
			b[i] %= 3;
		for(i=0; i<32; i++)
			for(j=0; j<32; j++)
				a[i][j] %= 3;
		x = 0;
		flag = -1;
		for(i=32; i>=0; i--)
		{
			x *= 2;
			if(b[i]==2)
			{
				x += 1;
				b[i]--;
			}
			else if(b[i]==1)
			{
				if(flag==-1)
				{
					x += 1;
					b[i]--;
					flag = i;
				}
				else if(a[flag][i]==1)
				{
					x += 1;
					b[i]--;
				}
			}
		}
		y = 0;
		for(i=32; i>=0; i--)
		{
			y *= 2;
			y += b[i];
		}
		if(x>y)
			swap(x, y);
		printf("%d %d\n", x, y);
	}
	
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ggggiqnypgjg/article/details/6723553


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮