SCOI2019 游记

~~作者本人的小号投稿应该没问题吧~~ # ~~先给[自己的博客](https://wallbreaker5th.github.io/2019/SCOI2019%E6%B8%B8%E8%AE%B0/)打个广告~~ 有几张图在该博客上。之后若有更新也更有可能写在该博客。 # Day0 周五 ### 上午 前去报到 ### 下午 笔试，~~到了考场才领到准考证~~。 笔试真是/cy。 `B.竞赛一年` `sb2` `D.无所谓` `有时可以` `A.Lazarus ... D.Lazarus` <!--more--> `逗留考场` `与监考员发生纠纷` …… 10 分钟写完，发了 20 分钟呆，然后提前交卷。 剩下的时间就是颓废+写游记+准备半期考试了（省选一完就是半期） ### 晚上 以后我再也不逞强吃那么辣的东西了(╯‵□′)╯︵┻━┻，一脸狼狈。 就当是攒 RP 吧 --- foldit 真好玩 foldit 不会玩，~~卸了(╯‵□′)╯︵┻━┻~~。 # Day1 ### 上午 凌晨醒了好几次，大概是热得。 到考场还是先拿两个面包和一瓶水（ 这次读优总算一次写对了（雾） 大致题意： #### T1 有三个平台，一、二号，二、三号平台之间均可往返，需要的回合数已知。先有 $m$ 个球在第一个平台，每次可以选择一个平台上的编号最小的球移到相邻的平台，并保证这个球的编号也是目标平台上最小的。问在最优策略下，第 $q_i$ 个回合移动的是编号为几的球。$m\leq1000$，答案不超过 30。 #### T2 查询树上到给定序列的一个区间（长度为奇数）的所有编号的点的距离和最短的点。 #### T3 求体积不超过 $n$ 的所有 $k$ 维长方体在每条边分别取 $b_i(0\leq b_i\leq 9)$ 次方后的体积和。序列 $b$ 可以被分成至多五段相同的数字。 第一眼看题面的印象： - T1 DP - T2 树分治/树链剖分/树上莫队/树上主席树……（反正只要是与树有关的高级数据结构都想到了） - T3 数论 认真分析了一下 T1，认为这是[汉诺塔的变种](https://www.bilibili.com/video/av7539453)。把它与三进制相关联起来，很快就能得出 50 分算法。 T2 一看 $n,m,q\leq 1000$，直接 BFS $n$ 遍预处理出两点之间的距离，再处理一下前缀和，每次询问枚举每个点。 T3 感觉十分毒瘤，不过前面部分分还是比较好写的。一维的两个部分分可以很快解决。对于二维的部分分，直接枚举即可（根据调和级数，时间复杂度是 $O(n\log n)$ 的） 弄完 T3 之后回头看 T1，一开始感觉高精是避不开的，不过之后强行利用 $ans\leq 30$ 的条件，在读入过程中就完成计算，强行不写高精。 T2 一开始以为 $n\leq 1e5\ m,q\leq 2000$ 可以 $O((m+n)q)$ 做： 在确定哪些点被选择之后，我们给每个边标一个箭头，从点少的一面指向点多的一面，代表顺着箭头走可以使答案更优。由于**区间长度是奇数**（这个条件容易被看漏），每个边就肯定都有箭头。也很容易可以看出来一个节点至多只会有一个箭头指出去。 那么我们随便找一个点，顺着箭头走，直到走不动为止，就可以到达**唯一的**最优解。 **但是这个~~常数~~时间复杂度是跑不过去的。** 于是我想到用虚树，然后耗了半天…… 之后根据前面的思路，链也就很好解决了——查询 $[l,r]$ 在链里面的 $pos$ 的中位数。用可持久化线段树可以很好解决。 之后就是各种检查+扫雷。~~扫雷几乎扫一次炸一次，怕是考试已经把 RP 用完了~~ 预估分数： - D1T1 100 - D1T2 50 - D1T3 20 实际分数： - D1T1 100 - D1T2 35 - D1T3 20 ### 下午 面试过于毒瘤 只要是与 OI 无关的题目都能考 我说您大学打广告就打广告，别带着咱选手去面试啊！ 面试完还有宣讲会，~~听了一个就走了~~，~~我宁可去听量子计算~~，~~出去之后背后还有人喊我们，说之后还有五个学校~~ ### 晚上 颓 # Day2 ### 上午 把昨晚买的咖啡喝完了~~这瓶子真心难打开~~ 进考场时已经开始发题了 大致题意： #### T1 平面上有 $n$ 个点，$m$ 次询问点 $(x,y)$ 与 $(0,0)$ 组成的直线把平面分为两部分。求一组编号连续的点，分别计算直线两边的点分别与 $(0,0),(x,y)$ 构成的三角形面积的绝对值之和，求两边的面积和之差的最大值乘 2。$m,n\leq 10^6$ #### T2 一棵带边权无根树树每个点有 R,G,B 三种颜色。求节点集合对 $(U,V)$ 的个数满足：两个集合在树上连通；集合 $U$ 只有 R,G 两种颜色；集合 $V$ 只有 G,B 两种颜色；存在公共节点使其到两集合内任意节点距离不超过 $m$。$n\leq 2000$ #### T3 定义函数 $f(x),g(x)$ 为 W-本质不同 当且仅当对于任意整数 $0\leq x\leq W$ 均有 $f(x)\not =g(x)$。令 $S$ 为一个集合，元素为正整数，定义函数 $f_S(x)=(S_1+x)xor(S_2+x)xor\dots$（$f_\complement$）。给定正整数集合 $S$ 以及 $W$，求函数集合 $C={f_T(x)|T\subseteq S}$ 有多少个函数是 W-本质不同 的。数据范围 $2^{17}$ 第一反应： - T1 计算几何，可能要离线询问，极角排序之类的 - T2 树分治~~反正不会写~~ - T3 状压 先写了个 T1 的 $O(mn)$ 算法——每次查询，算出所有点构成的三角形的面积，然后再扫一遍最大子段和。 T2 弄了半天 $n\leq 15$ 的情况。首先集合压成整数很显然。一开始想预处理去掉很多显然不符合的情况，再 $\text{玄学}^2$ 枚举，发现会被全 G 的 菊花图卡。 于是改了一下思路——对每个可行的集合，处理出其中到各个节点距离小于等于 $m$ 的节点集合，按照集合装进桶。答案即所有有交集的集合对的乘积之和。枚举有交集显然很慢，就枚举无交集。枚举无交集时，先枚举一个集合，接着枚举其补集的子集。由二项式定理可得，时间复杂度是 $O(3^n)$。 T3 的 $n\leq 15$ 的点很好弄，就是枚举~~我还懒到了直接用 `std::basic_string<int>+std::set<std::basic_string<int> >`~~。 $W=0$ 时就是一个背包，也很好写~~但是前一种情况写完之后没有换行也没有退出，导致两种情况的答案连起来输出，调了几十分钟没发现问题~~ 接着回去看 T2，感觉只有一个 G 很好写。以 G 为根，把离得太远的点忽略掉，分别处理两个颜色的连通块数量。$f_x=\prod_{y \text{是}x\text{的儿子 距离不超 同色}}^{}\ \ \ \ \ \ \ \ \ \ (f_y+1)$ 之后疯狂推链的情况。一开始枚举 G 并作为交叉部分的最右边一个节点并想当然以为那一个点到每个节点距离不超过 $m$，最后发现错了。 只剩二三十分钟，Linux 下编译了一下，玩扫雷去了。 预估分数： - D2T1 50 - D2T2 30 - D2T3 40 实际分数： - D2T1 50 - D2T2 30 - D2T3 40 ### 下午 没有等成绩。 到了 3:30 才回家，吃了午饭（？），睡了会觉。 快 5:00 的时候被喊醒，知道了分数，然后去参加体锻。 ### 晚上 颓 写游记 知道自己没进队