CF-Round #633-div2-E题&div1C

CF-Round #633-div2-E题&div1C

E. Perfect Triples

传送门

这道题是关于异或运算，构造，模拟的题目 （打表找规律题）

题目大意：让你构造出一个无限的序列s，满足以下要求。
每次选出一个三元组（a, b, c)
1.其中的a, b, c是s中没有出现过的;
2.a, b, c满足字典序最小;
3. a ^ b ^ c = 0;

有t次询问，每次输入一个n值，问你序列的第n个数是多少。

根据样例：
我们可以打表得到序列：


这些数字都是一块一块出现的。
从1~3， 4 ~ 15， 16 ~ 63， 64 ~ …
这是关于4的运算。
每部分是4 ^ i ~ 4 ^(i + 1) - 1;(i从0开始）
而且每部分的第一个数，也就是a,是顺序递增的。

现在我们来找找a和b之间的关系
因为关系到异或和4，我们不妨转化为4进制观察（因为观察2进制没有探索出规律）：

我们观察四进制下的a,b的关系：
当a的某一位为0时，b的对应位为0
当a的某一位为1时，b的对应位为2
当a的某一位为2时，b的对应位为3
当a的某一位为3时，b的对应位为1
（打表代码在最后）

于是我们就可以开始啦~
我们把上面的数字看成n * 3的矩阵。
于是我们可以通过输入的n值获得这个数应该在矩阵的哪一行哪一列。
row = (n - 1) / 3 + 1;
col = (n - 1) % 3;
row对应的是第几行；col对应的是第几个数（因为是取模操作。对应的是从0开始）

solve1（）解决第row行的第1个数。
因为每个部分的第一行的第一个数都是4的次幂。而且每一部分的行数也是4的次幂。
所以先看看当前行是哪个部分的。然后在算上偏移值即可得到a。

solve2()解决的就是由a的四进制找到b的四进制直接转化为十进制的过程。

代码部分：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
int a[4] = {0, 2, 3, 1};

ll solve1(ll x)
{
	ll sum = 1;
	while (x > sum)
	{
		x -= sum;
		sum <<= 2;
	}
	return x + sum - 1;
}

ll solve2(ll x)
{
	ll ans = 0;
	int k = (int)log2(x) + 1;
	for (int i = 0; i <= k; i += 2)
	{
		ans += (1ll << i) * a[(x >> i) % 4];
	}
	return ans;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		scanf ("%I64d", &n);
		ll row = (n - 1) / 3 + 1;
		ll col = (n - 1) % 3;
		ll num1 = solve1(row);
		ll num2 = solve2(num1);	
		ll num3 = num1 ^ num2;
		if (!col)
		{
			cout << num1 << endl;
		}
		else if (col == 1)
		{
			cout << num2 << endl;
		}
		else
		{
			cout << num3 << endl;
		}
	}
	return 0;
}

打表代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int vis[N];

void tobinary(int n)
{
	bitset<6> v(n);
	cout << v << " ";
}

void toquater(int n)
{
	string s;
	for (int i = 1; i <= 5; i++)
	{
		s += n % 4 + '0';
		n >>= 2;
	}
	reverse(s.begin(), s.end());
	cout << s << " ";
}

int main()
{
	while (1)
	{
		for (int i = 1; i <= 1e3; i++)
		{
			if (!vis[i])
			{
				for (int j = i + 1; j <= 1e3; j++)
				{
					if (!vis[j] && !vis[i ^ j])
					{
						vis[i] = vis[j] = vis[i ^ j] = 1;
						cout << i << " " << j << " " << (i ^ j) << endl;
						toquater(i);
						toquater(j);
						toquater(i ^ j);
						getchar();
						break;
					}
				}
			}
		}
	}
	return 0;
}