C. Divisor Chain

原创 于 2023-08-30 22:21:01 发布 · 粉丝可见 · 432 阅读 · 1 · 1 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132591614

题目：

样例：

cobol<br/>3<br/>3<br/>5<br/>14<br/>

3 3 2 1 4 5 4 2 1 6 14 12 6 3 2 1

题意：

输入  x  ，使得  x 一直减某个数值 一直减到 1，所减的这个数值不能出现两次，输出该过程 x 的变化情况。

思路：

我们可以反过来想，使得 1 累加到 x ，所累加的这个中间数值不能出现两次，其次我们可以利用 倍增的关系，这样可以使得 所累加的这个中间数值不会出现两次，其次，当我们倍增的时候，肯定会到达某个峰值 使得恰好越过了 目标 x ，所以我们也要注意往回退。

代码详解如下：

#include <iostream>
#include <stack>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	int x;
	cin >> x;
	stack<int>ans;	// 逆向输出
	int now = 1;	// 当前数值
	int add = 1;	// 添加值
	ans.push(1);	// 添加起点值
	do
	{
		if(now + add <= x)
		{
			now += add;	// now 开始 添加中间值
			add <<= 1;	// add  添加值开始倍增
			ans.push(now);	// 添加变化情况
		}else
		{
			// 到达了某个峰值，添加值往回退
			add >>= 1;
		}	
	}while(now != x);
	
	// 输出变化情况
	cout << ans.size() << endl;
	while(ans.size())
	{
		cout << ans.top() << ' ';
		ans.pop();
	}
	cout << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：