2019牛客暑期多校训练营（第四场）D——triples I（思维）

链接：https://ac.nowcoder.com/acm/contest/884/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.

He has decided to input several multiples of 3 and the output of the program should be his favorite number aaa.

Because he is lazy, he decided to input as few numbers as possible. He wants you to construct such an input for every aaa he chose.

It's guaranteed that for every aaa in the input there is such a solution. If there're multiple solutions you can output any.

输入描述:

There're multiple test cases in a test file.

The first line contains a positive integer TTT - the number of test cases.

In each of the following TTT lines there is one positive integer aaa.

输出描述:

For each test case output a line. First you need to output the number of numbers in your input, and then you need to output these numbers, separating by spaces.

示例1

输入

复制

2
3
7

输出

复制

1 3
2 3 6

说明

3=3, (3|6)=7

备注:

1≤T≤1051 \leq T \leq 10^51≤T≤105, 1≤a≤10181 \leq a \leq 10^{18}1≤a≤1018.

题意：给一个t表示有t个数，然后答案是输出最少数量的数或起来等于它，先输出数的个数，再输出数有啥~~

题解：此题本来不想写博客的，后来想想还是写了。给出一个数，首先想到，一个数或的话与二进制有关，后来想想发现，转换成二进制后，奇数位上1代表的十进制数mod3=1偶数位上的话是mod3=2，这样我们就可以分类讨论了，注意的是，所有的1代表的十进制都要用到，这样才能保证或起来是这个数~~讨论分为4类：

第一类：本身是3的倍数，输出本身即可

第二类：全是mod3=1的

第三类：全是mod3=2的

第四类：既有mod3=1的也有mod3=2的

具体处理细节看代码：

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 520;
ll a[MAX],b[MAX];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		ll n;
		scanf("%lld",&n);
		if(n%3==0) {//第一类
			printf("1 %lld\n",n);
			continue;
		}
		ll sum=1;
		int cnt1=0;
		int cnt2=0;
		int cnt=1;
		while(n){
			if((n&1)&&(cnt&1)) a[++cnt1]=sum;
			else if((n&1)&&!(cnt&1)) b[++cnt2]=sum;
			n>>=1;
			cnt++;
			sum*=2;
		}
		if(cnt1!=0&&cnt2==0){//第二类
			ll sum1=0;
			ll sum2=0;
			sum1=a[1]+a[2]+a[3];
			if(cnt1%3==0){
				for (int i = 4; i <= cnt1;i++){
					sum2+=a[i]; 
				}
			}
			else if(cnt1%3==1){
				for (int i = 2; i <= cnt1;i++){
					sum2+=a[i]; 
				}
			}
			else if(cnt1%3==2){
				for (int i = 3; i <= cnt1;i++){
					sum2+=a[i]; 
				}
			}
			printf("2 %lld %lld\n",sum1,sum2);
		//	cout << (sum1|sum2) << endl;
		}
		else if(cnt1==0&&cnt2!=0){//第三类
			ll sum1=0;
			ll sum2=0;
			sum1=b[1]+b[2]+b[3];
			if(cnt2%3==0){
				for (int i = 4; i <= cnt2;i++){
					sum2+=b[i]; 
				}
			}
			else if(cnt2%3==1){
				for (int i = 2; i <= cnt2;i++){
					sum2+=b[i]; 
				}
			}
			else if(cnt2%3==2){
				for (int i = 3; i <= cnt2;i++){
					sum2+=b[i]; 
				}
			}
			printf("2 %lld %lld\n",sum1,sum2);
			//cout << (sum1|sum2) << endl;
		}
		else{//第四类
			ll sum1=0;
			ll sum2=0;
			int w=cnt1+cnt2*2;
			if(w%3==1){
				for (int i = 2; i <= cnt1;i++){
					sum2+=a[i];
				}
				for (int i = 1; i <= cnt2;i++){
					sum2+=b[i];
				}
				sum1=a[1]+b[1];
				printf("2 %lld %lld\n",sum1,sum2);
			//	cout << (sum1|sum2) << endl;
			}
			else{
				for (int i = 1; i <= cnt1;i++){
					sum2+=a[i];
				}
				for (int i = 2; i <= cnt2;i++){
					sum2+=b[i];
				}
				sum1=a[1]+b[1];
				printf("2 %lld %lld\n",sum1,sum2);
			//	cout << (sum1|sum2) << endl;
			}
		}
	}
	return 0;
}