OI
「HAOI2012」高速公路-期望+线段树
· ✏️ 730 words · ☕ 2 mins read

Y901 高速公路是一条由 $N-1$ 段路以及 $N$ 个收费站组成的东西向的链,我们按照由西向东的顺序将收费站依次编号为 $1 \sim N$ ,从收费站 $i$ 行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况,会不定期地对连续路段的收费标准进行调整,根据政策涨价或降价。

求对于给定的 $l,r(l < r)$ ,在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ,那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?


「ZJOI2014」力-快速傅立叶变换
· ✏️ 479 words · ☕ 1 mins read

给出 $n$ 个数 $q_i$ ,给出 $F_j$ 定义为:

$$
F_j = \sum _ {i < j}\frac{q_i q_j}{(i-j)^2} - \sum _ {i > j}\frac{q_i q_j}{(i-j)^2}
$$

令 $E_i = \frac{F_i}{q_i}$ ,求 $E_i$ 的值。


「IOI2014」Wall-线段树
· ✏️ 409 words · ☕ 1 mins read

给定一个长度为 $n$ 且初始值全为 $0$ 的序列。你需要支持以下两种操作:

  • $Add, L, R, h$ :将序列 $[L, R]$ 内所有值小于 $h$ 的元素都赋为 $h$,此时不改变高度大于 $h$ 的元素值
  • $Remove, L, R, h$:将序列 $[L, R]$ 内所有值大于 $h$ 的元素都赋为 $h$ ,此时不改变高度小于 $h$ 的元素值

你需要输出进行 $k$ 次上述操作之后的序列。


「CF990G」GCD Counting-并查集/点分治
· ✏️ 1227 words · ☕ 3 mins read

给定一个 $n$ 个节点的树,每个点有一个正整数权值 $a_i$ 。我们定义 $g(x,y)$ 为 $x,y$ 之间简单路径上所有点(包括端点)的权值的最大公约数。

现在请求出对于所有的 $i \in [1,2×10^5]$ ,满足 $1 \le x \le y \le n$ 且 $g(x,y) = i$ 的点对 $(x,y)$ 的数目。


「SCOI2010」股票交易-dp+单调队列
· ✏️ 642 words · ☕ 2 mins read

lxhgww预测到了未来 $T$ 天内某只股票的走势,第 $i$ 天的股票买入价为每股 $AP_i$ ,第 $i$ 天的股票卖出价为每股 $BP_i$ (数据保证对于每个 $i$ ,都有$AP_i \ge BP_i$ ),第$i$ 天的一次买入至多只能购买 $AS_i$ 股,一次卖出至多只能卖出 $BS_i$ 股。两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 $W$ 天;在任何时间一个人的手里的股票数不能超过 $MaxP$ 。

在第 $1$ 天之前,lxhgww手里有数目无限的钱,但是没有任何股票,在 $T$ 天以后, lxhgww 能赚到的钱最多是多少?


「HAOI2016」找相同字符-后缀数组+单调栈
· ✏️ 1661 words · ☕ 4 mins read

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。当这两个子串中只要有一个取得位置不同时,两个方案不同。


「NOI2016」优秀的拆分-后缀数组
· ✏️ 1273 words · ☕ 3 mins read

如果一个字符串可以被拆分为 $AABB$ 的形式,其中 $A$ 和 $B$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  • 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  • 在一个拆分中,允许出现 $A = B$。例如 $cccc$ 存在拆分 $A = B = c$。
  • 字符串本身也是它的一个子串。

「POI2014」PTA-单调队列
· ✏️ 473 words · ☕ 1 mins read

给定 $n$ 个点的高度,规定从 $1$ 点出发,跳到比高度小于当前点的点不消耗体力,否则消耗一点体力,最后到达 $n$ 点。

$q$ 次询问,每次询问有一个步伐限制 $k$ ,求最少耗费的体力。


高斯消元法学习笔记
· ✏️ 1641 words · ☕ 4 mins read

高斯消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。


「TJOI2017」DNA-后缀数组
· ✏️ 784 words · ☕ 2 mins read

加里敦大学的生物研究所发现了决定人喜不喜欢吃藕的基因序列 $S$ ,有这个序列的碱基序列就会表现出喜欢吃藕的性状,但是研究人员发现对碱基序列 $S$ ,任意修改其中不超过 $3$ 个碱基,依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S0$ 上,有多少个连续子串可能是该基因,即有多少个 $S0$ 的连续子串修改小于等于三个字母能够变成 $S$ 。


「CQOI2016」手机号码-数位dp
· ✏️ 785 words · ☕ 2 mins read

手机号码是一个有 $11$ 位且不含前导 $0$ 的数。满足条件手机号码的必须同时满足:号码中出现至少 $3$ 个相邻的相同数字;号码中不能同时出现 $8$ 和 $4$ 。

给定两个数 $L$ 和 $R$ ,统计出 $[L,R]$区间内所有满足条件的手机号码的个数。 $L$ 和 $R$ 都是符合定义的手机号码。


「ZJOI2010」数字计数-数位dp
· ✏️ 689 words · ☕ 2 mins read

给定两个正整数 $a$ 和 $b$ ,求在 $[a,b]$ 中的所有整数中,每个数码(digit)各出现了多少次。


「JSOI2016」最佳团体-树上背包+0/1分数规划
· ✏️ 690 words · ☕ 2 mins read

JSOI 信息学代表队一共有 $N$ 名候选人,这些候选人从 $1$ 到 $N$ 编号。方便起见,JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人$R_i$推荐。如果 $R_i = 0$ ,则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐,JYY 需要保证,如果招募了候选人 $i$,那么候选人 $R_i$ 也一定需要在团队中。当然了,JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$ ,也有一个招募费用 $S_i$。JYY 希望招募 $K$ 个候选人(JYY 自己不算),组成一个性价比最高的团队。也就是,这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。


「NOI2010」能量采集-简单数学
· ✏️ 561 words · ☕ 2 mins read

给定两个整数 $n,m$ ,对于平面上的整点 ${(x,y)|x \in [1,n],y \in [1,m],x,y \in \mathbb Z}$ 。若 $(x,y)$ 与 $(0,0)$ 的连线上有 $k$ 个整点(不包括 $(0,0),(n,m)$ ),则产生的贡献为 $2k+1$ 。求所有满足条件的点的贡献总和。


「NOI2014」魔法森林-LCT
· ✏️ 1210 words · ☕ 3 mins read

给定一个 $n$ 个点 $m$ 条边的无向图,每条边有两个权值 $a_i,b_i$ 。请你找到一条从 $1 \rightarrow n$ 的道路,令道路上所有边的集合为 $S$ ,使 $ans = \max(a_i)+\max(b_j),i,j \in S$ 最小,求出这个最小值 $ans$ 。