Gym 101503C Twisting the Number（思维+枚举）

题目大意：

有一个整数 $n$，其中$W(n)$表示 $n$ 的二进制循环的数的集合，比如说：
$n=11$ 二进制表示为 $1011$，循环一次得到：
$0111 ==> 7$
$1110 ==> 14$
$1101 ==> 13$
所以 $w(11)={7,11,13,14}$
现在给你一个 $n$， 找到一个 $P$ 使得 $w(1),w(2),...,w(P)$ 能够表示 $1-n$ 中的所有数，输出这个 $P$。

解题思路：

首先我们对于给定的 $n$，可以求出 $n$ 的二进制循环中的最小值，设为 $ans$，那么一定有 $P\in[ans,n]$，那么我们在写出 $n$ 的二进制表达式，对二进制中 $1$ 的位置进行一个枚举。举个例子：
设有 $n$ 的二进制表示为 $101001000$
那么我们只需要枚举 $101000111$，$100111111$ 这两个就可以了，因为别的数字都可以由比这两个小的得到，仔细看一下代码就懂了。

代码：

#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <map>
using namespace std;
typedef long long LL;
const LL INF = 2e18;
const int MAXN = 1e6+5;
const double PI = acos(-1);
const double eps = 1e-8;
const LL MOD = 1e9+7;
LL get1(string s){if(s[0] == '0') return INF;LL ans = 0;int len = s.length();for(int i=0; i<len; i++) if(s[i] == '1') ans += (1LL<<(len-1-i));return ans;
}
string get2(LL n){string s = "";while(n){s += ((n&1)+'0');n>>=1;}for(int i=0; i<s.length()/2; i++) swap(s[i],s[s.length()-i-1]);return s;
}
LL cal(LL n){string s = get2(n);string s1 = "";s1 += s[0];LL ans = n;int len = s.length();for(int i=1; i<len; i++){string s2 = s.substr(i);s2 += s1;ans = min(ans, get1(s2));s1 += s[i];}return ans;
}
int main(){LL n;while(cin>>n){LL ans = cal(n);string s = get2(n);int len = s.length();for(int i=1; i<len-1; i++){if(s[i] == '1'){string s1 = s.substr(0,i)+'0';string s2 = get2((1LL<<(len-i-1))-1);s1 += s2;LL tmp = cal(get1(s1));ans = max(ans, tmp);}}printf("%lld\n",ans);}return 0;
}