HNOI2020

我在省选前夜最大的感想就是：我要是是慢热的学习者，那我这热得也太慢了。

尽管这次考试的分数没有作用，还让我们的月考被腰斩，但是我还是感觉很紧张。考试前夜在机房自习，迟迟无法开始动手。思绪总是想回到初二寒假奶奶帮我背生物地理的时候。

Day -1(0619)

今天晚上可以相对自由一点离开。竞赛最重要的是要把握好节奏。

? ——袁帅

但是大多数人仍然还是按照以前的时间走的。回家后相当紧张，有点睡不着。

Day 1(0620)

今天上午的前半段时间在断断续续地睡觉。

上午的后半段时间在改shopping。使用了那个传递的DP算法，结果发现算法本身有一个错误。重新改，写完了还没有测试的时候就要走了。

T1 icefire

预计得分：100 实际得分：

支持两种操作：在平面直角坐标系上，维护加点和删点的操作。点有两种类型，冰和火。每次操作后，要询问这样的两个答案：

选取一条竖线 \(x= T\) ，所有在线左侧的冰点的纵坐标之和为c，所有在线右侧的火点之和为f，求\(ans=2\min(c,f)\)的最大值，以及取到最大值时T为多少。

解法：

这个题花费时间为2小时左右。我感觉是正解，通过了大样例。

用\(f(T)\)表示\(x=T\)右侧的火点纵坐标之和。\(c(T)\)同理。显然， \(f(T)\)是减函数，\(c(T)\)是增函数。

那么，我们的目标就是找到\(min(f(T), c(T))\)的最小值。显然，这个地方就是两个函数的交点。设\(h(T)=f(T)-c(T)\)，显然它是一个减函数，而且我们要的两个函数交点就是\(h(T)\)的零点。

显然选择的T会与某一个火点的x坐标相同。所以先把所有询问输入，再把所有的点（不仅仅是火点）的x坐标离散化。然后用线段树维护\(h(T)\)在T取每一个x坐标时的取值。加入一个火点时，会使得h的一个前缀增加；加入一个冰点时，会使得一个后缀减少；去掉火点、冰点时则相反。每次访问就是线段树二分，找到那个零点。

另外用树状数组维护一下\(f\)和\(c\)，因为用线段树找到零点后还得计算相应的y坐标之和。

要考虑一个问题，就是有可能零点虽然是最优解之一，但不是最优解中T最大的那个。我们需要找到零点后面的第一个火点，作为另一个可能的解。找到零点后面的火点这个操作，就还需要拿一个set保存所有出现了的火点的横坐标，同时拿一个桶来辅助它（因为横坐标相同的火点可能有多个）。

T2 problem

预计分数：40 实际分数：

给出x,n,p,m。求：

\[\big( \sum_{k=0}^{n} f(k)\times x^k \times C_n^k \big)\mod p \]

其中\(f(k)\)是一个m次多项式，它的m+1个系数\(a_0,a_1 \cdots a_m\)也会依次给出。

解法:

暴力\(O(nm)\)有10分。当m=0时，原式等于

\[a_0\sum_{k=0}^nx^kC_n^k=a_0(x+1)^n \]

可以快速幂直接算，这里有30分。

T3 shop

预计得分：10 实际得分：

n个商品，每个商品有一个权值和一个价格。一个合法的选择方案是：选择的商品集合的权值们构成的集合是所有n个商品权值的线性基。

小明选择了一个合法的选择方案A，小刚选择了一个合法的选择方案B。小明想要让小刚也选择A，所以他要改变商品的价格，使得A是所有合法方案中总价最低的，B是所有合法方案中总价最高的。他可以随便改变一个商品的价格，甚至到负数都可以，其要花费的魔力值是新旧价格之差的平方。

求最小的魔力花费。

解法：

写了几个不知道能不能得分的不严谨的暴力。唯一能保证得分的是一个10分的部分分，保证A=B，其言外之意就是要让所有商品的价格相同。用二次函数的性质可以很轻松地解决。

考完之后

考完之后坐校车回学校，袁老师安排了吃晚饭，然后役袁老师简单讲话就放学了。但是我之前和爸爸约好了回家吃晚饭，于是晚饭变成了夜宵。卤虾还没有烤韭菜好吃。

今天考试中途(14:30)突然停电。幸好我有每15秒就按一次Ctrl-S的习惯。我们在偌大的机房里等待回复。说是有两根保险丝，昨天烧了一根，今天因为外面施工出了什么问题，又烧一根。因为是考试中途所以不准讨论，只有从外面传进来的远处的施工声和鸟叫声。我突然感觉这个感受很熟悉，体验了心灵的宁静。

正当校车来了打算接我们回一中继续考试，我们走出机房门口的时候，电力突然恢复了。大家都十分高兴，考试在15:40继续开始计时。这真是一次奇妙的经历。

Day 2(0621)

上午10点半才被爸爸喊醒，11点半才到学校，坐下来开机写了一点昨天的总结，屁股还没坐热就又要出发了。

T1 transfer

预计得分：30 实际得分：

m个信号站，每个信号站有一个编号。有一个信号要走一个n长度的信号序列：从\(S_1\)号信号站走到\(S_2\)号，再走到\(S_3\)号......一直走到\(S_n\)号。

信号站被排列在一条路上，相邻两个相距1单位长度，正常方式下信号只能从左往右传，每单位长度耗时为1单位时间。

如果要从右往左传，就必须传到控制塔处，再由控制塔传给目标信号站。控制塔的位置是最左边的信号站再往左1单位长度。这种传递方式，信号每走1单位长度耗时k单位时间。

你可以随意排列信号站的位置。请把它们排到一个合适的排列，使得总耗时最小。

解法：

想了半个小时的状态压缩DP无果，30分暴力。

T2 tree

给定一棵 n 个结点的有根树 T，结点从 1 开始编号，根结点为 1 号结点，每个结 点有一个正整数权值 \(v_i\)。

设 x 号结点的子树内（包含 x 自身）的所有结点编号为 \(c_1, c_2, \cdots, c_k\)，定义 x 的价值为：

\[val(x) = (v_{c_1} + d(c_1, x)) ⊕ (v_{c_2} + d(c_2, x)) ⊕ · · · ⊕ (v_{c_k} + d(c_k, x)) \]

其中 \(d(x, y)\) 表示树上 x 号结点与 y 号结点间唯一简单路径所包含的边数，\(d(x, x) = 0\)。\(⊕\) 表示异或运算。 请你求出 $\sum^n_{i=1} val(i) $的结果。

解法：

10分\(O(N^2)\)暴力：每个点对从它开始往上直到树根的这条路径产生贡献。如果数据不强，还可以多过几个点。

花一个半小时打的树链剖分跑得比暴力还慢。

我想起了新海诚为了画面的表现效果，把工作人员们辛辛苦苦画的东京俯瞰图用云盖住的典故；于是就放弃了树链剖分的部分，没有让main函数调用它。

T3 count

预计分数：30 实际分数：

对于一个边权图的所有生成树，定义它的权值为：

假设这棵生成树的所有边权为\(w_1,w_2,\cdots,w_{n-1}\)，那么它的权值为：

\[(\sum_{i=1}^{n-1}w_i)\times \gcd_{i=1}^{n-1}(w_i) \]

求所有生成树的权值之和。对998244353取模。

解法：

10分暴力。枚举哪些边被取，保证边有n-1条，然后判断连通性。

20分m=n。找到那唯一的一个环，枚举这个环上哪条边不被使用，求权值。

其他的不会了。

时间是1个小时。

考完之后

考试最后40分钟没有事情可以做了。果然我的水平还有待加强。要是我会求矩阵行列式，第三题就可以多拿20分。

考后张明驰说第二天容易一些。我惊了。这就是两个月停课的威力吗！

从今天下考前1小时时开始，我就开始头疼头晕。这个现象在校车上持续了一路，我为了缓解，在车上乱唱歌。同学们看起来都很萎靡不振，在下午六点的阴沉阳光下显得更加颓唐，这使我更加有了靠乱唱歌来让自己维持心态的想法。

下了车仍然头晕，感觉是因为今天的考试让我的脑子烧坏了，不知道去学校里还能不能学得动。再加上张明驰刚才申请半路下车回家，回家回得毫不犹豫毫无感情，所以我决定今天晚自习请假。没想到袁老师答应得很勉强，我有点犹豫了，但是还是回去了。只要写考试总结的任务完成了，在哪里自习都是一样的吧？我想先回家洗了澡躺一会再爬起来学习，这样会好一些。

总的来说

预计分数：220 实际分数：

这次省选考试相当充实，第一天有了获得感，第二天有了危机感。对将来的信息学习有很大的指导意义。

HNOI2020

幸运的是，我在第二天考试考完之后拿U盘把题面、样例和自己的代码拷下来了，有文可据。曹老师说不要把题目泄露到网上，因为可能会造成一中的名额被削。既然明确说了，我就肯定是不会犯这个傻的。

关于以后学习的感想，我觉得最重要的是做题。看过一个视频：

大学怎么鼓励自己继续学习？

A：高中的学习是由零到整，老师组织大家按照顺序学习既定内容，规定考纲。到了大学就会很迷茫，不知道要学些什么，不知道学了有没有用。方法是从整到零，先定下一个大目标，比如制作一个可以飞的玩意，然后把子任务往下细分，到最后就分成了需要做的小任务。

后来又听陈亮恺说他那个信息国家队的表哥，有几个算法（可并可删除堆之类）是不会的，他就是会做题。

所以每一道题可以看成是一个大目标，需要学会的以及能从这道题里学会的东西就是小任务。这次省选综合性较强，这种做法会很有效。

但是，我说“要多做题”已经很久了，但是仍然没什么用。至今仍然没法让自己多做题，总会被别人超过。这是一个老大难问题，只能靠外力解决了，比如制定渐进但是必须完成的计划这样的传统方法。

我先来：这个星期任务是HNFMSBlog上的两道DP题。。！》》？

我是不是太飘了？

看了张明驰的总结之后

果然停课了的人的思维就是不一样。有许多的思想。

D1T1我忽略了卡常的问题，没有进行进一步的测试，可能这个唯一的我可能AC的题目也葬送了。

D1T2：省选数学原来是需要恐惧的。我之前完全没有见识过。关键词：k次下降幂。

D1T3：打了暴力，这是我感到高兴的。虽然只有10分。

果然D2T1是状压DP，但是没办法我太菜了没有搞出来，去请教题解或者zmc。

D2T2：线段树合并是我的空白区域。

D2T3：矩阵树定理记不清楚，不知道行列式怎么求；更不用说当时讲的复杂的要死的证明过程，完全没有意义。zmc说的容斥又得20分也不知道是什么意思。

总的来说，D1体现我的认知问题，D2体现了我的知识能力问题。怪不得我觉得“第一天有了获得感，第二天有了危机感”了。

感觉自己考前也没有复习什么东西，基本上都是靠的平时积累和最近集训的内容——这可能是我个人的一大特色。该拿的分也都拿到了（只希望不要卡常）。

? ————张明驰

今年的原题有点多，对于板刷AT、CF选手自然是十分友好。也确实，我从停课以来一直和我们组的几位聚聚一起做CF，Daniel_yuan也到这我们打AT。我最近一次打线段树合并就是AT的F题，想必如果没有这个题，我恐怕就少了30分。但是这些网站上的题目质量也是参差不齐的，要提高对自己的要求，就不要满足于在div2的前4个题上。考后要钻研tutorial，把最难的几个题改出来。

? ————张明驰

省选的暴力分呈现越来越少的趋势。今年的纯暴力分有130，高级暴力分数与去年基本持平：310。

? ————张明驰

数据结构依然是大头。其中一道中档题，一道简单题，与往年类似。dp减少了，而且放在了简单题的位置。可以看到数学题数量有明显增加，有3道，线性代数则破天荒地增加到2道，让人不得不重视数学方面的内容。

? ————张明驰

我今年是深刻体会到了被卡常数的恐惧......借用一下lzx的话：

卡常数也是今年省选的一大特色，两天T1,D2T3均有卡常之嫌。这可能对选手的代码实现能力提出了更高的要求。在平时做题的时候，其实并不应该喷毒瘤出题人屑题卡常数，而应该联系如何更高效，更好地实现一份代码，这必定是今后的学习中需要练习的。

? ————张明驰

看了李子熙的总结之后

这么多原题？

他说自己D1的考试策略遭遇了大失败。所以考试时遇到难题不要肝太久。

然后......板子？5min切？模拟退火？

害怕。

这篇总结让我停止了思考。

他告诉我的道理只有一个：做题。CF，AT，Luogu上的题，刷刷刷刷刷刷刷刷刷刷刷刷会对考试有大大的好处。

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

看了袁湘韬的总结之后

先吐槽一句：这就叫丧了？看来Yxt老板日常心态是真的好啊。

他的做题过程虽然比我高很多，但是我仍然能大概看懂，这是很让我感激的。

袁湘韬主要考虑的是他在考场上没有想到很多题目的本来可以想到的解法。

感觉整个过程都在凭着自己的直觉走，把一个个知识点依葫芦画瓢给套上去，并不是对式子整体分析然后有目的地去化简，这是需要加强的。

? ————袁湘韬

好几道数学相关把我送自闭，但是逃避解决不了问题，终究还是要去解决它。

? ————袁湘韬