若#1T了又不愿意放弃dfs的可看看
查看原帖
若#1T了又不愿意放弃dfs的可看看
714500
Tennif_hxz楼主2023/10/17 15:56

如题

这个不是题解,仅供娱乐 ,请勿投诉QwQ.


注:该帖仅是提供给那些想用dfs伪AC后再写正解的人看的(比如有的就想用5、6种方法AC,只有dfs AC不了就很难受),仅供娱乐。如果用本方法AC后不再订正,我认为热心的谷友会造新的Hack数据把这些人的AC给hack掉,所以我再次强调:本帖仅供娱乐,请各位谷友用正解AC

实际上,我们有一个投机取巧的思路:

因为只是被T了一个点,说明人家是针对dfs个卡的。那么就要尽量规避这个卡点。(所以明眼人也应该明白这不是正解,更不是题解)

首先,毛估估是出数据的人让ans从大变小使要搜索遍所有情况。那么就倒着走,从B搜索到A。

然后,代码实现:

// 实测:dfs被Hack了;不过是正dfs;可以反着来试试;
int n,A,B;int mn=210;
struct elevator{
	int num;
	vector<int> from_upper;
	vector</*请自主填空*/> /*请自主填空*/;
	bool vis=0;
}v[210];

for(int i=1;i<=n;i++) v[i].num=read();
for(int i=1;i<=n;i++) {
	if(i-v[i].num>=1)/*请自主填空*/.push_back(i);
	/*请自主填空*/;
	}

首先我们记录4个值
一个是它本身可以移动的距离。
然后是可以从它头上到它这里和从它楼下来到这里的楼层
(实际上只要一个vector就可以了,记录可以到它那里的楼层,方便理解才这么写)
vis表示有没被访问过;

void dfs(int t,int p){
	if(t>mn) return; if(p==A) mn=t;//特判
	v[/*请自主填空*/].vis=/*请自主填空*/;
	for(auto i:/*请自主填空*/) if(/*请自主填空*/) dfs(t+1,i);
	/*请自主填空*/
	v[/*请自主填空*/].vis=/*请自主填空*/;
}

然后正常搜索;

不敢贴出完整代码,本来提供思路就已经在违规的边缘疯狂试探了,再贴完全地触犯了社区规则就玩脱了哈[挠头]。


我弱弱的补充两句:
1.因为这不是正解,所以应该算不上题解(雾)
2.同时,我又不敢说这思路是我独创的,但的确在比赛时一下子写不出正确代码是,可以这么考虑一下,说不定这种方法出题人忘记卡了
3.再而,请各位遵守以下共识约定:
····1.本思路AC后,用正解订正一遍;
····2.我想不到,烦请谷友补充\

2023/10/17 15:56
加载中...