解题思路: 一层循环线性遍历,vis用于去重,mp用于局部去重
注意事项: 目前 dotcpp 官方测评数据存在问题
参考代码:
错解(目前可通过 dotcpp 所有测试样例)
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define int long long using namespace std; const int MAXN=4e4+5; int n,c[MAXN],ans; unordered_map<int,bool> vis; //全局已走过的点 unordered_map<int,bool> mp; //本次搜索已走过的点 unordered_map<int,bool> valSet; //本次搜索已获得的c的集合 void dfs(int start){ // cout<<start<<"\n"; valSet[start]=true; mp[start]=true; vis[start]=true; int next=start+c[start]; if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n"; dfs(next); } next=2*start; if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n"; dfs(next); } } signed main(){ IOS; cin>>n; for(int i=1;i<=n;++i) cin>>c[i]; for(int i=1;i<=n;++i){ if(vis.find(i) == vis.end()) { mp.clear(); valSet.clear(); dfs(i); ans=max(ans,(int )valSet.size()); } } cout<<ans<<endl; return 0; }
正解(目前无法通过 dotcpp 测试样例)
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define int long long using namespace std; const int MAXN=4e4+5; int n,c[MAXN],ans; unordered_map<int,bool> vis; //全局已走过的点 unordered_map<int,bool> mp; //本次搜索已走过的点 unordered_map<int,bool> valSet; //本次搜索已获得的c的集合 void dfs(int start){ // cout<<start<<"\n"; valSet[c[start]]=true; mp[start]=true; vis[start]=true; int next=start+c[start]; if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n"; dfs(next); } next=2*start; if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n"; dfs(next); } } signed main(){ IOS; cin>>n; for(int i=1;i<=n;++i) cin>>c[i]; for(int i=1;i<=n;++i){ if(vis.find(i) == vis.end()) { mp.clear(); valSet.clear(); dfs(i); ans=max(ans,(int )valSet.size()); } } cout<<ans<<endl; return 0; }
0.0分
1 人评分
【出圈】 (C++代码)(典型的约瑟夫环——链表解决)浏览:1228 |
C二级辅导-统计字符 (C语言代码)浏览:552 |
陶陶摘苹果 (C语言代码)浏览:1615 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:528 |
C语言程序设计教程(第三版)课后习题8.1 (Java代码)浏览:785 |
【回文数(二)】 (C++代码)浏览:884 |
C语言训练-最大数问题 (C语言代码)浏览:636 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:496 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1644 |
【亲和数】 (C语言代码)浏览:876 |