第一周 备战决赛

第一周备战决赛,和原队友进行了四次训练,恢复了状态。

ECF2017

A1 签 组合数求和

求:

i=knCni\sum_{i=k}^nC_n^i

T102,n109,k105T\le10^2,n\le10^9,k\le10^5

因为 kk 比较小,所以转化为前缀和问题。组合数前一项到后一项的转移是容易的。直接一边求一边加就行了。

J10 铜 思维题

给一个非负整数数列,每次可以给连续 353-5 个数减一,问能否得到全零。

连续的 353-5 个数,等价于连续的 33 个及以上的数。

差分,正数表示区间的开头,负数表示区间的结束,区间的长度大于等于三,所以一个负数只能用至少三位之前的正数去抵消。求一下前缀和,看中间有没有出现负数就行了。

ECF2020

学长说这一场的体验很好,确实如此。整场比赛有一直有事情做,让人感觉非常充实。

A1 银 计数 动态规划

求一个字符串中有多少最小字符表示为 abcdcd 的子序列

从后往前DP,维护有多少形如 d,cd,dcd的 子序列,然后:

  1. 计算每种以当前字符开头的形如cdcd的子序列各自有多少。
  2. 对于每种以当前字符开头的形如cdcd的子序列,计算前面有有多少形如ab的子序列。
  3. 相乘后累加到答案就行了。

时间复杂度为字符集大小乘字符串长度,空间复杂度为字符集大小的平方。

B2 银 计数 单调栈

给定一个 n×mn\times m 的棋盘,棋盘上的格子会依次消失,给出消失的顺序,求每个时刻棋盘上有多少个长方形。

举例来说,第0时刻棋盘上有 n(n1)m(m1)4\frac{n(n-1)m(m-1)}4 个长方形。

n,m500n,m\le500,需要 n3n^3 的做法。

只要计算每个时刻消失的长方形的数量,最后求前缀和就行了。

我们枚举长方形的上下端点,求出每一列的最小值,即这一列消失的时间。

注意求最小值可以在移动下端点的时候动态更新。

每一列消失的时候,会有许多长方形消失。

长方形的左端点可以是这一列到这一列左边第一个已经消失的列。

长方形的右端点可以是这一列到这一列右边第一个已经消失的列。

所以可以用单调栈维护每一列左遍第一个比它小的列,以及每一列右边第一个比它大的列。

长方形的数量就是两个差量的积。

最后因为爆 int WA 了好几发,果然爆 int 是最常见的错误,没有之一。

G7 金 静态数列 数据结构

给定一个静态数列,每次询问一个区间里有几个子区间有奇数个不同的数。

赛时有思路但没写,赛后卡常卡过去了。我写的是莫队,复杂度比标算慢。

莫队要支持左插、左删、右插、右删,这里以右插为例,其它都是对称的。

每次插入一个数,都会增加许多子区间,统计有多少子区间需要计入答案。

记录上次插入操作增加的子区间的奇偶数量,本次增加的子区间的奇偶数量在上次的数量上更新:

  1. 如果当前区间没有和右端点相等的数,每个区间的奇偶性都会反转。最后加上单个数的区间。
  2. 否则,从右端点到第一个和右端点相等的数,以这些点为左端点的区间奇偶反转,其它区间的奇偶性不变。

所以我们需要预处理:

  1. 每个数的左边第一个和它相等的数的位置。
  2. 这个数为右端点,这个数到前一个相等的数中的点为左端点的区间的奇偶数量。

前者非常容易,后者可以用线段树来维护,每次查询一个区间和,再改变这个区间的奇偶性就行了。

HDU02

A1 银 树链剖分

给定一棵有根树,每次询问给出三个节点集合 A,B,CA,B,C ,问有多少节点 uu 满足条件:

  1. 存在 AA 中元素 aauu 的后代。
  2. 存在 BB 中元素 bbuu 的后代。
  3. 存在 CC 中元素 ccuu 的祖先。

其实没啥思维难度,就写个板子练练手。

树链剖分之后:

  1. AA 中元素 aa 的所有祖先打上标记一。
  2. BB 中元素 bb 的所有祖先打上标记二。
  3. CC 中元素 cc 的所有后代打上标记三。
  4. 线段树上每次维护一个区间,都给修改过的所有点和它们到根的路径打上标记四。
  5. 打完所有标记,遍历线段树,查询有打上所有标记的区间长度之和,最后再次遍历,清空所有标记。

通过压位技术和非递归线段树,以及快读,代码在OJ上排在第三。

F6 银 概率期望 动态规划

一直以为概率期望是自己的强项,结果连这种套路题都不会做,

要在一个游戏里从 Lv.0 升到 Lv.n,每次抽卡会随机抽出两个整数0a<A,0b<B0\le a<A,0\le b<B,表示有 aA\frac a A 的概率升级,升级失败的话有 bB\frac b B 的概率降到Lv.0。可以自由选择是否使用每张卡片,问在最优策略下升到Lv.n的期望抽卡次数。

直觉上看,一开始肯定可以使用所有的卡片,随着等级的升高,会越来越不愿承担降级的风险。

总之,用 ansians_i 表示最优策略下升到 Lv.i 的期望抽卡次数,则 Δansi\Delta ans_i 表示从 Lv.i 升一级的期望抽卡次数。

根据题意:

Δansi=1+1AB0a<A0b<Bmin(Δansi,AaAΔansi+(Aa)bABansi)\Delta ans_i=1+\frac 1{AB}\sum_{0\le a<A}\sum_{0\le b<B}min(\Delta ans_i,\frac{A-a}A\Delta ans_i+\frac{(A-a)b}{AB}ans_i)

0=1+1AB0a<A0b<Bmin(0,aAΔansi+(Aa)bABansi)0=1+\frac 1{AB}\sum_{0\le a<A}\sum_{0\le b<B}min(0,-\frac{a}A\Delta ans_i+\frac{(A-a)b}{AB}ans_i)

AB=0a<A0b<Bmax(0,aAΔansi(Aa)bABansi)AB=\sum_{0\le a<A}\sum_{0\le b<B}max(0,\frac{a}A\Delta ans_i-\frac{(A-a)b}{AB}ans_i)

注意到等式右边是过原点的、在第一象限单调递增的分段函数,且每段的斜率递增。因此方程有唯一解。

把每个分段函数按照转折点的顺序排序,注意到这个顺序和 ansians_i 无关。

一开始答案在所有转折点的右边,随着 ansians_i 的增大,转折点会移动到答案左边,这个时候求出来的答案不准确。

不断更新求答案的公式,直到答案落在公式对应的区间内为止。

说得不够清晰

第二周 拿银跑路

第二周去西安比赛,发挥一般,最后拿银跑路。

ECF2021

A1 签 树的遍历

一开始还挺顺利,每人一道签到题。

给定一棵有根树,求出每个节点的 DFS 序的最小值和最大值。

最小值就是深度,最大值就是节点总数减子树大小加一。

B2 银 计数 字符串

接下来就变成多线程卡题。队友怎样我不知道,反正我是被卡常了。

一个字符串分割成六个非空子串,必须具有 114514114514 的模式(相同的必须相同,不同的可以相同)。

给定一个字符串,求出所有子串的合法分割方案数之和。

n5000,n30000n\le5000, \sum n\le30000

看数据范围应该可以用 n2n^2 的算法。我的思路是这样的:

  1. 对于每个子串,求出以它作为开头 14141451414514 串的数量 (1)
  2. 对于每个子串,求出以它作为结尾 1414114114 串的数量 (2)
  3. 两者相乘求和即为答案
  4. 对于每个子串,求出以它作为结尾 111111 串的数量 (3),最后求个前缀和就得到 (2) 了

我的做法是暴力建一棵后缀树,每个节点按逆序记录对应的所有子串,然后双指针扫一扫得到 (1) 和 (3) 了

使用压位技巧,清空后缀树的复杂度和字符集无关。

最后是一个玄学的事情,每次处理后缀树的一个节点会TLE,但是每次处理一个子串能过,在本机上也能测出这个区别,估计和内存的访问顺序有关。(感谢队友帮我造数据,不然这场真的要拿铁了)

听说正解是 KMP,其实前一周刚刚学习过,仔细一看跟动物园那个题长得真像。不过因为是 n2n^2 就没想到 KMP 上。

第三周 新队磨合

决赛结束了,新的赛季开始了。回去之后就和新队友接连进行了七场训练赛。

牛客02

D4 铜 二分答案 判断负环

就是说有 nn 种货币,以及 mm 种单向的汇率,要求一个系数 ww,使得每个汇率乘上这个系数之后,刚好不存在通过汇率把钱变多的可能。题目保证初始状态存在把钱变多的可能。

n1000,m2000n\le1000,m\le2000

取个对数,二分答案,就变成了经典的判负环问题。然而我不会,还是考场上现学的。

每个节点的初始距离为 00 ,然后轮流松弛每条边,如果第 nn 轮还是有边被松弛,说明有负环。

I9 铜 合并同类项

XkX_kbb 维列向量,YkY_kcc 维列向量,求 Zk=i=1nXkXiYiZ_k=\sum_{i=1}^nX_kX_iY_i

b50,c50,n104b\le50,c\le50,n\le10^4

这题乍一看好像有很深的数学背景,其实就是个合并同类项。

Zkl=i=1nj=1bXkjXijYil=j=1bXkji=1nXijYilZ_{kl}=\sum_{i=1}^n\sum_{j=1}^bX_{kj}X_{ij}Y_{il}=\sum_{j=1}^bX_{kj}\sum_{i=1}^nX_{ij}Y_{il}

把后面那个和式的内容预处理出来,然后去求每个 ZklZ_{kl} 就行了,时间复杂度 b×c×nb\times c\times n

L12 铜 分层图 最短路

有一个分层图,一共有 nn 层,每层有 mm 个节点,每条单向边只会从一层指向下一层。

首先每个节点都都有边指向下一层的同一个节点,其次还会依次输入另外的 oo 条边。

求最少保留连续的几层,可以从第一层的 11 号节点走到最后一层的 mm 号节点。

n104,m2×103,o106n\le10^4,m\le2\times10^3,o\le10^6

空间限制比较特殊,不能存下所有的边,只能读一个处理一个。

其实也不难。求出每层的终点可以被走到的最后的起点就行了。

至于怎么求,维护每个节点可以被走到的最后的起点。加入一条边就进行一次松弛操作。拓扑图上的最短路就是这么简单。至于空间,用滚动数组就可以了。

牛客03

A1 签 最近公共祖先

给定一棵有根树和一个节点的集合。求集合中每个元素的补集的最近公共祖先。

最近公共祖先具有可加性,所以就是求前缀和以及后缀和,每次对一个前缀和和一个后缀和求和就行了。

不过还有更优的算法,就算数据量乘上一百倍也能过这个题。其实答案最多只能有两种。

可能成为答案的节点,必须是至少 k1k-1 个节点的祖先。如果发现一个节点是 k1k-1 个节点的祖先,就用它来更新剩下的那个节点,如果发现一个节点是整个集合节点的祖先,就用它来更新所有节点的祖先。这样就可以线性求答案了。

B2 银 模拟费用流

nn 个员工要派到 mm 个城市,每个城市需要 aia_i 个员工,且 i=1mai=n\sum_{i=1}^m a_i=n,求最小费用。

n105,m10n\le10^5,m\le10

就是个最小费用流,只不过要根据图的性质优化求最短路的算法。

左边是城市,右边是员工,每次找一条最短路,必然是先走到左边的点,再经过若干次反悔,最后走到右边的点。

一次反悔,指先从左边走到右边,再从右边走到左边。于是右边的每一个被选中的点,都可以看成左边的图上的 m1m-1 条单向边,反悔之后这些边就都不可用了。我们用堆来维护左边每个有序点对之间的最小边权,每次找增广路都在左边跑一次全源最短路,然后找到源点到汇点之间的最短路,增广就行了。

其实完全不会费用流,只会一点最短路。这题是我给出想法,学长去实现的。标算的复杂度要更优一些。

HDU03

这场没有一个题是我写的,震惊。

铜 伪计算几何

空间中有一些线段,求一个平面最多能和多少线段有交。线段的端点都是整点。

T10,n50T\le10,n\le50

假设一个平面是答案,它可以在一定范围内移动,在范围的边缘,平面被线段的端点卡住了。

就是说除非所有线段共线,作为答案的平面可以由三个端点确定。

每次任选三个不共线的端点,就可以枚举所有这样的平面,至于如何判断线段与平面相交,只要有向体积之积不为正数就行了。

因为除了求四面体的有向体积没有其它操作,而且都是整数运算,所以是伪计算几何。

HDU04

这场就写了两题,一题只要输出 No 就行了,一题(可以)是线段树,还调了半天。

E5 铜 矩阵乘法 线段树 对顶栈

有一个分层图,一共有 nn 层,每层有 mm 个节点,每条单向边只会从一层指向下一层。

首先每个节点都都有边指向下一层的同一个节点,其次还会依次输入另外的 oo 条边。

求最多保留连续的几层,第一层的 11 号节点走到最后一层的 mm 号节点的方案数不超过 kk

n5×103,m20,o106n\le5\times10^3,m\le20,o\le10^6

求方案数显然可以用矩阵乘法,线段树的预处理是 nm3nm^3 ,查询的时候变成一个行向量乘一堆方阵,用结合律优化一下,单次查询的复杂度是 m2lgnm^2lgn 的,再双指针扫一扫就行了。

我写的时候,查询的是每个左端点的答案,变成在线段树上二分,会稍微麻烦一点,就当练手了。

题解的方法不同,说是对顶栈。就是双指针扫的时候,如果要维护一个不支持减法的区间和,可以用某种技巧做到只做线性次加法。

例题:给定长度为 nn 的整数数列,求所有长度为 mm 的区间积的和,答案对 kk 取模。

牛客04

B2 银 二重积分

有两个同心圆,许多过小圆的切线组成一个多边形,保证多边形在大圆内,求大圆内多边形外一点到最近的切点的距离的平方的期望值。

二重积分,作每对相邻切点的中垂线,那么每个切点都管辖着两个对称的扇形,把每个扇形减三角形的面积和面积分求出来,最后求和再相除就行了。

S=αR22R12tanα2S=\frac{\alpha R_2^2-R_1^2tan\alpha}2

A=θ=0aρ=0R2ρ((ρcosθR1)2+ρ2sin2θ)dρdθx=0R1y=0xtanα((xR1)2+y2)dydxA=\int_{\theta=0}^a\int_{\rho=0}^{R_2}\rho((\rho cos\theta-R_1)^2+\rho^2 sin^2\theta)d\rho d\theta-\int_{x=0}^{R_1}\int_{y=0}^{xtan\alpha}((x-R_1)^2+y^2)dydx

A=θ=0aρ=0R2(ρ32R1ρ2cosθ+R12ρ)dρdθx=0R1((xR1)2xtanα)dxx=0R1y=0xtanαy2dydxA=\int_{\theta=0}^a\int_{\rho=0}^{R_2}(\rho^3-2R_1\rho^2cos\theta+R_1^2\rho) d\rho d\theta-\int_{x=0}^{R_1}((x-R_1)^2xtan\alpha)dx-\int_{x=0}^{R_1}\int_{y=0}^{xtan\alpha}y^2dydx

A=θ=0a(R2442R1R23cosθ3+R12R222)dθx=0R1(x3tanα2R1x2tanα+R12xtanα)dxx=0R1x3tan3α3dxA=\int_{\theta=0}^a(\frac{R_2^4}4-\frac{2R_1R_2^3cos\theta}3+\frac{R_1^2R_2^2}2)d\theta-\int_{x=0}^{R_1}(x^3tan\alpha-2R_1x^2tan\alpha+R_1^2xtan\alpha)dx-\int_{x=0}^{R_1}\frac{x^3tan^3\alpha}3dx

A=R244α2R1R233sinα+R12R222αR14tanα12R14tan3α12A=\frac{R_2^4}4\alpha-\frac{2R_1R_2^3}3sin\alpha+\frac{R_1^2R_2^2}2\alpha-\frac{R_1^4tan\alpha}{12}-\frac{R_1^4tan^3\alpha}{12}

K11 签 数论

一次操作能把 ii 变成 10i+x(0x9)10i+x(0\le x\le9),求对每个模 nn 意义下的 ii,最少几次操作变成 i+1i+1

n106n\le10^6

挺简单的题目,不知道为什么学长让我做。

每次操作之后,值域都是一个连续的区间,所以六次之内必然出解。每次对于一个右端点,求它左侧最近的点是否在区间内就行了。

CCPC

F6 铜 状压动规

一个整数 xx 要模 nn 个模数 aia_i,可以任意排列模数的顺序,求最终结果的最值。

n21n\le21

直接枚举模数的排列有 n!n! 种情况,无法接受。注意到先模小数后模大数,模大数的操作是无效的。

所以可以把模数排序之后,枚举有效的模数,这样就只有 2n12^{n-1} 种情况(最小的模数肯定是有效的)。

J10 银 前缀树 分块

有十个四项选择题,给出若干个提交和总得分,问有几种可能的答案。

n2×104\sum n\le2\times10^4

直接枚举所有可能的答案有 4104^{10} 种情况,无法接受。注意到前一半的答案确定后,后一半的得分也确定了。

把后一半的每种情况对应的分数插到前缀树中,再对前一半的每种情况查询对应的后一半的得分的情况数就行了。

K11 银 计数

非常无聊的题目,根据样例猜结论猜公式就行了。

上学期

上学期打了两场正式赛,也记录一下。

ICPC

C3 银 概率期望

不断累加随机数(在 [0,1][0,1] 之间随机分布),问超过 xx 所需要的操作次数的期望。

0<x20,T1040<x\le20,T\le10^4

f(x)={0x<01+x1xf(x)dxx0f(x)=\begin{cases} 0 & x < 0 \\ 1+\int_{x-1}^xf(x)dx & x \ge 0 \\ \end{cases}

f(x)={0x<0ex0x<11+x1xf(x)dxx1f(x)=\begin{cases} 0 & x < 0 \\ e^x & 0 \le x < 1 \\ 1+\int_{x-1}^xf(x)dx & x \ge 1 \\ \end{cases}

我发现我已经不会做了,震惊。是时候隐退了。

不过场上第一个过的队是离散取点近似求值的,比较取巧,就当是这样做的吧。

G7 铜 概率期望

有一个无限长的数列,出现 ii 的概率是 pi(i=1npi=1)p_i(\sum_{i=1}^np_i=1),求从第一个数走到下一个相等的数,中间出现过的不同的数的期望个数。

n100n\le 100

对于每一个 iji\neq j,求出从一个 ii 走到下一个 ii,中间没有出现 jj 的概率。

aij=pi+(1pipj)pi+(1pipj)2pi=pipi+pja_{ij}=p_i+(1-p_i-p_j)p_i+(1-p_i-p_j)^2p_i\dots=\frac{p_i}{p_i+p_j}

L12 铜 投影 离散化

平面上有一些整点,每个整点会向若干个不相交的角度范围散发光线,角度范围的边界也是整数。求每个整点能够照到多少个整点。

n105,k10n\le10^5,k\le10

对于每个角度范围,将每个点在两个方向向量上的投影长度作为新的座标,然后就变成了求一个点右上角有多少点的经典问题。

唯一要注意的是精度问题。存在两个整点的投影长度相同,当且仅当角度为 4545 的倍数,这个时候求投影要用整数和整数去运算,最后再转浮点数,这样就不会出现精度误差了。

ZCPC

E5 银 概率期望 动态规划

有点繁琐的题目,但没什么难度,注意细节就行了。