跳转至

第五场

没想到赛程已经过半了

平均成绩距离平均水平依然很远

今天带了 kuangbin 的板子,vagrt 看了看计算几何说:有向四面体都有?

然后今天的二维计算几何考了个《工程测量》什么控制点碎部点当场 PTSD

赛后也是讨论和思考了一下学算法到底是学思想还是学模板

Rank Author Solved Penalty 1001 42/286 1002 70/558 1003 548/4161 1004 93/441 1005 4/75 1006 119/1212 1007 270/1594 1008 26/272 1009 9/86 1010 789/2292 1011 25/127 1012 669/3172
408 team1157 四川大学 2 05:00:48 (-4) 02:49:41 02:11:07

1001 Pandaemonium Asphodelos: The First

题意:给定 \(n\) 个砖块,每个砖块一个权值,初始都为 \(0\)\(q\) 次操作:

  • \(\mathtt{1}\ x\ c\):对区间 \([x-c,x+c]\) 的砖块赋予一个新的属性,与原属性共存
  • \(\mathtt{2}\ x\ y\):将 \(x\) 的属性复制到 \(y\) 以及 \(y\) 相邻、连续、同属性的最长砖块段上
  • \(\mathtt{3}\ x\ v\):对属性与第 \(x\) 块相同的砖块的权值增加 \(v\)
  • \(\mathtt{4}\ x\):输出第 \(x\) 块砖块的权值

操作 \(1\) 中新属性直接记作询问的 \(id\) 即可。

  1. 开一个数组 \(tag\) ,用于维护属性的权重
  2. 开一个珂朵莉树,用于维护砖块属性
  3. 开一个线段树,用于维护砖块权重

那么,操作 \(3\) 只需要将 \(tag\) 中对应属性的权值加上 \(v\) 即可

操作 \(1, 2\) 修改区间属性时,先在珂朵莉树上裂开区间,当一个区间被赋予新属性时,将原属性贡献减去新属性贡献存入线段树中,即在时间上进行差分

特别的,对于操作 \(2\) 修改属性后,有可能珂朵莉树上裂开的区间左右段还有属性相同的区间,需要进行合并

对于操作 \(2\) 只需要对线段树进行单点查询,并加上属性 \(tag\) 存储的权值即可,注意到这里的 \(n\) 很大,应当进行动态开点

1005 3D Puzzles

三维精确覆盖。

我盯着精确覆盖 DLX 的模板看了半点硬是没看出是个板子来,

看了看题解,标程基本和 kuangbin 的模板一样。