欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019牛客暑期多校训练营(第四场)D triples I(构造+思维)

程序员文章站 2022-04-02 22:09:20
...

链接:https://ac.nowcoder.com/acm/contest/884/D

题意:T组样例。每组样例给出一个a(1<=a<=1e18),让用尽可能少的3的倍数,使这些数按位或起来的值为a。题目保证输入的a一定有答案。

思路:既然是按位或,那么肯定和二进制有关。显然,一个数的二进制中,奇数位上的1%3=1,偶数位上的1%3=2。那么我们就统计奇数位,偶数位上的个数并用数组记下。首先,我们最多用2个数肯定能凑出这个数。然后分类讨论。

1.a%3==0,显然就是只用a这一个数即可,否则肯定要用两个数。

2.a%3==1,我们就要想办法删去这个1。再次分类讨论:

(1)奇数位上的1和偶数位上的1都不为0,那么我们只需删去第一个奇数位上的1构造出第一个数(这个数肯定是3的倍数),然后再用上删去的那个数和第一个偶数位上的数构造出第二个数((1+2)%3==0,也肯定是3的倍数)。

(2)奇数位上的1不为0,偶数位上的1为0。那么我们也是只需删去第一个奇数位上的1构造出第一个数,再用上删去的那个数和其后的前2个奇数位的数(也就是用前三个奇数位上的数,(1+1+1)%3==0,是3的倍数)。

(3)奇数位上的1为0,偶数位上的1不为0。那么我们只需删去前两个偶数位上的数构造出第一个数((2+2)%3==1,删去后肯定是3的倍数),再用上删去的那两个数和其后的第一个偶数位的数(也就是用前三个偶数位上的数,(2+2+2)%3==0,是3的倍数)。

3.a%3==2,同理,我们要想办法删去这个2。再次分类讨论:

(1)奇数位上的1和偶数位上的1都不为0,那么我们只需删去第一个偶数位上的1构造出第一个数(这个数肯定是3的倍数),然后再用上删去的那个数和第一个奇数位上的数构造出第二个数((1+2)%3==0,也肯定是3的倍数)。

(2)奇数位上的1为0,偶数位上的1不为0。那么我们也是只需删去第一个偶数位上的1构造出第一个数,再用上删去的那个数和其后的前2个偶数位的数(也就是用前三个偶数位上的数,(2+2+2)%3==0,是3的倍数)。

(3)奇数位上的1不为0,偶数位上的1为0。那么我们只需删去前两个奇数位上的数构造出第一个数((1+1)%3==2,删去后肯定是3的倍数),再用上删去的那两个数和其后的第一个奇数位的数(也就是用前三个奇数位上的数,(1+1+1)%3==0,是3的倍数)。

注意:一定要用上删去的那若干个数,不然构造出两个数按位或后就不等于a。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,ans1,ans2,odd[65],even[65],cnto,cnte;
int main(void)
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		cnto=cnte=0;
		scanf("%lld",&a);
		if(a%3==0) 
		{
			printf("1 %lld\n",a);
			continue;
		}
		for(int i=0;i<=60;i++)
		{
			if(a&(1LL<<i))
			{
				//这里要(i+1),因为从0开始的 
				if((i+1)&1) odd[++cnto]=(1LL<<i);
				else even[++cnte]=(1LL<<i);
			}
		}
		//分类讨论 
		if(a%3==1)
		{	
			if(cnto!=0&&cnte!=0)
			{
				ans1=odd[1]+even[1];
				ans2=a-odd[1];
			}
			else if(cnto!=0)
			{
				ans1=odd[1]+odd[2]+odd[3];
				ans2=a-odd[1];
			}
			else
			{
				ans1=even[1]+even[2]+even[3];
				ans2=a-even[1]-even[2];
			}	
		}
		else
		{
			if(cnto!=0&&cnte!=0)
			{
				ans1=odd[1]+even[1];
				ans2=a-even[1];
			}
			else if(cnto!=0)
			{
				ans1=odd[1]+odd[2]+odd[3];
				ans2=a-odd[1]-odd[2];
			}
			else
			{
				ans1=even[1]+even[2]+even[3];
				ans2=a-even[1];
			}	
		}
		//cout<<(ans1|ans2)<<endl;
		printf("2 %lld %lld\n",ans1,ans2);	
	}
	
	
	return 0;	
}