NKOJ --拓拓展展3--H

建议  Ctrl + A    观看。文中有隐蔽链接和白字

题目描述：

你的初始位置在 1 ，让你寻找出一条路径，能到达 n[i] 。跳跃方式：

                ​​​​​在这里

思路：

        Step 1:  

                 感觉和  P1088追牛​​​​​  很像。便想到了 bfs。

                对于当前宇宙 n，可以扩展出以下几个宇宙：

                        2 * n    ,    min(abs(n),abs(n-d))<=l ? n-d : 1    ,    n%3==1 ? (n-1)/3 : 0

                                PS：三目运算符中的1必然已经被搜过，即没有不能扩展。

                如果下标是负数又该怎么办呢？

                        第一种解法：偏移量

                                将所有下标同一加上一个正整数，使其全部都变成正数。访问时再减去那个正数即可。但是：

                                        对于 100% 的数据，满足 |  n[i]  | <= 10000000

                                 10000000+10000000=20000000 ，数组能存下。

                        ​​​​​​更优秀的解法：map（哈希）

                                如果你知道 map 这个玩意（毒瘤），请跳过这一段。

                                map， 即 STL 自带的哈希表。能以 int , double , string 类的元素为下标，并对其赋值 （ 值也可以是 int , double , string  当中的其中一个 ）。它包含在头文件

#include

里的。

                                食用方法：

                                        map< typename , typename >  name;

                                        第一个typename是填下标类型（ 注意没有 char 类 ），第二个typename是值得类型（可以是 char 类）。

                                        例如：

#include
#include

例如,样例中的 10：

n  : 1  2  4  8  16  13  10
fa : 1  1  2  4  8   16  13

访问时：
10 -> fa[10]=13 -> fa[13]=16 -> fa[16]=8 -> fa[8]=4 -> fa[4]=2 -> fa[2]=1 -> fa[1]=1

#include
#include

#include
#define int long long
using namespace std;

int q,d,l;
int n,cut;

void get_cut(int x)
{
	if(x==1)
	{
		return;
	}
	
	if(min(abs(x),abs(x+d))<=l)
	{
		get_cut(x+d);
		cut++;
		return;
	}
	
	if(x&1) get_cut(x*3+1);
	
	else get_cut(x/2);
	
	cut++;
	
	return;
}

void out(int x)
{
	if(x==1)
	{
		cout<>q>>d>>l;
	while(q--)
	{
		cin>>n;
		cut=0;
		
		get_cut(n);
		cout<