题目链接：点击查看

题目大意：序列 s 是一个无限数列，现在给出构造方法：

选择三个数 a b c ，将其依次加到序列 s 的最后面，三个数需要满足：

a b c 在序列 s 中均未出现过

a b c 是字典序最小的数列

a ^ b ^ c = 0

现在给出一个 n ( <= 1e16 ) ，求出数列的第 n 项

题目分析：乍一看可能没什么思路，不过看起来可以打表，于是打表观察一下，打表代码放在最后

打出表后可以发现，以 a b c 为整体的数对被分成了好几大段，每一段的长度分别为 1,4,16,64....4^n，其中在每一大段中，a 都是依次增大的，这是一个比较明显的规律

因为这是对于异或的操作，所以将所有数都转换为二进制再看一看，会发现 b 和 a 有着某种微妙的关系，仔细观察观察或者大胆猜想一下，可以知道这个与四进制有关

将所有数转换为四进制后，就能看出 a 与 b 其中的相同位上：

a == 0 时 b =0

a == 1 时 b = 2

a == 2 时 b = 3

a == 3 时 b = 1

这样就能在知道 n 的基础上，求出第 n 个数的行与列的坐标，然后求出 a 和 b ，根据 a^b^c=0，得到 c=a^b，这样就能求出答案了

代码：

AC代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int b[]={0,2,3,1};LL get_num1(LL x) {LL base=1;while(base<x){x-=base;base<<=2;}return base+x-1; }LL get_num2(LL x) {LL num1=get_num1(x);LL ans=0;for(int i=0;i<=60;i+=2)ans+=(1LL<<i)*b[(num1>>i)%4];return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL n;scanf("%lld",&n);LL row=(n-1)/3+1;int col=(n-1)%3;LL num1=get_num1(row);LL num2=get_num2(row);LL num3=num1^num2;if(col==0)printf("%lld\n",num1);else if(col==1)printf("%lld\n",num2);elseprintf("%lld\n",num3);}return 0; }

打表代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;bool vis[N];void print(int num)//输出四进制 {string ans;for(int i=1;i<=5;i++){ans+=to_string(num%4);num/=4;}reverse(ans.begin(),ans.end());cout<<ans<<' '; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);for(int k=1;k<=100;k++){for(int i=1;i<=1000;i++){if(!vis[i]){for(int j=i+1;j<=1000;j++){if(!vis[j]&&!vis[i^j]){vis[i]=vis[j]=vis[i^j]=true;printf("%d %d %d ",i,j,i^j);print(i),print(j),print(i^j);puts("");goto end;}}}}end:;}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1339E Perfect Triples(打表找规律)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。