---恢复内容开始---
我是一个刚入坑的新人，没有老师指导，所以任何来看我的文章的网友都是我的老师，若文章有错误，务必指出！
我在做这道题时，看了很多很多很多网友码，现在来总结一下。
题目大体意思：
输入一个数x（该数范围是1 ~ 1e6），将此数通过一定的操作（操作步数不多于40）转变成另一个数，最后得到的数字一定是处于（2^n-1 ， n >= 0 && n <= 30）这样的一个整数集合里。
操作A：任意选择一个n，算出（2^n - 1），并将该数与x进行异或运算，将结果值赋值给x。
操作B：将x进行自身+1运算。
规定操作的奇数步数进行操作A，偶数进行操作B。
打印总操作步数，和奇数步数对应指数n
思路：
判断x是不是等于2^n-1，我们可以设x = 2^n - 1，将-1左移，得到x + 1 = 2 ^ n。所以只要判断x+1是不是等于2^n即可
关于二进制的一些特点，任何在指数函数2^n上的数，换成二进制数都是，最高位为1，其余位为0，如2 ^ 0 = 1, 2 ^ 1 = 10, 2 ^ 2 = 100, 2 ^ 3 = 1000。
若在此数基础上减去一个1即：2 ^ n - 1，换成二进制数为n个1，如 2 ^ 3 - 1 = 111, 2 ^ 4 = 1111, 2 ^ 5 = 11111。
根据以上的特点，即可解出此题，判断x + 1 是否等于2^n，可进行1 << i （ i >=0 && i <= 30 因为2^30 > 1e9 ),该左移位运算可以看成 1 乘以 i 个 2。
如何选择一个合适的指数n与x进行异或运算：（把x换成二进制数来看）每次进行异或运算应该依次把高位的0变成1同时把低位的1变成0，我们可以把x进行右移位运算并记录移位次数m，之后判断x是不是属于集合2^n-1的数，若属于则m即为我们要找的指数n
|
#include <cstdio>
#include <iostream> #include <vector> using namespace std;
vector<int> T;
bool judge( int x )
{ x++; for( int i = 0; i <= 30; i++ ) { if( x == ( 1 << i ) ) { return true; } } return false; } int bcnt( int x )
{ for( int i = 0; i <= 30; i++ ) { if( judge( x >> i ) ) { return i; }
} return -1; } int main()
{ int in; while( scanf("%d", &in) == 1 ) { T.clear(); int cnt = 0; while( !judge( in ) ) { cnt++; if( cnt % 2 == 1 ) { int b; b = bcnt( in ); T.push_back( b ); in = in ^ ( ( 1 << b ) - 1 ); } else { in++; } } if( cnt == 0 ) { cout << cnt << endl; } else { cout << cnt << endl; for( int i = 0; i < T.size(); i++ ) { cout << T[i] << " "; } printf("\n"); } } return 0; } |
|
---恢复内容结束---
Neko Performs Cat Furrier Transform
原文：https://www.cnblogs.com/Naive-and-pure/p/10816288.html