題目

小b有一個數n，現在她想把n的每一位重排列，使得得到的結果為2的冪次。

請問小b能得到2的冪次嗎？

注意重排列后不允許有前導0。

樣例解釋：46重排列成64，為2^6。

輸入

輸入一個數N，其中1≤N≤10^9

輸出

滿足條件，輸出“true”；
不滿足，則輸出“false”。

輸入樣例

46

輸出樣例

true

思路：提前將 2^i 打好表，然后對于數字 n 去分解每一位，再對所有位進行全排列，于表中的數字進行比較即可，要注意的是，由于 n 最大到 1e9，打表需要使用 map

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 4000000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;int bit[15],tot; map<int,int> mp; void init(){for(int i=0; i<31; ++i)mp[1<<i]=1; } int main() {init();int n;scanf("%d",&n);while(n) {//分解每一位bit[tot++]=n%10;n/=10;}sort(bit,bit+tot);bool flag=false;do {//對所有位數全排列int sum=0;if(bit[0]==0)continue;for(int i=0; i<tot; ++i)sum=sum*10+bit[i];if(mp[sum]==1) {//逐個判斷每一位flag=true;break;}} while(next_permutation(bit,bit+tot));if(flag)puts("true");elseputs("false");return 0; }

?

總結

以上是生活随笔為你收集整理的重排列得到2的幂（51Nod-2515）的全部內容，希望文章能夠幫你解決所遇到的問題。

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