IOI2018国家集训队一轮作业第一部分解题报告(CommonAnts)

liu_cheng_ao 2017-10-30 11:56:37 2017-10-30 12:06:17

IOI2018国家集训队一轮作业第一部分解题报告

作者:刘承奥(CommonAnts)

【AGC015C】 Nuske vs Phantom Thnook

原题链接

https://agc015.contest.atcoder.jp/tasks/agc015_c

简略题意

给定一个 N\times M 的方形网格,单元格有蓝白两种颜色, Q 次询问一个子矩形内的蓝色方格组成的连通分量数。保证不存在点双连通的两个不同点。
N,M\le 2000,q\le 200000

建模

考虑无向图 G ,其中的点与蓝色单元格一一对应,对应单元格四连通的点连边。
每次查询就是询问子矩形内的单元格对应的点的生成子图的连通分量数。

算法

由于不存在点双连通,即图是森林,故我们可知连通分量数 C=V-E
故用二维前缀和维护矩形区域内的点数和边数即可。

时间复杂度: O(NM+q)

实现

http://agc015.contest.atcoder.jp/submissions/1610237

【AGC003F】 Fraction of Fractal

原题链接

http://agc003.contest.atcoder.jp/tasks/agc003_f

简略题意

给定一个 H\times W 的黑白网格,保证黑格四连通且至少有一个黑格。
定义分形如下: 0 级分形是一个 1\times 1 的黑色单元格。 k+1 级分形由 H W 列较小一级的分形按网格的样式拼成:与黑色单元格对应的位置是一个 k 级分形;与白色单元格对应的位置是一个全部为白色,尺寸与 k 级分形相同的网格。
k 级分形的黑格的四连通分量数 \pmod {10^9+7} H,W\le 1000,k\le 10^{18}

建模

考虑无向图 G ,其中的点与一个 1 级分形一一对应,对应至少一个位置的黑格四连通的点连边。如下图:
AGC003F_sol_1.png
则答案就是 k 级分形对应的图 G 的连通分量数。

算法

可以看到, G 的连边情况只与网格的上下,左右边的黑格位置是否有重复(即两个拼在一起时水平和垂直方向是否连通)相关。
那么分类讨论:设 \mathrm{lr} \mathrm{ud} 分别表示上下和左右的黑格位置重复的个数

另外,设 v,\mathrm{ev},\mathrm{eh} 分别表示原网格中的黑格个数,垂直方向的相邻黑格对数和水平方向的相邻黑格对数。

  1. \mathrm{lr}>0 \land \mathrm{ud}>0 ,归纳可得 G 任意两点均连通,故答案为 1
  2. \mathrm{lr}=0 \land \mathrm{ud}=0 ,归纳可得 G 任意两点均不连通,故答案为 v^{k-1}
  3. \mathrm{lr}>0 \land \mathrm{ud}=0 ,将网格逆时针旋转 \frac{1}{4} 周变为情况 4。
  4. \mathrm{lr}=0 \land \mathrm{ud}>0 : 我们可以发现所有边都是垂直方向的,故 G 一定是若干条垂直方向的链组成的。
    链是树,我们可以用 C=V-E 来计算连通分量数。
    那么考虑计算 k 级分形对应的图 G_k 中的点数 V_k 和边数 E_k ,有递推式:

    \begin{align} V_k=V_{k-1}\times v,V_1=1 \\ E_k=E_{k-1}\times \mathrm{ud}+V_{k-1}\times \mathrm{ev},E_1=0 \end{align}

    该递推式由以下定理导出: k 级分形等于把 k-1 级分形的每个黑格替换成一个 1 级分形。可以归纳证明。

故我们使用矩阵乘法等方法计算 V E 的线性递推即可。

时间复杂度: O(HW+\log k)

实现

http://agc003.contest.atcoder.jp/submissions/1623698

【LNR1D2T1】 北校门外的回忆

原题链接

https://loj.ac/problem/510

简略题意

给了一个错误的 K 叉树状数组的代码,要求模拟这个代码的输出。

算法一

直接把翻译代码即可。

时间复杂度:当 K 2 的幂时依照 \mathrm{lowbit} 实现方式从 O(q\log n) O(q\log^2 n) 不等;否则依照 \mathrm{lowbit} 实现方式从 O(qn) O(qn\log n) 不等。

期望得分: 0\sim 32

算法二

注意到修改操作的每一步实际上是最低非零位乘 2 并进位。当 K 是奇数时这一位不会变成 0,也就是最低非零位不会改变。

如果我们从 x x+\mathrm{lowbit}(x) 连边的话,会发现实际上 1\sim n 被划分成了若干条链。每次修改相当于后缀加。

那么我们预处理出这些链,每个链用树状数组、线段树或者其它的数据结构维护一下异或和就行了。

时间复杂度: O(q\log^2 n)

期望得分: 19 ,结合前述可得 51

算法三

如果 K 是偶数的话, 1\sim n 不会完全被划分成若干条链。但如果只考虑最低非 0 位中含有的质因子 2 的个数不少于 K 的那些数,它们被划分成了若干条链。

对于不在这些链上的数,我们使用暴力。每次至多需要走 O(\log_2 K\cdot\log_K n)=O(\log n) 步(每一步末位就多一个质因子 2)。
对于链上的数,预处理出这些链,每个链用树状数组、线段树或者其它的数据结构维护一下异或和就行了。

另外,观察到从 x x+\mathrm{lowbit}(x) 连边形成一棵树,可以直接用树链剖分或维 LCT 等数据结构维护。

时间复杂度: O(q\log^2 n)

期望得分: 75

算法四

n 很大,我们不能暴力预处理每条链了。但可以发现每条链由其中第一个数完全确定。

于是我们可以倍增求出 f(i,j) 表示最低非零位为 i ,这一位之前的数为 2^j 时链首的值。每次查询也倍增即可。

处理大下标可以用离线离散化或者平衡树或者树状数组/线段树动态开内存之类的东西。

时间复杂度: O(K\log n+q\log n(\log n+\log K))

期望得分: 100 分。

共 2 条回复

ccc000

高中开始学OI,高一进国集……%%%LCA

lijiamu

前排膜拜LCA