背景

怪盜基德 VS OIBH
第三話

描述

怪盜基德第三次來到熟悉的OIBH總部。屢屢失敗的OIBH這次看守的是The Eye of Moon。還是那個
房間，還是那扇門，不同的是OIBH對密碼鎖進行了改進。這次屏幕上只顯示一個數n(基德：這是
改進了還是退化了？）。

密碼生成方法：設集合A中A={1,2,...,n}，B為A子集。對于B中任意一個元素x，2x均不在集合B中。

B中元素數目最大值即為密碼。

格式

輸入格式

一行，一個整數n(1<=n<=maxlongint)

輸出格式

只有一個整數m，表示B中元素最大值

樣例1

樣例輸入1

100

Copy

樣例輸出1

67

Copy

限制

OIBH在6s內就會發現，所以每個點只有1s時間給你

提示

簡單數學題哦~~

來源

From 瑪維-影之歌；
感謝vijos的朋友提供數據

暴力可以過4個點，當我再加大數組的時候就炸了。

然后，分治。。。

知道A數組的長度，從后往前取

當長度為奇數是取后半段加上中間的數

然后再取1/4的長度，意思是剩下的二分之一中，后四分之一是不能取得了

當長度為0或1時就加上然后結束。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 10000000
long long n,m,l,tot;
void q(long long x)
{
    if(x<=1)
    {
        tot+=x;
        return ;
    }
    if(x%2==1)
    {
        tot+=x/2+1;
        q(x/4);
    }
    else if(x%2==0)
    {
        tot+=x/2;
        q(x/4);
    }
}
int main()
{
    scanf("%d",&n);
    q(n);
    printf("%d",tot);
    return 0;
}

總結

以上是生活随笔為你收集整理的Vijos 1385盗窃-月之眼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。