善用STL

题1. 重排后为2的幂

题目描述

为了平衡卷王对课程压力的影响，一些反卷斗士自发地组成了反卷者联盟。在反卷者联盟中，每一个反卷斗士都是二进制天选之子。为了防止卷王发现潜伏在其中的反卷斗士，反卷斗士之间有自己独特的相互验证方式。具体验证方式为：如果一个学生的学工号（一个整数）的各个数字经过重新排序后，并且前导数字不能为0，得到的新数字是2的幂次方，则这个学生就是反卷斗士，这也是二进制天选之子名字的由来。现在你是反卷者联盟的一员，给你一个整数n，即学生的学工号，你需要验证这个学生是否是反卷斗士。如果是则输出1，否则输出0。

输入数据说明：

• 1≤n≤109

样例

输入：10
输出：0

输入：1
输出：1

答案

#include <iostream>
#include <algorithm>
using namespace std;
 
bool check(int n) { // 判断n是否是2的幂次方
    return (n & (n - 1)) == 0;
}
 
int main() {
    int n;
    cin >> n;
    string str = to_string(n); // 将整数转换为字符串方便排序
    sort(str.begin(), str.end()); // 排序
    do {
        if (str[0] == '0') continue; // 如果排序后的数字以0开头，直接跳过
        int num = stoi(str); // 将字符串转换为整数
        if (check(num)) { // 判断是否是2的幂次方
            cout << 1 << endl;
            return 0;
        }
    } while (next_permutation(str.begin(), str.end())); // 生成下一个排列
    cout << 0 << endl;
    return 0;
}

使用的STL有：

• string 类
• sort() 函数，保证str中的字母按照字典顺序排列，为使用next_permutation() 函数准备
• next_permutation(beg, end)，将当前序列转换称下一个排列，序列必须已经按照字典序从小到大排序，否则该函数无法正常工作。