CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====比赛信息=====

  * **日期：2020.3.13**

  * **比赛地址：** [[https://www.jisuanke.com/contest/8124?view=rank|传送门]]

  * **做题情况：lxh(AB)，tyx(ACGJ)，gyp(EF)**

=====题解=====

  * A - Artwork
    * solved by tyx,lxh
    * 题意：在一张图上染色，每次给出$xi,yi,xj,yj$,将从$(xi,yi)$到$(xj,yj)$的路径染黑(保证有$xi==xj||yi==yj$)，问每次这样操作后将图分成了多少个不连通的白块。
    * 数据范围：$1 \le n,m \le 1000$，$1 \le q \le 10^4$。
    * 题解：我们不妨反向来思考这个问题，由于题目不强制在线，我们可以先得到所有处理过后的图(路径每经过一次就将$w[i][j]+=1$),dfs得到块数并用并查集维护相同块内的点，然后倒过来思考，依次去掉染色，当有$w[i][j]==0$,检测其周围有没有没联通的块，将其联通并使块数-1即可。

=====Replay=====

=====总结=====

CVBB ACM Team

用户工具

站点工具

页面工具