SCOI游记与题目题解

说在前面

这大概是最后一场考试了吧…?

Day“-3” — Day0

4天省选前例行培训，三天讲课一天考试。貌似每年省选都有的？不过去年那一场me并没有去，那时候自己还是一只小蒟蒻呢…

话说为什么要来参加这个集训呢？me也不是很清楚…不过又有谁知道，会不会有什么“特别”的地方呢？（16年的时候的集训讲了高斯消元和异或矩阵。很巧的是SCOI2016就考了一道线性基）
所以可能还是抱着一丝侥幸=w=，参加了这个集训

日常并没有什么特别的…反正也就是上午讲课，然后下午和晚上都在机房呆着。
机房总是很吵，而且颓废的人超多！所以me和一些小伙伴们，吃完晚饭之后就直接回酒店了。

最后一天上午考了试，有两道题是codeforces edu.场的原题，还有一道不清楚。题目还是很简单的，T1很明显的状压，T2异或最小生成树，T3是一个有点难度的图论题，需要动态维护最小割。
me这次考试没有失误，最后拿到了270，Rk忘记了，不过比较靠前。
不过本身这场考试就存在问题，编译器版本是g++3.8，很多人的程序都莫名编译错误了（比如me同学MaxMercer， $i n t$ $m a x n = 1 e 5$ ，然后因为 $1 e 5$ 是double赋值给了 $i n t$ ，就CE了，岂不呵呵），而且题还简单的1B，所以其实参考价值不大

下午在UESTC附近的酒店住下了（上回是在天街附近住的），晚上出去吃了一碗豌杂面，很久没有尝到这么好吃的面了…上一次还是一年前来这里的时候，不过那家店早就拆了，有点可惜呀=w=

晚上，教练把我们都召集起来，开了一个小短会，让我们放平心态。
睡觉之前敲了了几个板子（UPD：根本没用上hhhhh）

Day1

早上6.35起的床，在酒店磨蹭了一会，同房的zyc趁着这段时间复习了一些板子，然后就下楼吃饭了。楼下的小笼包，味道还不错。愚蠢的me用筷子夹着吃，才咬了一口就掉到桌子上，还滚了一圈，滚了一圈！幸好馅没有撒出来qwq

担心时间会比较紧，所以不少家长都把车开来了，然而大家一致决定走路去考场…~~欢乐多多~~
~~心疼家长1s~~

接下来就是考试了
题目压缩包的密码貌似是随机字符串，me还以为会是「方得始终」，因为NOIP是「不忘初心」，有点小失望

先看了下题目总览，T1时间3000ms空间64M，感觉有点卡空间。T2时间1000ms空间128M，比较正常。T3时间3000ms空间貌似是256M，感觉也比较正常

T1

T1一眼数据结构题，1e5的一棵树，有点权。1e5次询问从「一个点出发的链上点权和」的最大值，支持单点修改点权。其实还是比较简单的吧…询问链，带修改，能上的数据结构已经不剩几个了…
于是me敲了一个点分+线段树，调过小样例之后直接就过了大样例，然后对拍也没有出错，整个题搞定只用了两个小时。me还用计算器算了下空间，感觉没问题，然后就做下一题去了。
期望得分100

写完T1还拉肚子了…可能是昨晚上凉着了吧

T2

回来之后开始gangT2
T2还是树上的，1e5的一棵树，有点权。询问v是u的祖先，并且满足 ${a_{u}}^{2} + A a_{u} a_{v} + B {a_{v}}^{2} \equiv 0 (\mod p)$ 的点对有多少个，其中A，B是给定常数，P是质数，且A，B，P不超过 $1 e 16$ 。
强行快速乘差评
me一开始以为是维护一点什么东西，就可以算出答案的…但是这一项 $a_{u} a_{v}$ 很烦，维护不了，统计信息也存在问题…于是me果断写数据分治，写了百来行。
期望得分55

UPD：关于做法，请教了同机房的大佬Doggu，现在整理后更新于此。正确性还不是很清楚，不过感觉没有锅
（以下都忽略v是u的祖先这个限制，反正这也不是这道题的重点）
题目就是要求符合条件的数对，然而如果有两个未知数，显然mmp。于是考虑先确定一个数，然后查询另一个。
那么先确定 $a_{v}$ ，原式 $⟹ {a_{u}}^{2} + A a_{v} a_{u} + B {a_{v}}^{2} + p \cdot α = 0$ ，现在就是一个关于 $a_{u}$ 的一元二次方程，直接套公式解方程得到 $a_{u} = \frac{- A a_{v} \pm \sqrt{A^{2} {a_{v}}^{2} - 4 (B {a_{v}}^{2} + p \cdot α)}}{2}$ ，然后我们把模数p放回式子里去，那个根号就是模意义下开根，也就是二次剩余，化简得 $a_{u} = \frac{- A \pm \sqrt{A^{2} - 4 B}}{2} a_{v} (\mod p)$ 。
所以如果计算出了上面那坨分数，每个 $a_{u}$ 对应的 $a_{v}$ 就都确定了，随便写点什么统计一下就可以
如果二次剩余无解，那么唯一的合法情况只能是 $a_{u} = a_{v} = 0$
关于复杂度，预处理出分数，快速乘是log的，一共N个点，所以 $N l o g$ ，可过

T3

T3，这题me一点思路都没有的…题意是这样的：给出一个M维的空间，空间中有1e5个关键点。你一开始在坐标原点，并且你的移动方式只能是：选取一个关键点，并把自己对称过去（比如三维坐标下，当前在 $(3, 4, 5)$ 这个点，关键点是 $(- 3, 6, 5)$ ，那么就会移动到 $(- 9, 8, 5)$ 这个点）。
有1e5个询问，每次询问给出一个点的坐标，输出是否能够在模 $P$ 意义下到达那个点（假如P=5，询问点是 $(1, 2, - 2)$ ，如果你可以到达 $(- 4, 7, - 2)$ ，那么视作可以到达）。模数P不超过1e8，维度不超过10
这题me瞎写了一个exgcd+裴蜀就走了…期望得分不知道

考完后

后来考完试和小伙伴们吃饭，说起今天的考试。me突然发现me算T1空间的时候，貌似忘了一个节点要维护多个域，me可能会MLE…? 于是吃饭也不安心了…担心me的第一题没分…全程祈祷

下午去看分，me的T1还真的MLE了，感觉整个人都GG了。教练帮me申诉了，结果是：空间开大可以过，但是空间限制就是64M，所以0分。
所以最终呢，day1只有55分…

不过day1貌似所有人都考的不是很好（因为T1卡空间，me一个同学甚至是写了正解都没敢交，T2和T3全场几乎没人做出来），所以分差不大，那么还是期待明天的发挥吧。

Izumihanako @ 2018.4.6 18:03

晚上，不想吃饭，去买了面包嚼着…

因为想着T1，T2树上数据结构，另外T2本校有同学化出了二次剩余的式子。也就是说，day2可能还要考「图论」、「字符串」、「计算几何」和「dp」
于是睡觉之前复习了一堆字符串的知识，敲了manacher和SAM的板子，回文自动机也看了看，算是对day2的准备吧（UPD：还是没用上，服气）

Day2

昨天晚上十二点过才睡的，设置了一个六点半的闹铃

然而早上天还没亮的时候，me突然醒了，一看手机才6点钟
躺下继续睡，然而睡不着，到了6点半闹铃居然没有响只有震动…？幸好me是清醒的，感觉上天都在眷顾me

然后早上还是去了那一家包子铺吃早餐。然而今天早上换蠢蠢的zyc把包子弄掉了hhhhh
好啦……然后仍然是走路去的UESTC
中间的等待时间就不写了，反正也就那样子…还是说一下考试

惯例的看题目目录，貌似没有什么亮点，day2的空间开的比较大（比起day1），应该不用卡空间。然后看题。

T1

刚看到这个T1的时候，me：又tm的是数据结构？？？黑人问号脸.jpg
题意是这样的，给出一个1e5的序列（数字在整形范围内），然后1e5个询问。每次询问给出 $L, R, u$ ，表示在L到R中任意选取连续的三个数字，使这三个数字加上u之后，整个序列的绝对值之和最大（并不真正的加，只是询问）。带单点修改。保证 $R - L \geq 3$ 。

最终的答案其实就是原序列abs和 + abs变化量。于是现在就是要最大化abs的变化量
做法其实比较简单（如果能想得到的话）。
先考虑单个数字。假设这个数字是a，那么|a|变化量和加的数字u大概是这样的关系：
SCOI2018游记与题目题解（如果a是个正数的话，负数也差不多）然后把连续三个数字的变化量之和，就是三个这样的图像加起来，画出来会发现整个图像有四段：第一段斜率-3，第二段斜率-1，第三段斜率1，第四段斜率3。我们可以把四个线段当作四条直线，那么对于每次询问的u，这个三元组的答案就是四条直线在u位置处的最大值。
于是写四棵线段树分别维护最大值就好了。写起来可能有点点麻烦……另外分块貌似只有70分？

这道题呢，其实和[APIO2016]烟火表演有那么一点相似，都是维护图像找最优位置。在考场上me只发现了「贡献分段」，并没有画个图出来看看，也就没有想到后面的东西了…
所以这玩意er，me写了30分暴力就放掉了…没有想出来正解，可惜可惜

T2

然后是T2，T2的计算几何方向很明显，第一感觉不可做
题面是这样的，一个500个点组成的凸包，有一些顶点是「好点」，并且在凸包内部有一些圆（不超过50个，圆心半径随意，保证圆周不超出凸包）。
现在进行T次操作，每次操作将会在凸包上随机一个点O（点O可以在边上，也可以在顶点上），然后寻找距O点最远的顶点 P，将OP连线。如果P是一个「好点」，且OP不穿过任何一个圆，那么这次操作会获得1的收益，否则收益为0。称收益总和为 $s u m$ ，操作次数为 $Q$
除了选点之外，还可以花费k次操作机会来移除一个圆。可以在T次操作开始之前进行「预先移除」，但是「预先移除」所消耗的操作机会也会被累计进 $Q$ 中。
要求最大化 $\frac{s u m}{Q}$

读完题就发现很不可做对不对！不过还是要思考一下！
对于每个顶点P，先把它的控制范围找出来（控制范围内的点到P距离最远），然后对于每个圆就可以计算出，去掉它之后能增加的「获得收益的概率」，当然有些概率可能需要同时去掉多个点才能获得。然后这和网络流就很像对不对！要求最大化的那个式子也有点像分数规划！感觉可做！

然而me考场上没有想到实现，于是这导致me连部分分都得不到！
然而me并不想弃疗，于是开始乱搞hhhhh…..题目让me求期望，那就直接随机算期望！于是me写了一个，在凸包上等距离分布400000个点，然后统计答案的方法。
最后get到了50分…

UPD：关于实现方法
首先找控制范围那一步，可以用半平面交。假设要求A点的控制范围，枚举另一个顶点B，作AB的中垂线。
SCOI2018游记与题目题解显然粉色的那一半离A更远，于是这就是一个裸半平面交问题。
然后这时已经求出了A的控制范围，枚举每一个圆，算出切线与凸包的交点位置，那么这每一段都是一个最大权闭合子图模型，就可以知道去掉哪些圆之后能获得哪些收益。显然段数是很少的，如下图（黑色细线表示控制范围） SCOI2018游记与题目题解然后建图跑就好了……

T3

然后是T3。T3呢，me现在一点思路都没有，感觉很诡异的一道题，还是先把题面奉上，期待大神的解答吧…（或者官方题解，如果有的话）

题目是这样的：
这是一个只能干两件事的世界：买饮料，时间穿越。
饮料有三种属性（权值）：A，B，C。其中A和B吃多了对身体不好，而C是美味度。这三种属性值都是对于每个单位的饮料而言的。
在这个世界里有1e5个事件，事件分为三种：
1. 推出了一款新的饮料，属性值为：A，B，C
2. 买饮料。给出两个值 $a l$ ， $b l$ ，询问在满足 $\sum A \leq a l$ 且 $\sum B \leq b l$ 时， $\sum C$ 的最大值是多少。饮料可以混合，并且可以购买实数单位的饮料（比如可以这样购买：0.1单位的某种饮料和 0.6单位的某种饮料）
3. 时间穿越。回到第 $i$ 次操作之前
对于每次买饮料操作，输出答案，取整输出

UPD：看了wxh的博客，里面提到了凸包，然后me自己把这道题给想通了……下面奉上题解
这个题其实和 [JSOI2007]合金有类似之处
首先，我们把每种饮料全部按照 $A$ 标准化。就是说，原本是 $(A, B, C)$ 的，现在变成了 $(1, \frac{B}{A}, \frac{C}{A})$ ，转化后与原问题等价。
（下文默认进行了标准化）
然后把所有的点按照「横坐标为B，纵坐标为C」画在坐标系上。可以发现，有用的饮料形成了二维偏序，如下图
SCOI2018游记与题目题解那些被矩形框住的点都是不优的，比如图中打叉的点

然后我们发现，因为可以调配饮料，所以如果一个点在另外两个点连线的下方，那么这个点就不优。
因为这张图里每个点都代表一种饮料，所以线上的所有饮料都能被凑出来。那么同样的花费，肯定是贡献大的优
SCOI2018游记与题目题解于是就变成了这样，被叉掉的点都不优
这时候其实我们已经得到了一个凸包，最优的饮料都在凸包上
那么对于一个询问 $a l$ ， $b l$ ，这时候我们选择凸包上横坐标为 $\frac{b l}{a l}$ 那个点，肯定是最优的。
如果 $\frac{b l}{a l}$ 小于了最左边的点呢？这种情况，可以看作是最左边的点和一个属性为（1，0，0）的进行了调配，因此在凸包中需要加入原点(0,0) 以及无限远点(0,inf)，然后维护动态凸包，于是这道题就完美解决了

end

好吧那么考试的部分就这样完了。
考察的知识点设置很不合理，数据结构的题有一坨，加上算几，这一次省选码量怕是有点大。而且，字符串和dp….

那么最后呢
因为day1T1的MLE，以及day2T1没有想出来，所以最后的分数，真的很不好看。即使加上这些分也会被卡线，没什么好说的，毕竟共享名额

不过me身上的问题也很多呐……考成这样，主要原因还是在me
在省选考场上，算了四遍空间都算错了，这真是只能怪me自己了
另外，me的水平真的够不到那么高，而厉害的大有人在。二次剩余me学过，但是day1T2 me连式子都没有推出来，这能怪谁呢？day2T1，me自信me学过的知识肯定能搞定，但是没有想出来，这又能怪谁呢？

Izumihanako @ 2018.4.13 21:59

后记

想拿D