我预感到以考代练的模式会让我这个罗马数字的标号特别丑陋……
另外 T2 是道模拟,就不写了
# 题面
A. 监控中心 center
给出一个 $n$ 个点,$m$ 条边的连通图。对一些点作标记。当所有作标记操作结束后,对于一个被做了标记的点 $u$,与它相邻的没有标记的点 $v$ 会“报告”信息 v->u
。
输入 $n,m$ 和一个图,第 $i$ 条边的表示方式是 E[i][0],E[i][1]
,即 E[i][0]
和 E[i][1]
之间有边。
现在进行 $Q$ 组询问,每组询问独立。一个询问的内容如下:给出 $k$ 条“报告”信息,一条信息的表述方式是 id
——若 id<0
则报告为 E[-id][1]->E[-id][0]
;若 id>0
则为 E[id][0]->E[id][1]
。
对于每个询问,计算出有多少个点被标记。(保证输入的信息合法)
数据规模: $1\le n\le10^6$,$n-1\le m\le 2.5\times 10^6$,$Q,\sum k\le 10^6$
给出 $m$ 个数组 $A_1$ 到 $A_m$,其中 $A_i$ 大小为 $n_i$。将 $A_i$ 和 $A_j$ 拼成一个数组 $S_{i,j}$,则 $f(i,j)$ 表示 $S_{i,j}$ 的第 $\left\lfloor\frac{n_i+n_j+1}{2}\right\rfloor$ 大的数。
对于每个 $u\in[1,m]$ 求:
数据规模: $m\le 10^4$,$n_i\le500$,数组元素在 $0$ 到 $10^9$ 之间。
# 解析
A. 监控中心 center
我们把信息看成一条条的有向边,那么被有向边围在内侧的点就是被标记的。比如:
Tab. 橙色的点就是被有向边围起来的,也就是被标记的点。
我们把图中所有的有向边都删去,那么原图就变成了一个个的块。
那么我们从简单的情况——树,来考虑。对于一棵树,有向边无非两种情况:
- 从父亲 $u$ 指向儿子 $v$:这说明 $v$ 所在的块 被围起来了;
- 从儿子 $v$ 指向父亲 $u$:说明 $v$ 所在的块 没有被围起来;
怎么计算被围起来的块的大小?
比如上图这个例子,当出现①这个有向边时,把 U 的子树大小加上,出现 ② 时就把 V 的子树大小减去。
总结一下就是:
- 从父亲 $u$ 指向儿子 $v$:加上子树 $v$ 的大小
- 从儿子 $v$ 指向父亲 $u$:减去子树 $v$ 的大小
但是有个 Bug,根节点没法统计到,因为根节点如果有标记,也不可能有从“根的父亲”指向根的边。
这个也有解决方法,此时我们计算出的答案会<0,于是如果最后算出来答案小于0,就直接把整棵树加上(+=n
)就好了。
怎么处理一般的图?我们发现,因为输入是合法的,我们只需要原图的一棵生成树就可以判断哪些点被标记。因此随便生成一棵树,再用树的方法做就好了。
首先把所有数组排序。
考虑当数组 $A$ 和 $B$ 拼起来时,$A$ 中的元素 $a_i$ 成为中位数的条件。设 $A,B$ 的大小分别为 $s,t$,且存在 $k$ 使得 $b_k\le a_i\le b_{k+1}$。
$a_j$ 成为中位数的条件就是 $i+j=\lfloor\frac{s+t+1}{2}\rfloor$。
- $s,t$ 奇偶性相同:$i+j=\frac{s+t}2$,整理可得 $(2i-s)+(2j-t)=0$;
- $s,t$ 奇偶性不同:$i+j=\frac{s+t+1}2$,整理可得 $(2i-s)+(2j-t)=1$;
于是可以将所有数组拼起来得到一个大小为 $\sum n_i$ 的数组 $S$,然后把 $S$ 排序。
从小到大枚举 $S$ 中的元素 $x$。
设 $x$ 原来是 $A_i$ 的第 $p$ 个元素;如果 $A_i$ 能与 $A_j$ 拼起来使得 $x$ 成为中位数,设 $A_j$ 中的第 $q$ 个元素 $A_j$ 中比 $x$ 小的最大数,则 $p+q=\lfloor\frac{n_i+n_j+1}2\rfloor$,即 $2q-n_j=n_i-2p$ 或 $2q-n_j=1+n_i-2p$。
由于是从小到大枚举的元素,那么 $p,q$ 是非常好维护的,关键是如何找满足条件的 $A_j$。于是想到可以维护——定义 $A_j$ 的特征值 $P_j$ 是 $n_j-2q$($q$ 这里是一直维护的),那么我们可以随时维护这个特征值,同时维护对于一个特征值 $P’$,有哪些数组的特征值是 $P’$。
维护这个信息需要支持随时插入删除一个指定元素——链表!
那么枚举到 $x$ 时,我们只要找特征值为 $P_j=-P_i$ 或 $P_j=1-P_i$ 的 $A_j$ 就好了。
由于合法的情况是 $O(m^2)$ 个(即数组两两之间可以产生一个合法的情况),所以这样维护并且暴力枚举的方法是 $O(m^2)$ 的~
# 源代码
A. center.cpp
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<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=1e6,M=2500000;
int n,m;
struct GRAPH{ int to[M*2+3],nxt[M*2+3],head[N+3],ncnt; void AddEdge(int u,int v){ int p=++ncnt,q=++ncnt; to[p]=v;nxt[p]=head[u];head[u]=p; to[q]=u;nxt[q]=head[v];head[v]=q; } int operator [](int id){return head[id];} }Tr;
struct DSU{ int fa[N+3]; void Init(int exn){ for(int i=1;i<=exn;i++) fa[i]=i; } int FindFa(int u){return fa[u]=(u==fa[u]? u:FindFa(fa[u]));} bool Merge(int u,int v){ int fu=FindFa(u),fv=FindFa(v); if(fu==fv) return false; fa[fu]=fv; return true; } }Ds;
int edg[M+3][2]; int dep[N+3],siz[N+3];
int RI(){ int a=0,b=1,c=getchar(); while(c<'0' || '9'<c){ b=c=='-'? -1:b; c=getchar(); } while('0'<=c && c<='9'){ a=(a<<1)+(a<<3)+c-'0'; c=getchar(); } return a*b; } void DFS(int u,int fa){ siz[u]=1;dep[u]=dep[fa]+1; for(int it=Tr[u];it;it=Tr.nxt[it]){ int v=Tr.to[it]; if(v==fa) continue; DFS(v,u); siz[u]+=siz[v]; } } int main(){ freopen("center.in","r",stdin); freopen("center.out","w",stdout); n=RI();m=RI(); for(int i=1;i<=m;i++) edg[i][0]=RI(),edg[i][1]=RI(); Ds.Init(n); for(int i=1;i<=m;i++) if(Ds.Merge(edg[i][0],edg[i][1])) Tr.AddEdge(edg[i][0],edg[i][1]); else edg[i][0]=edg[i][1]=0; DFS(1,0); int cas=RI(); while(cas--){ int ans=0,k=RI(); for(int i=1;i<=k;i++){ int id=RI(),u,v; if(id>0) u=edg[id][0],v=edg[id][1]; else u=edg[-id][1],v=edg[-id][0]; if(dep[u]>dep[v]) ans-=siz[u]; else ans+=siz[v]; } if(ans<0) ans+=n; printf("%d\n",ans); } return 0; }
|
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
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int M=1e4,N=500;
int m,totn; int n[M+3],sp[M+3]; pair<int,int> val[N*M+3];
struct LIST{ int lef[M*2+3],rig[M*2+3],bel[M*2+3],head[2*N+3]; void Insert(int now,int id){ int nxt=head[id]; head[id]=now; lef[now]=0; rig[now]=nxt; if(nxt) lef[nxt]=now; bel[now]=id; } void Delete(int now){ if(head[bel[now]]==now) head[bel[now]]=rig[now]; if(rig[now]) lef[rig[now]]=lef[now]; if(lef[now]) rig[lef[now]]=rig[now]; } }Li;
int ans[M+3];
int main(){ freopen("median.in","r",stdin); freopen("median.out","w",stdout); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d",&n[i]); for(int j=1,inp;j<=n[i];j++){ scanf("%d",&inp); val[++totn]=make_pair(inp,i); } sp[i]=-n[i]; Li.Insert(i,N+sp[i]); } sort(val+1,val+totn+1); for(int i=1;i<=totn;i++){ int bel=val[i].second,num=val[i].first; Li.Delete(bel);sp[bel]+=2; if(sp[bel]==0 || sp[bel]==1) ans[bel]^=(num+bel+bel); for(int it=Li.head[N-sp[bel]];it;it=Li.rig[it]) ans[bel]^=(num+it+bel),ans[it]^=(num+it+bel); for(int it=Li.head[N+1-sp[bel]];it;it=Li.rig[it]) ans[bel]^=(num+it+bel),ans[it]^=(num+it+bel); Li.Insert(bel,N+sp[bel]); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
|
THE END
Thanks for reading!