Day0

笔试很水然而还是挂了一分。。

练习赛没有提答,看来今年没有提答玩了

晚上复习了几个早已忘记的模板,FFT,SAM,单纯型。

果然都没考。

Day1

Integer

Descrption

一个初始为$0$的整数$x$,两种操作:

1.令$x = x + a \times 2^b$

2.询问$x$二进制$k + 1$位的值

$n$次操作,$n \le 10^6, 1 \le b, k \le 30n, |a| \le 10^9$

Analysis

直观的思路是大整数加法,然而进位会很慢,我们不妨用线段树来模拟这个过程。

考虑$a = 1$时,我们只需要找到从第$b + 1$位开始往后第一个$0$的位置,让它变为$1$,然后中间的一段变为$0$。要在$O(\log n)$时间内实现这个操作,只需要在每个节点上记录区间内最后出现的$0$的位置。

$a = -1$时,只需要找到第一个$1$。$a$为其它值时,只需要将其按二进制分成若干个$ a = 1$的操作即可。

这样复杂度是$O(n\log a \log (n \log a) )$的,有点卡,可以将$32$位压成一位,标记仍然是类似的,可以将复杂度中的$\log a$去掉。

于是只需要实现一棵支持区间修改,单点查询的线段树就可以了。然而松爷的题当然不会那么好打,于是T1就做了2h。

queue

Description

有一个字符串集合$S$,初始时是一些字符,每次有三种操作:

1.取出$S$中两个串,首尾相接放入$S$。

2.取出$S$中一个串断开,将断开后的两个串放入$S$。

3.给定$k$和串$T$,询问$T$的所有长为$k$的子串,在$S$中的元素的子串中出现次数的乘积,对$998244353$取模。

初始时$n$个字符,$m$次操作,$n \le 10^5 , m \le 5 \times 10^5, k \le 50$,断开操作的个数$c \le 10^3$。

Analysis

询问出现次数可以使用Hash,不难想到每次合并时将新出现的长度$50$以内的子串加入哈希表,断开时删除即可。

这样复杂度似乎每次是$O(k^2)$的,然而由于总的串数是$O(nk)$的,均摊下来每次$O(k)$,而断开操作会带来$O(ck^2)$的复杂度。

感觉比T1好写很多,然而一直以为复杂度是错的所以花了半个多小时想更好的做法,结果只是证明了复杂度没有问题。。

pool

Description

一个$1001 \times N$的大矩形,每个格子有$q$的概率是安全的,求最大的与大矩形底部相接且只含安全格子的矩形,面积恰好为$K$的概率。输出模$998244353$意义下的结果。

$N \le 10^9, K \le 10^3$

Analysis

考场上只会$N = 1$,想了很久连指数级算法都没有想到。。

不难发现矩形面积只跟每一列底部安全的格子个数有关,而每一列都是独立的,所以直接枚举每一列底部的安全格子数就可以拿到25暴力分。

然而很多dalao都拿到了至少70分。可以先考虑怎样算给定局面的答案,我们将每一列底部的安全格子个数为权值建笛卡尔树(父亲的权值比孩子小),那么答案就是每个节点的$size$与其权值之积的最大值。考虑以此模型DP:令$dp[i][j]$表示大小为$i$的子树,根权值为$j$,答案仍小于等于$k$的概率,则

由于$ij \le k$,直接暴力转移也可以保证复杂度。注意这里算的是小于等于的概率,分别对$k$和$k - 1$DP就能得到最终答案。

而$N$较大时,我们可以不计算$j = 0$时的答案,然后单独考虑。设$f_i$为$i$列时的答案,则:

矩乘可以做到90分,而这是一个常系数线性递推式,可以用多项式快速幂做到$O(k^2\log N)$甚至$O(k \log N \log k)$。

后记

今天似乎还不错,不得不说大样例给的很良心。

本来有点担心T2自然溢出的单哈希会挂,还好并没有卡。

T3完全没想到啊,看来得补补概率期望的DP题了。

100+100+10,竟然A题了?

Day1.5

社会活动日,本来可以去科技馆,但看天气这么热还是呆在学校吧。

上午下午都有电影放映,可惜下午的电影看过了。。于是回寝室看(寝室中弥漫着一股颓废的气息)

恩就这样颓了一天

Day2

game

Description

小 L 计划进行 $n$ 场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆,分别用大写字母 A、B、C 表示。地图一共有四种,分别用小写字母 x、a、b、c 表示。

其中,赛车 A 不适合在地图 a 上使用,赛车 B 不适合在地图 b 上使用,赛车 C 不适合在地图 c 上使用,而地图 x 则适合所有赛车参加,适合所有赛车参加的地图最多只会有 $d$ 张。

小 L 对游戏有一些$m$个要求,这些要求可以用四元组 $(i,h_i,j,h_j)$ 来描述,表示若在第 i场使用型号为 $h_i$ 的车子,则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。

如果无解,输出 -1。

$n \le 5 \times 10^4, m \le 10^5, d \le 8$

Analysis

看到限制条件很容易想到2SAT,于是就随手打了一个暴力2SAT(其实一直以来2SAT都是用DFS打的,根本没用Tarjan + Topsort写过)。

至于$d$张适合所有赛车参加的地图,枚举将其填入$a/b$即可,总复杂度$O(2^d(n + m))$。

然而考场上建图时一个判断写错了,而本题又是spj不好拍,check一下大样例的答案没问题就没管了,结果。。

vegetables

Description

在蔬菜仓库中,共存放有 $n$ 种蔬菜,小 N 需要根据不同蔬菜的特性,综合考虑各方面因素,设计合理的销售方案,以获得最多的收益。

在计算销售蔬菜的收益时,每销售一个单位第 $i$ 种蔬菜,就可以获得 $a_i$​​ 的收益。

特别地,由于政策鼓励商家进行多样化销售,第一次销售第 iii 种蔬菜时,还会额外得到 $s_i$的额外收益。

在经营开始时,第 $i$ 种蔬菜的库存为 $c_i$ 个单位。

然而,蔬菜的保鲜时间非常有限,一旦变质就不能进行销售,不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间:对于第 $i$ 种蔬菜,存在保鲜值 $x_i$​​ ,每天结束时会 有 $x_i$ 个单位的蔬菜变质,直到所有蔬菜都变质。(注意:每一单位蔬菜的变质时间是固定的)

同时,每天销售的蔬菜 . 总量也是有限的,最多不能超过 $m$ 个单位。

现在,小 N 有 $k$ 个问题,想请你帮忙算一算。每个问题的形式都是:对于已知的 $p_j$,如果需要销售 $p_j$天,最多能获得多少收益?

$n, p_j \le 10^5, m \le 10$

Analysis

挂的很惨的一题,首先是看错题了,(题面中对于$x_i$的描述极具迷惑性,差评),看到样例解释才发现不对。因为最后来打暴力的,所以这时候没什么时间了,导致暴力都炸了。。

不过对于$x_i = 0$的测试点还是拿到了,不难发现这种情况下只需要排个序贪心。

还没太弄懂,题解待填坑。。

phantom

Description

平面上有 $n$ 个小 P 的分身。定义一组分身占领的区域为覆盖这组分身的最小凸多边形。小 P 能力有限,每一时刻都会有若干分身消失。但在下一时刻之前,小 P 会使用 “分!身!术!” 使得这些消失的分身重新出现在原来的位置。小 P 想知道,每一时刻分身消失后,剩下的分身占领的区域面积是多少?

每次消失的分身为$k_i$,则$k_i \le 100, \sum k_i \le 2 \times 10^6, n \le 10^5$。

Analysis

20的暴力还是很好写的,过了大样例后又乱搞了一个$k = 1$的做法。

我们将凸包弄出来,显然删掉一个不在凸包上的点不会对答案产生影响。而删掉一个在凸包上的点,新的凸包中,原来在凸包上的点不变,还会有若干个点加入。假设凸包上的点为偶数,对于凸包上的点,我们每隔一个点删去一个点,再求凸包,就可以得到那些删去的点删去之后新加入了哪些点。奇数是类似的,只不过需要特判一下第一个点和最后一个点。

而正解则求了多层凸包,待填坑。

后记

本来以为T1有85,结果挂成35。听说直接随机解都能拿到75,这么弱应该写个暴力啊。

T2暴力写错了,不过还有24。

于是35+24+40滚粗了,没想到T3分还是最多的。

稍有遗憾,如果T2暴力没挂就au了呀。

围观__debug与h10进队

Day$\infty$

第一次NOI就这样结束了呢,虽然Day2挂了点分但A了两题感觉还不错。

总之在考场上还是得求稳一点,尽量打个暴力保证暴力分,能拍则拍,不要只依靠大样例。

题目一定要看清楚,样例解释也要认真看,数据范围里面不要漏掉能拿的部分分。

归根到底还是太弱了,希望接下来一年有所长进

NOI2018再见(前提是还能进NOI2018)