当前位置: 首页> 房产> 家装 > 简历制作专业模板_国内软件开发培训机构_百度seo推广怎么收费_淘宝站外引流推广方法

简历制作专业模板_国内软件开发培训机构_百度seo推广怎么收费_淘宝站外引流推广方法

时间:2025/7/11 15:38:09来源:https://blog.csdn.net/theskyinblue/article/details/147195829 浏览次数:0次
简历制作专业模板_国内软件开发培训机构_百度seo推广怎么收费_淘宝站外引流推广方法

补题链接
在这里插入图片描述

看网上题解很少,来写一份,这题个人觉得思维难度不是特别大,难度主要在于代码准确度,首先将问题转化成 x x x f ( x ) f(x) f(x) 连边,这一步转化应该是比较容易想到的,通过手模样例,会有类似的灵感,那么 n n n 个点 , n n n 条边,会构成基环树森林,因为图没有保证连通所以会有多棵基环树,并且还会有自环(虽然这是trivial的)
然后我们考虑如何计算答案,题解中给出如下条件
在这里插入图片描述
将第二个条件转化成实际意义就是,两个点都需要通过移动进入环内并且,二者在环内的路径之差是环长的倍数,也就是最终会落在同一点,了解完需要的条件后我们需要计算答案,对于第二种条件,我们只关心能否走进环,并且路径差是环长倍数。所以我们对于相同环的长度进行合并处理,注意到环长最多只有 n \sqrt{n } n 种(通过 ( 1 + 2 + 3 + . . . . + x ) = n (1+2+3+....+x)=n (1+2+3+....+x)=n 推导出来的),将环上的点的深度定义为 0 0 0 , 环外面的点的深度依次递增,统计每个环长深度小于等于 1 1 1 的点有多少, 深度小于等于 2 2 2 的点有多少,这样子做下去即可

有多颗基环树,我们怎么知道每个环长是多少呢?我们可以先找出环上的点,对环上的点进行 B F S BFS BFS,就可以知道环长.
那么我们如何知道深度呢,对环上的点跑 D F S DFS DFS 即可,相信大家都会
我们如何求出深度小于等于 d d d 的点有多少个呢?我们可以先求出对于每个环长,每个深度的点有多少个,再进行前缀和即可。

至此,所有的步骤已经清楚,我们先进行连边,同时建立反图,在正图上跑拓扑排序,找出所有环,对每个环进行深搜,求出所有环外点的深度,求出每个环长的深度数组并求前缀和,回答每个询问即可

同时,还有一些细节,如何是一整个大环,环外没有点如何,我们可以单独记录每个环长的数量,对于环内的贡献,用环长成数量即可

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<execution>
using namespace std;
using i64 = long long;
using i128 = __int128;constexpr int maxn = 1e5+10;
vector<int> g[maxn],rg[maxn];
vector<int> hc_dep[maxn];//对于每种环长算不超过d的点有多少,vector<int> 开桶,求前缀和
vector<int> hc;
int n,query,f[maxn],in[maxn],hc_num[maxn];
bool vis[maxn],vis2[maxn],vist[maxn];//是不是在环上,BFS有没有走过,dfs中有没有走过
bool in_tuopu[maxn];
void dfs(int x,int fa,int depth,int& hc_len){vist[x]=1;if(depth>0) hc_dep[hc_len].emplace_back(depth);for(int &y:rg[x]){//反图跑链长if(y==fa||vist[y]==1) continue;dfs(y,x,depth+1,hc_len);}
}void tuopu(int i){deque<int> q;q.push_back(i);while(!q.empty()){int x = q.front();q.pop_front();in_tuopu[x]=1;for(int &y:g[x]){in[y]--;if(in[y]==0) q.push_back(y);}}
}void bfs(int x){queue<int> que;que.emplace(x);vector<int> huan;while(!que.empty()){int x = que.front();que.pop();if(vis2[x]) continue;huan.emplace_back(x);vis2[x]=1;vist[x]=1;                  //在dfs的时候不进去环for(int &y:g[x]){if(vis[y]&&!vis2[y]){que.emplace(y);}}}int len = huan.size();hc.emplace_back(len);hc_num[len]++;for(auto &i:huan){dfs(i,0,0,len);}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i = 1;i<=n;++i){cin>>f[i];g[i].emplace_back(f[i]);in[f[i]]++;rg[f[i]].emplace_back(i);} for(int i = 1;i<=n;++i){if(in[i]==0&&!in_tuopu[i]){tuopu(i);}}//处理每个环的环长for(int i = 1;i<=n;++i){if(in[i]==0) continue;vis[i]=1;}for(int i = 1;i<=n;++i){if(in[i]>0&&!vist[i]) bfs(i);//环上的点并且没有经过}//处理每种环长小于d的大小   求的时候要去min(d,hc_dep[i].size())sort(hc.begin(),hc.end());hc.erase(unique(hc.begin(),hc.end()),hc.end());for(int i = 1;i<=n;++i){if(hc_dep[i].empty()) continue;vector<int> t;int mx = reduce(execution::par,hc_dep[i].begin(),hc_dep[i].end(),0,[&](int a,int b){return a>b?a:b;});t.assign(mx+2,0);for(auto &j:hc_dep[i]) t[j]++;for(int j = 1;j<t.size();++j) t[j]+=t[j-1];         //求前缀和hc_dep[i].swap(t);}cin>>query;i64 a,b;while(query--){cin>>a>>b;if(a==b){cout<<n<<"\n";continue;}if(a>b) swap(a,b);i64 cha = b-a,ans=0;for(auto &i:hc){if(cha%i) continue;if(hc_dep[i].empty()){                          //环外面没有点ans+=hc_num[i]*i;}else{int mx = hc_dep[i].size()-1;ans+=hc_dep[i][min(1LL*mx,a)]+i*hc_num[i];}}cout<<ans<<"\n";}return 0;
}/*
5
5 5 4 4 3 
4
9613 992
4626 8562
7139 448
296 401
*/
关键字:简历制作专业模板_国内软件开发培训机构_百度seo推广怎么收费_淘宝站外引流推广方法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: