牛客round94E

 原题链接：E-小苯的数字操作_牛客周赛 Round 94

题目背景：

        集合中初始有一个元素 n 可以对集合进行 k 轮操作，每次操作可以将集合中的元素除以 2（下取整）或乘 2 并将元素添加到集合中，请问最后集合中有几个元素。

思路：

        通过模拟过程不难发现以下规律：

                1.如果 n 为偶数，我们对其除以 2 后再乘 2 ，可以发现是没有贡献的。

                二进制：1100 -> 110 -> 1100

                2.如果 n 为奇数，我们对其除以 2 后再乘 2，可以发现有一次贡献。

                二进制：1101 -> 110 -> 1100

        可以假设 k = 4，可以得到几种枚举过程：x x x x，/ x x x，/ / x x，/ / / x

        如果 n 为偶数第一种枚举会得到四点贡献，既每一次都会得到一个新数字；第二种枚举会得到一点贡献，既第一次除以 2 的时候；以此类推，后面两种的贡献为 2，3。

        如果 n 为奇数第一种枚举会得到四点贡献，既每一次都会得到一个新数字；第二种枚举会得到四点贡献，及每一次运算时（因为初始时 n 为奇数，除以 2 以后变为一个偶数，后面每一次运算都是一种新的值，既 1101 -> 110 -> 1100 -> 11000 -> 110000）。

        通过以上模拟可发现：如果当前 n 为偶数那么会得到 1 个新值，如果当前为奇数那么会得到k点贡献（剩余轮数）。

        特判：如果 n = 1,他的贡献是 1，因为 0 后面的数字不能继续除了。

        为什么不乘完再除呢：如果当前 n 为奇数，乘 2 变为偶数，再除以 2 又变为原来的 n ，可以发现这样没有意义。

数据范围：

        1 <= t <= 1e4，1 <= n，k <= 1e9。

ac代码： 

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}void solve()
{int n, k;cin >> n >> k;ll ans = k + 1;while (n > 0){if (!k)break;if (n & 1){if (n > 1)ans += k;else++ans;}else++ans;n >>= 1;k--;}cout << ans << endl;
}int main()
{ioscc;int T;cin >> T;while (T--)solve();return 0;
}