Codeforces 988D Points and Powers of Two ( 思维 || 二的幂特点 )

题目链接

题意 : 给出坐标轴上的 n 个点的横坐标，要你选出最多的点，使得这些点两两距离是二的幂 ( 特殊情况 : 选出的集合只有一个点也满足条件 )

分析 :

官方题解已经说的很好了

最关键是是判断选出的集合元素数量肯定不可能大于 3

简单翻译一下题解就是

假设现有答案集合元素数量为 4 ，且令其为 a、b、c、d ( a < b < c < d )

令 a、b 间距为 dist(a, b) = 2^k

令 b、c 间距为 dist(b, c) = 2^l

则可得出 dist(a, c) = dist(a, b) + dist(b, c) = 2^k + 2^l = 2^m

根据二的幂相加的性质，可以得出 k == l ( !!!!! 这个思想很重要 !!!!!! )

对于 a、b、c 有如上关系，所以对于 b、c、d 也有同样的关系

所以有 dist(a, b) = dist(b, c) = dist(c, d) = 2^k

故有 dist(a, d) = 3 * 2^k 这个因为有因子 3 的存在，所以定不是二的幂

故推出答案集元素数量为 4 是不可行的，由此可以推广出大于 4 的也都不可行

所以只要枚举二的幂，然后对于每一个点去检查其加上或者减去当前枚举的二的幂的元素是否存在

若都存在，那么肯定存在答案集合大小为 3 的解。若只存在一个，则存在答案集合大小为 2 的解。

若枚举完了都没有的话，那么答案集合大小只能为 1 ，此时随便输出一个元素即可。

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long

#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scl(i) scanf("%lld", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))

#define fir first
#define sec second
#define ins(i) insert(i)
#define pb(i) push_back(i)
#define pii pair<int, int>
#define mk(i, j) make_pair(i, j)
#define all(i) i.begin(), i.end()
#define pll pair<long long, long long>

#define _TIME 0
#define _INPUT 0
#define _OUTPUT 0
clock_t START, END;
void __stTIME();
void __enTIME();
void __IOPUT();
using namespace std;
;
LL arr[maxn];

int main(void){__stTIME();__IOPUT();

    set<LL> s;
    int n;
    sci(n);

    ; i<=n; i++){
        scIl(arr[i]);
        s.ins(arr[i]);
    }

    LL ans1, ans2, ans3;
    bool _3 = false;
    bool _2 = false;
    ; i<=; i++){
        ; j<=n; j++){
            if(s.count(arr[j]+(1LL<<i))){
                if(!_2){
                    _2 = true;
                    ans1 = arr[j];
                    ans2 = arr[j]+(1LL<<i);
                }
                if(s.count(arr[j]-(1LL<<i))){
                    if(!_3){
                        _3 = true;
                        ans1 = arr[j]-(1LL<<i);
                        ans2 = arr[j];
                        ans3 = arr[j]+(1LL<<i);
                    }
                }
            }
            if(_3) break;
        }
        if(_3) break;
    }

    if(_3){
        puts(");
        return !printf("%I64d %I64d %I64d\n", ans1, ans2, ans3);
    }

    if(_2){
        puts(");
        return !printf("%I64d %I64d\n", ans1, ans2);
    }

    printf(]);

__enTIME();;}

void __stTIME()
{
    #if _TIME
        START = clock();
    #endif
}

void __enTIME()
{
    #if _TIME
        END = clock();
        cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl;
    #endif
}

void __IOPUT()
{
    #if _INPUT
        freopen("in.txt", "r", stdin);
    #endif
    #if _OUTPUT
        freopen("out.txt", "w", stdout);
    #endif
}

巴特西

Codeforces 988D Points and Powers of Two ( 思维 || 二的幂特点 )

最新文章

热门文章