当前位置:首页 >> 助手公告

CF活动助手全屏申领CF#761div.2E散文式

来源:珍惜站长 时间:2022-06-17 15:00:54

半条命:题面不太详尽的非官方英语散文式条码:观念 & 图论

题意

具体来说表述互换操作方式:对有理数,能德博瓦桑县三个使设立的非负有理数,将代替为,称作 1 次互换.

对三个有别有理数互换数是指将代替为的最轻的互换单次.

给三个宽度为的有理数字符串,确保大部份原素各半. 明确要求在大部份可能将的(有别)有理数对中,找寻互换数最小的有理数对或其互换数.

统计数据覆盖范围

思路

规律 1:对非零有理数,其能互换到的大部份数中,有且仅有三个小于.

证明:(存在性)能互换到的最轻数,即为最轻的所对应的. 设是最轻的,那么必有,否则能取到更小的. 整理得到. (唯一性)若不唯一,则必有. 整理得到2^\kappa"> ,那么最轻的将起码是,矛盾.

规律 2:将每个数与其可互换到的数相连(不包括自环),能构成一张图. 这张图是一棵树.

证明:反证法证明图中没有环. 对任意一组数,根据规律 1,不可能将与 2 个比它小的数相连,则不能成环.

推论 2.1:令可互换的小于的数作为的父节点,则 0 是这棵树的根.(易证)

推论 2.2:互换数就是两数在树上的距离.(易证)

规律 3:树的最小深度不超过.

证明:因为越深数字越大,所以最深的叶节点是. 设,则,也就是说每上一层,其数的上界都会缩小一半,自然,最小深度不超过.

这棵树有无穷个节点. 然而有了规律 3 的保障,我们能只存储以给定数为叶子的链,只有最多个有理数. 于是问题的答案呼之欲出:

  1. 一般情况:答案就是树的直径. 2 次 DFS 即可.
  2. 退化情况(树退化成单链):答案是最小的数和最轻的数.

算法总复杂度为.

实现

  • unordered_map>存邻接表,用unordered_map存节点深度. 使用unordered_map也就是哈希表的原因是:用vector内存会爆炸;用map效率低,因为没必要有序. 使用set的原因是方便去重.
  • 树的直径使用两遍 DFS 即可,需要额外维护unordered_map depths记录节点深度.

基本框架

// auxiliary functionsintfa(intx){...}voiddfs(intcur,intfa,intdepth){...}autoargmax(unordered_map<int,int>&mp){...}// solvervoidsolve(vector<int>&v){build_tree();dfs_twice_for_diameter();discussion_and_output();}

完整代码

includeusingnamespacestd;constintINF=0x3f3f3f3f;define ALL(x) begin(x), end(x)define SZ(x) (int)(x).size()unordered_map<int,set<int>>G;// for build treeintfa(intx){inti=0;while(x>(1<<i))i++;return(1<<i)-x;}// for diameterunordered_map<int,int>depths;voiddfs(intcur,intfa,intdepth){depths[cur]=depth;for(intnxt:G[cur])if(nxt!=fa)dfs(nxt,cur,depth+1);}autoargmax(unordered_map<int,int>&mp){pair<int,int>P=make_pair(-1,-INF);for(autoit:mp)if(it.second>P.second)P=it;returnP;}// solver ==================voidsolve(vector<int>&v){// build treefor(intit:v){while(it!=0){intfa_it=fa(it);G[fa_it].insert(it);G[it].insert(fa_it);it=fa_it;}}// twice DFS to calc diameter PQdfs(0,-1,0);autoP=argmax(depths);dfs(P.first,-1,0);autoQ=argmax(depths);// discussion, print answerif(Q.first!=0){printf("%d %d %d",find(ALL(v),P.first)-v.begin()+1,find(ALL(v),Q.first)-v.begin()+1,Q.second);}else{// degenerate: tree is mono-chainpair<int,int>mx=make_pair(-1,-INF),mn=make_pair(-1,INF);for(inti=0;i<SZ(v);i++){if(v[i]>mx.second)mx=make_pair(i,v[i]);if(v[i]<mn.second)mn=make_pair(i,v[i]);}printf("%d %d %d",mn.first+1,mx.first+1,depths[mn.second]);}}intmain(){intn;cin>>n;vector<int>v(n,-1);for(inti=0;i<n;i++)cin>>v[i];solve(v);return0;}