NKOJ --拓拓展展3--H

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

题目描述：

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

在这里![](https://cdn.luogu.com.cn/upload/image_hosting/c436ohub.png)

思路：

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

using namespace std;//食用 map 时要打这一句

map mp;//定义了一个以 int 类为下标，值也为 int 类的一个map，名字叫做 mp 

int main()
{
	mp[666]=1;//把 666 标记为 1 
	mp[1223]=-3;//把 1223 标记为 -3
	mp[-100000000]=-111111111;//把 -100000000 标记为 -111111111
	cout< 
更多关于 map 的知识 ， 请参考以下几篇文章： 
                        这里      和   那里 
那如何保存路径呢？？？ 
        我们可以参照单链表的写法（或并查集），设一个 fa 数组。对于每一个扩展出来的数，在 fa 中将其对应的值标记为那一个数。 
例如,样例中的 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 
然后再套一个 vector 或 queue 即可。 
如果您不知道 vector ，请使用 queue 或参考这个 

于是，0 分的代码出炉啦！！！： 
#include
#include
#include
#include
#include

using namespace std;

int q,d,l,p[101],k;
vector s[101];
map mp;

queue Q,tmp;
map st,fa;

void bfs()
{
	fa[1]=1;
	st[1]=1;
	Q.push(1);tmp.push(0);

	while(!Q.empty())
	{
		int t=Q.front(),T=tmp.front();
		Q.pop();tmp.pop();

		if(!st[t-d] && min(abs(t),abs(t-d))<=l)
		{
			fa[t-d]=t;
			st[t-d]=1;
			Q.push(t-d);
			tmp.push(T+1);
		}
		if(!st[2*t])
		{
			fa[t+t]=t;
			st[t+t]=1;
			Q.push(t+t);
			tmp.push(T+1);
		}
		if(t%3==1 && !st[(t-1)/3])
		{
			fa[(t-1)/3]=t;
			st[(t-1)/3]=1;
			Q.push((t-1)/3);
			tmp.push(T+1);
		}

		if(mp[t]==1)
		{
			int tt=t;
//			cout<<"###"<>q>>d>>l;
	for(int i=1; i<=q; i++)
	{
		int x;
		cin>>x;
		mp[x]=1;
		p[i]=x;
	}

	bfs();
	
	for(int i=1; i<=q; i++)
	{
		cout<=0; j--) cout< 
hack: 
 
 20 100000 1000
 -401
 -714
 123
 425
 428
 705
 413
 425
 -606
 224
 58
 -449
 504
 558
 870
 568
 -8
 391
 -887
 -360 
 
 原因：直接爆掉了！！！ 
于是，我们只能去寻找新出路！！！ 

 
 
 
 
                                                  请至少想五分钟再往下看！！！ 
 
 
 
 

STEP 2: 
我们可以考虑倒着退回去。 
将式子变形后： 
 
 n*2  ->  n/2    ,    (n-1)/3  ->  n*3+1 
 
这不是 冰雹猜想吗？？？   可参考洛谷 P5727 
于是，有死循环的代码出来啦！！！： 
#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< 
 这下怎么办？？？ 
 

 
 
 
 
                                                  请至少想五分钟再往下看！！！ 
 
 
 
 
 

 经过对一堆数据的测试，我发现了一个玄学现象： 
        负数内部会出现死循环，并且会经过0，-1，-5，-17。 
于是，特判一下就行了。 
把   
 && (x==0 || x==-1 || x==-5 || x==-17) 
加在第二个  if  里面。 
 

 
 
 
                                                             想要代码？？？没门！！！ 
 
 

                                                                THE END

NKOJ --拓拓展展3--H

C/C++/C#相关栏目本月热门文章