「泉七培训 – 黄施霖」最近公共祖先
第一次做交互题。。。
可以任意询问俩点的lca，然后要求回答出树的形态，最多50000个点
各种乱搞搞了90分
首先对于一条链的情况可以用平衡树维护点之间的关系，不过如果直接写个快排也是可以的
那么对于一棵树可以这样考虑
假设我们大致知道了前i个点的情况，这时候加入一个点x
先求其与当前根root的lca设为t，如果t=x，那么fa[root]=x,ls[x]=root,root=x
否则有两种情况，x在root的左子树，或者在右子树，就可以递归下去
所以只要先选俩个点和他们的lca作为起始点然后一个个加入点即可
如果数据是随机的话，复杂度应该是nlogn
判断一条链只要递归次数远超过nlogn基本可以确定
但是由于出题人比较丧病。。一条链加一棵小树就能卡掉这种做法。。所以被卡了10分，暂时还没想到好的做法解决这种情况，大概这种做法的出发点就决定了会被卡吧，如果随机把一棵树分成俩棵什么的这样就不会在这里被卡
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include "lca_lib_c.h" #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define ll long long using namespace std; int n=50000,tmp,size; int root; int ls[50005],rs[50005]; int fa[50005],son[50005],id[50005],rnd[50005]; int ans[50005]; ll cnt; void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;k=t;} void printans() { for(int i=1;i<=n;i++) if(fa[i]&&fa[i]!=i) answer(fa[i],i); } void printchain(int k) { if(!k)return; printchain(ls[k]); ans[++cnt]=id[k]; printchain(rs[k]); } void insert(int &k,int num) { if(!k){k=++size;id[k]=num;rnd[k]=rand();return;} int t=query(num,id[k]); if(t==num){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void chain() { memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); root=0;cnt=0; for(int i=1;i<=n;i++)insert(root,i); printchain(root); for(int i=1;i<n;i++) answer(ans[i],ans[i+1]); } void solve(int k,int x) { cnt++; int l,r; if(ls[k]) { l=query(ls[k],x); if(l==ls[k])solve(ls[k],x); else if(l==x){fa[x]=k;fa[ls[k]]=x;ls[x]=ls[k];ls[k]=x;} else if(l==k&&(!rs[k])){rs[k]=x;fa[x]=k;return;} } if(rs[k]) { r=query(rs[k],x); if(r==rs[k])solve(rs[k],x); else if(r==x){fa[rs[k]]=x;fa[x]=k;ls[x]=rs[k];rs[k]=x;} else if(r==k&&(!ls[k])){ls[k]=x;fa[x]=k;return;} } if(!ls[k]&&!rs[k]){ls[k]=x;fa[x]=k;} } int main() { generate(n); n=init(); int a=1,b=2; root=query(a,b); if(root!=a){ls[root]=a;fa[a]=root;} if(root!=b){rs[root]=b;fa[b]=root;} for(int i=1;i<=n;i++) { if(i==a||i==b)continue; int tmp=query(root,i); if(tmp==root)solve(root,i); else if(tmp==i){ls[i]=root;fa[root]=i;root=i;} if(cnt>3000000)break; } if(cnt>3000000)chain(); else printans(); return 0; } |
计数器 9334349
OI 课件=>
OI 课件=>
呵呵