Neko Performs Cat Furrier Transform

time limit per test 1 second memory limit per test 256 megabytes

题目链接http://codeforces.com/problemset/problem/1152/B

---

emmm，题目大意：给你一个数n，让你对他进行t次操作使得它的值为2^x-1，你第一次只能将它异或2^x-1，第二次只能对它+1，第三次…让你求t，并输出每个x；

题目有点想法，如果对异或不太熟悉的人可能有点迷，但实际上我们可以通过第一个样例来看：

首先我们将它（39）化为二进制：100111 异或会使得相同的变为0，不相同的变为1，而2^x-1化为二进制则是1111111…（x-1个）。也就是说我们异或的时候会使得x-1位及以下的反转。

那么题目的意思就是让你在二进制的数据下降n的每位变成1。

那么也就好做了，我们对n从高位一位位地找下去，如果该位置为1，则继续找，否则我们就将它异或2ⁱ⁺¹-1（i为二进制下的第i位）。至于第二个操作就不用管了，他是固定的操作。

当然我是先将它异或了一个2^p-1（p为n的二进制下的长度）。这个完全可以删掉。。

以下是AC代码：

#include <bits/stdc++.h> using namespace std; int ok(int x) { while (x){ if (x%2==0) return 0; x>>=1; } return 1; } int a[60],b[60]; int pow(int x,int y) { int ans=1; for (int i=1; i<=y; i++) ans*=x; return ans; } int main() { int n; scanf ("%d",&n); if (ok(n)){ printf ("0\n"); return 0; } else { int ans=0,nb=0; while (!ok(n)){ ans++; int cp=n,op=0; if (ans&1) { if (ans==1){ while (cp) cp>>=1,op++; n^=pow(2,op)-1; a[++nb]=op; } else { int sb; memset(b,0,sizeof(b)); while (cp) b[op++]=cp%2,cp>>=1; while (!b[op]) op--; for (int i=op; i>=0; i--) if (!b[i]){ sb=i+1; break; } n^=pow(2,sb)-1; a[++nb]=sb; } } else n++; } printf ("%d\n",ans); if (ans&1) for (int i=1; i<=ans/2+1; i++) printf ("%d ",a[i]); else for (int i=1; i<=ans/2; i++) printf ("%d ",a[i]); printf ("\n"); } return 0; }