题解 CF1338C 【Perfect Triples】

ix35 · 2020-04-13 08:46:18 · 题解

红名了，纪念一下。

这题一开始看不出任何东西，于是写了下面这个程序打了个表：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int cnt,vis[MAXN];
int main () {
    for (int i=1;i<=10000;i++) {
        if (vis[i]) {continue;}
        for (int j=i+1;j<=10000;j++) {
            int flg=0;
            if (vis[j]) {continue;}
            for (int k=j+1;k<=10000;k++) {
                if (vis[k]) {continue;}
                if (i^j^k) {continue;}
                printf("%d:   %d %d %d\n",++cnt,i,j,k);
                vis[i]=vis[j]=vis[k]=1;
                flg=1;
                break;
            }
            if (flg) {break;}
        }
    }
    return 0;
}

表大概长这样（局部：

然后可以总结出如下规律:

2. 同一块内，b 的取值可以递归构造。每次将大块分成四小块，分别取第 1,3,4,2 小的值。

3. 同一块内，c 的取值可以递归构造。每次将大块分成四小块，分别取第 1,4,2,3 小的值。

于是我们先搞出 n 在哪一块，如果是 a 可以直接返回，如果是 b,c 就递归构造即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll calc2 (ll x,ll y) {
    if (x==1) {return 1;}
    else {
        ll t=x/4;
        if (y<=t) {return calc2(t,y);}
        else if (y<=2*t) {return calc2(t,y-t)+2*t;}
        else if (y<=3*t) {return calc2(t,y-2*t)+3*t;}
        else {return calc2(t,y-3*t)+t;}
    }
}
ll calc3 (ll x,ll y) {
    if (x==1) {return 1;}
    else {
        ll t=x/4;
        if (y<=t) {return calc3(t,y);}
        else if (y<=2*t) {return calc3(t,y-t)+3*t;}
        else if (y<=3*t) {return calc3(t,y-2*t)+t;}
        else {return calc3(t,y-3*t)+2*t;}
    }
}
ll t,n;
ll calc (ll n) {
    ll tmp=n%3;
    n=(n+2)/3;
    ll pos=0,cnt=0;
    while (pos+(1ll<<cnt)<n) {
        pos+=(1ll<<cnt);
        cnt+=2;
    }
    ll res=3*pos;
    if (tmp==1) {
        return res+(n-pos);
    } else if (tmp==2) {
        return res+(1ll<<cnt)+calc2(1ll<<cnt,n-pos);
    } else {
        return res+(1ll<<(cnt+1))+calc3(1ll<<cnt,n-pos);
    }
}
int main () {
    scanf("%lld",&t);
    for (int ii=1;ii<=t;ii++) {
        scanf("%lld",&n);
        printf("%lld\n",calc(n));
    }
    return 0;
}