【2022年省赛B组】试题J: 砍竹子

题解

每次使用魔法砍竹子，可以使得柱子高度$H$变成$\Bigg \lfloor \sqrt{\big \lfloor\dfrac{H}{2} \big \rfloor + 1}\Bigg \rfloor$。可以发现，砍竹子的次数在log级别以下。

当高度达到上限$10^{18}$时，最多只需要砍6次，高度即可变为1。 那么对于每棵竹子，可以暴力求出每次砍完之后的高度。$dp[i][j]$表示第$i$棵竹子，倒数第$j$次砍之后的高度。 那么我们最开始可以求出所有的竹子单独使用魔法的次数$ans$，并且同时记录$dp$数组，即每棵树每次砍完后的高度。 对于相邻的低$i - 1$和第$i$棵竹子，如果存在高度相同，则可以一并砍掉，此时将$ans$减1即可。 遍历所有$dp[i - 1]$和$dp[i]$​,存在相同高度则答案减1，最终则是所有竹子变成1的最少魔法使用次数。

提交代码

#include<bits/stdc++.h>
typedef long long LL;
const int N = 2e5 + 10;
std::vector<LL> dp[N];

void solve()
{
	int ans = 0;
	int n; std::cin >> n;
	
	for(int i = 0; i < n; i++)
	{
		long double h; std::cin >> h;
		while(h > 1)
		{
			dp[i].push_back(h);
			h = std::floor(std::sqrt(std::floor(0.5 * h) + 1));
			ans++;
		}
		std::sort(dp[i].begin(), dp[i].end());
	}
	for(int len = 0; len < 6; len++)
	{
		for(int i = n - 1; i > 0; i--)
		{
			if(dp[i].size() > len && dp[i - 1].size() > len && dp[i][len] == dp[i - 1][len])
			{
				ans--;
			}
		}
	}
	std::cout << ans << "\n";
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}