搞颓记录

7-12

三道题都不难。。。

T2小细节挂了20分

T3考场上居然不会十进制下的矩阵快速幂。。。

100 + 80 + 80 = 260

T1

完全背包

T2

[换根dp]

换根dp,处理下每个点上去和下去的最长链即可

T3

[矩阵快速幂]

递推式可以通过爆搜/找规律等方法求出,但是直接高精度+矩阵快速幂会T

考虑十进制下的矩阵快速幂

假设需要求A1283A^{1283},那么显然可以拆成(A1A1000)(A2A100)(A8A10)(A3A1)(A^1 * A^{1000}) * (A^2 * A^{100}) * (A^8 * A^{10}) * (A^3 * A^1)

但显然A1040000A^{10^{40000}}不能快速求出,于是考虑优化。

((((A1)10A2)10A8)10A3)10 \Bigg(\Big(\big((A^1)^{10}*A^2\big)^{10} * A^8\Big)^{10} * A^{3}\Bigg)^{10}

和读入优化类似的技巧:

1
sum = (sum << 3) + (sum << 1) + ch - '0';

把运算法则都升一级后显然也成立,也就是A10=((A2)2)2A2A^{10} = \Big(\big(A^2\big)^2\Big)^2 * A^2

复杂度就降下来了

7-13

今天崩了,11:20才做出来T1,后面两题都没看

正解想不出来的时候考虑暴力做法,一步步往下推就能推出来了

100 + 0 + 0 = 100

Process

T1

dp[i]dp[i]表示从合成出ii级武器开始,到合成出nn级武器所需的期望花费

好像不能这么设。。。

dp[i]dp[i]表示合成出ii级武器的期望花费

ai=min{ci,bmax{0,i1}}ci\displaystyle a_i = \frac{\min\{c_i, b_{max\{0, i - 1\}}\}}{c_i}

以下是错误思路。。。

(dp[i2]+dp[i1])(dp[i - 2] + dp[i - 1])ai1a_{i-1}的概率转移到dp[i]dp[i]

(dp[i]+dp[i+1])(dp[i] + dp[i + 1])(1ai+1)(1-a_{i+1})的概率转移到dp[i]dp[i]

dp[i]=ai1ai1ai+1+1×(dp[i2]+dp[i1])+1ai+1ai1ai+1+1×(dp[i]+dp[i+1]) dp[i] = \frac{a_{i-1}}{a_{i-1} - a_{i+1} + 1}\times(dp[i - 2] + dp[i - 1]) + \frac{1 - a_{i+1}}{a_{i-1} - a_{i + 1} + 1}\times (dp[i] + dp[i + 1])

边界:

dp[0]=adp[0] = a

dp[1]=dp[1] =

现在是10:47,我还一分都不会写。。。

状态设得可能有点问题,应该是第一次合成出ii级武器的期望花费

考虑dp[1]dp[1],显然只要没合成出11级武器,就一直在00级不断合成,好像实际上不需要考虑dp[2]dp[2]对它的影响

dp[1]=i=0(1a0)ia0×(i+2)dp[0](1a0)dp[1]=i=1(1a0)ia0×(i+1)dp[0]a0×dp[1]=2a0×dp[0]+i=1(1a0)ia0×dp[0]a0×dp[1]=2a0×dp[0]+(1a0)(1(1a0))dp[0]a0×dp[1]=2a0×dp[0]+(1a0)×dp[0]dp[1]=(1+1a0)dp[0] \begin{aligned} dp[1] &= \sum_{i=0}^{\infty}(1-a_0)^ia_0\times (i+2)dp[0]\\ (1-a_0)dp[1] &= \sum_{i=1}^{\infty}(1-a_0)^ia_0\times(i+1)dp[0]\\ a_0\times dp[1] &= 2a_0\times dp[0] + \sum_{i=1}^{\infty}(1-a_0)^ia_0\times dp[0]\\ a_0\times dp[1] &= 2a_0\times dp[0] + (1-a_0)\Big(1-(1-a_0)^{\infty}\Big)dp[0]\\ a_0\times dp[1] &= 2a_0\times dp[0] + (1-a_0)\times dp[0]\\ dp[1] &= (1 + \frac{1}{a_0}) dp[0] \end{aligned}

好像这样就过了样例了...

那么对于后面的dp值同理,应该也只需要考虑从前推过去的情况

dp[n]=i=0(1an1)ian1×((i+1)dp[n1]+dp[n2])dp[n]=1an1dp[n1]+dp[n2] \begin{aligned} dp[n] &= \sum_{i=0}^{\infty}(1-a_{n-1})^ia_{n-1}\times \Big((i+1)dp[n-1] + dp[n - 2]\Big)\\ dp[n] &= \frac{1}{a_{n-1}}dp[n - 1] + dp[n - 2] \end{aligned}

写的时候把1an\frac{1}{a_n}变成ana_n

11:18终于签上到了。。。

T3

启发式合并维护倍增数组,O(nlog2(n))O(n\log^2(n))

写不完了。。。

T1

[概率和期望]

process里讲完了

T2

数论,没碰

T3

[启发式合并] [倍增]

考虑启发式合并维护倍增数组

既然要启发式合并,那么树就必须要是一棵无根树,但原题因为要判断祖孙关系,必须要是一棵有根树

为了解决这个问题,只需要倍增时多维护一下边的方向即可,查询的时候要保证xyx\rightarrow y的路径上边的方向都相同且朝向yy

7-14

Process

T1搞了好久,后面两道题没什么思路

100 + 20 + 52 = 172

T1

操作顺序对答案无影响

先全部操作列,考虑列对行的贡献,再操作行

T2

倍增?

复杂度太高了。。。

T3

[l,r][l, r]的答案:左端点[1,l]\in[1, l],右端点[r,n]\in[r, n]的长度最小的合法区间

类似于二维数点?

T1

T2

[分块] [神仙题]

神仙题

首先显然会有循环,循环节是mm的倍数,且大小nm\le n * m

暴力做法是每次O(nm)O(n*m)找循环节,考虑一个类似于分块的优化

jump[i]jump[i]表示第一列第ii行走mm步到达的位置,即每mm步一大步,一大步一大步地走

再考虑修改操作:

假设修改(x,y)(x, y),那么只有可能(x1,y1),(x,y1)(x+1,y1)(x - 1, y - 1), (x, y - 1)(x + 1, y - 1)这三个格子的决策发生变化,然后对第一列的某些格子的jumpjump值产生影响

即我们需要考虑,第一列有哪些格子能走到当前格子

不难发现,它一定是连续的一段

因为上下两条曲线会将中间一块区域围起来,只要碰到边界就会走向目标格子

于是直接每次暴力往前找出连续区间的上下边界,修改其jumpjump

这个地方有不少细节,具体见代码。最主要的一个性质:

  • 在往前推区间范围时,合法的上下界每次最多会往里缩小11

T3

[扫描线] [堆] [数据结构] [线段树]

扫描线 + 堆 + 线段树,关于题目的具体细节见GC's Blog

其中线段树维护的部分非常厉害

一开始在线段树中对不同的节点赋不同的初值,巧妙地解决了,在扫描线移动时,后缀的长度同时发生变化的问题。即通过这种方法使得所有位置平等:离扫描线越远,初始赋上的权值越大

7-15

Process

T1开场切了,T2搞了好久,T3没时间搞了

100 + 100 + 25 = 225

T1

显然答案一定是某个位置与其目标位置之间的区间

随便统计下答案就行了

T2

[最短路]

在某个点(x,y)(x, y),只有两种决策方式

  1. 往四个方向走一步
  2. 往四个方向中的两个方向扔传送门,然后往其中一个传送门走,从另一个传送门出来

跑最短路即可

T3

[三分] [树状数组]

具体Solution见GC's Blog 我又不要脸地把链接贴上来了

考虑枚举最大值位置,然后确定其高度。显然代价随高度是一个单峰函数,可以三分。于是要快速计算三分出的最大值valval在位置ii时的代价

注:以下的ii表示枚举出的最大值位置,jj表示

题目的限制hj=hiijh_j= h_i - |i - j|可以转化成

{hjj=hii   (j<i)hj+j=hi+i   (j>i) \begin{cases} h_j - j = h_i - i~~~(j < i)\\ h_j + j = h_i + i~~~(j > i) \end{cases}

设初始的高度为vjv_j,最终方案的高度为hjh_j,那么我们就是要求vjhj\sum{|v_j - h_j|}

同样的,它可以化成

{(vjj)(hjj)   (j<i)(vj+j)(hj+j)   (j>i){(vjj)(hii)   (j<i)(vj+j)(hi+i)   (j>i){{(vjj)(hii)   ((vjj)>(hii))(hii)(vjj)   ((vjj)<(hii))   (j<i){(vj+j)(hi+i)   ((vj+j)>(hi+i))(hi+i)(vj+j)   ((vj+j)<(hi+i))   (j>i) \begin{aligned} &\begin{cases} |(v_j - j) - (h_j - j)|~~~(j < i)\\ |(v_j + j) - (h_j + j)|~~~(j > i) \end{cases} \\\\ \Rightarrow &\begin{cases} |(v_j - j) - (h_i - i)|~~~(j < i)\\ |(v_j + j) - (h_i + i)|~~~(j > i) \end{cases} \\\\ \Rightarrow &\begin{cases} \begin{cases} (v_j - j) - (h_i - i)~~~\Big((v_j - j) > (h_i - i)\Big)\\ (h_i - i) - (v_j - j)~~~\Big((v_j - j) < (h_i - i)\Big) \end{cases}~~~(j < i)\\ \begin{cases} (v_j + j) - (h_i + i)~~~\Big((v_j + j) > (h_i + i)\Big)\\ (h_i + i) - (v_j + j)~~~\Big((v_j + j) < (h_i + i)\Big) \end{cases}~~~(j > i) \end{cases} \end{aligned}

两个树状数组,一个维护前缀信息,以vjjv_j - j为下标;一个维护后缀信息,以vj+jv_j + j为下标

7-16

NOI Day1 网络同步赛

T1写了70分暴力挂成65,T2 T3都是裸暴力

7-18

NOI Day2 网络同步赛

搞了一上午T1的K-D Tree,T3写了暴力,T2暴力dp没写完

晚上把T2 40分暴力写了

7-19

Process

开场写了T2,然后想了很久的T1。T3暴力一个小细节写挂。。。

95 + 100 + 0 = 195

T1

[容斥] [二分图] [动态规划]

题目要求没有不合法位置的排列个数,考虑容斥,转化求至少有ii个位置不合法的方案数

ans=i=0n(1)i(ni)!×f[i] ans = \sum_{i=0}^{n}(-1)^i(n - i)!\times f[i]

其中f[i]f[i]表示钦定ii个位置不合法的方案数

通过观察发现,不合法的情况中,每个位置和权值的对应关系如下图:

19-7-19-1

显然,钦定ii个位置不合法就是从图中选出ii条边,且这个边集必须是一个匹配

由于这个二分图是由若干条链构成的,于是可以把链一一提出来,排成一排做dp

因为最多只可能相邻的两个点之间有连边

dp[i][j][0/1]dp[i][j][0/1]表示到第ii个点,选出了jj条边,当前这个点和它前面的点之间是否有连边的方案数

T2

[树状数组]

我的做法和标程稍微有点不一样

类似于共价大爷游长沙的做法,给每条非树边连接的两个点一个权值,树状数组维护,求子树权值异或和即可

T3

本以为是一道披着多项式外衣的斗地主题,最后才知道其实是一道披着斗地主外衣的多项式题


晚上把自己T2的std和题面写了。myy的题是真的仙

打算多搞一点T2的部分分

7-20

Process

早上去搞了牙齿,到机房已经9:00了。先花了40分钟左右写完了T1(还是有点慢),然后写了T3的O(nlog2n)O(n\log^2n)的做法,卡了下常就没时间了。T2只写了个暴力

T1

考虑在旋转的时候答案会如何变化

显然,有些位置上的答案会+1+1,有些会1-1,但是我们并不需要知道这些位置到底是什么

直接用两个变量动态维护需要+1+1的位置的数量,和需要1-1的位置的数量即可

因为每个数最多只会改变一次贡献的正/负,随便存起来搞下就行了

T2

[线段树] [数据结构]

线段树维护矩阵

线段树的[l,r][l, r]上维护f[i][j]f[i][j]表示从(i,l)(i, l)走到(j,r)(j, r)的最少步数,随便合并

T3

O(nlog2n)O(n\log^2n)的暴力

枚举答案区间中的最小值,分别往左右二分扩展即可


想今天把自己的题搞完,不知道搞不搞得完

显然搞不完啊。。。

7-21 ~ 7-28

去海南浪

期间把自己的题数据造完了

课件开了个头,基础知识点基本写完了

7-29

beamer样式调了好久

课件搞了一点点

7-30

上午把课件写了34\frac{3}{4}

下午又调了好久beamer样式

晚上大体把课件搞完了

7-31

上午看了哪吒

下午调整了下课件的一些小细节,正式收工