【2024蓝桥杯/C++/B组/传送阵】

题目

问题代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int n;
int porter[N];
int ans;
int sign[N];
bool used;void dfs(int now, int cnt)
{if(sign[now] && used){ans = max(ans, cnt);return;}if(!sign[now]){cnt++, sign[now] = 1; dfs(porter[now], cnt);}if(!used){used = true;dfs(now-1, cnt);dfs(now+1, cnt);used = false;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n ; i++) cin >> porter[i];for(int i = 1; i <= n; i++) dfs(i, 0);cout << ans;return 0;
}

分析

修改

我想了一下，可能是由于回溯的问题。因为我定的是全局变量sign和used，所以回溯应该要逐个回溯。而且我还忘了边界限制。修改如下

#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int n;
int porter[N];
int ans;
int sign[N];
bool used;void dfs(int now, int cnt)
{if(sign[now] && used){ans = max(ans, cnt);return;}if(!sign[now]){cnt++, sign[now] = 1; dfs(porter[now], cnt);sign[now] = 0;}if(!used){sign[now] = 1;used = true;if(now-1 >= 1) dfs(now-1, cnt);//used = false;//sign[now] = 0;sign[now] = 1;used = true;if(now+1 <= n) dfs(now+1, cnt);used = false;sign[now] = 0;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n ; i++) cin >> porter[i];for(int i = 1; i <= n; i++) dfs(i, 0);cout << ans;return 0;
}

再分析

可以看出原本不过的样例过了。说明修改可能正确了，但是因此也增加了时间消耗。