操作系统与硬件 / 比赛日志 / 组合数学

MOCK quasi-PTS 20221214 日志

NOIP+？准省选难度？已经到了能力的边缘么？

但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。

另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。

简略题解

A – 种花

（更多…）

More
  • 2022年12月16日
数据结构 / 题解

NOIP 2022 T4 – 比赛 (match) – 题解

洛谷题库 P8868 [NOIP2022] 比赛

本文记号可能稍显凌乱，但都能在题面或者前文中找到定义。

部分分

20 pts\text{20 pts} – n,Q≤3000n,Q\leq 3000

考虑枚举所有 O⁡(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间，预先计算它们本身的答案。记 ga(l,r)={max⁡{ai∣l≤i≤r},(1≤l≤r≤n)0otherwisegb(l,r)={max⁡{bi∣l≤i≤r},(1≤l≤r≤n)0otherwise\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\end{aligned} 则做前缀和 s(l,r)=∑i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i)，对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 ∑i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

令 n,Qn, Q 同阶，时空复杂度 O⁡(n2)\bigO(n^2)。 （更多…）

More
  • 2022年12月8日
OI / 组合数学 / 题解

CF1747E – List Generation – 题解

这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为，aa 和 bb 均为单调不降的序列，长度相等（记为 kk），且 a1=0,ak=n,b1=0,bk=m,∄i∈[2,k],ai=ai−1∧bi=bi−1a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}。

考虑差分序列 ai’=ai−ai−1(i∈[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])，bi’{b_i}’ 同理，它与原序列形成双射。于是不存在 ai’=bi’=0{a_i}’={b_i}’=0 的差分序列合法。考虑 ∑i=2kai’=n\sum_{i=2}^{k}{a_i}’=n，也就是和为 nn 的 k−1k-1 元线性方程组的一组非负整数解；b’b’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 ∑c=0k−2(k−1c)(n+(k−1)−1−c(k−1)−1−c)(m+(k−1)−1−c(k−1)−1−c)(−1)c\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c 答案累加上式结果 ×k\times k。 （更多…）

More
  • 2022年12月1日
OI / 比赛日志

MOCK NOIP 20221117 日志

T1 的 Hack 数据提醒我，尽管时间复杂度没有变化，但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

T2 没有认真读题，忽略了“恰执行一次”的要求。

T3 里面没有使用自己熟悉的存边方式，时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

简单题解

A – 跳棋

从 (x,y)(x,y) 跨步跳能够跳到 (x±2,y),(x,y±2)(x\pm 2,y),(x,y\pm 2)，以及 (x+k,y+k),k=±2(x+k,y+k),k=\pm 2。可以发现 x,yx,y 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块，在这些连通块上 BFS 即可。

若采用 std::map 存储，时间复杂度为 O⁡(7nlog⁡n)\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)。需要采纳“避免遍历不存在的连通块”之类的优化。 （更多…）

More
  • 2022年11月23日
OI / 比赛日志

MOCK NOIP 20221112 日志

仍然是中规中矩的一场模拟赛。前两题正解，第三题暴力，第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边，若是则无解，若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路：两球相撞调转方向时，我们不认为是球本身转向，而认为两球仍然保持原方向运动，而其编号交换。 （更多…）

More
  • 2022年11月20日
OI / 比赛日志 / 算法

MOCK ??? 20221012 日志

44 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现：

  • 当树的形态确定时，我们总是将权值更大的节点安插到深度更小的叶子上。可以将 aa 降序排序后逐层填写。
  • 一个节点只可能有 00 个或者 22 个儿子。如果只有 11 个儿子，显然可将该节点删除而整棵子树全部向上平移。

设 f(d,i,c1,c2)f(d,i,c_1,c_2) 表示“现在位于第 dd 层（此处“层”指的是节点实际深度）。已经填写好了 a1,a2,⋯ ,aia_1,a_2,\cdots,a_i，且第 dd 层共 c1c_1 个空置（非叶子）节点，第 d−1d-1 层有 c2c_2 个此类节点”。那么两层的每一空置节点，均会有一个第 d+1d+1 层的儿子。枚举“下一层要填写 kk 个元素”，有转移 f(d+1,i+k,c1+c2−k,c1)←f(d,i,c1,c2)+(∑j=i+1i+kaj)(d+1)f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1) （更多…）

More
  • 2022年11月18日
OI / 比赛日志

MOCK NOIP 20221110 日志

fread 专场。44 道题里面 33 道适合用快读。

简略题解

A – 远征

由题意可得 aia_i 应为目前战斗力 xx 的子集。这一迭代过程最多只有 1010 轮（ai,x≤1023=210−1a_i,x\leq 1023=2^{10}-1），于是处理出跳转指针暴力模拟即可。

复杂度 O⁡(1024n)\newcommand\bigO{\operatorname{O}}\bigO(1024n)。

B – 传送

观察样例可以感知到答案应当只有 −1,0,1,2-1,0,1,2 四种取值。

根据题意，在原图 GG 上若有一条简单路径（在迭代加边的过程中绕回原点不符和要求） x→⋯→yx\rightarrow\cdots\rightarrow y，满足其长度 l≡1(mod2)l\equiv 1\pmod{2}，那么 G’G’ 上一定存在边 (x,y)(x,y)。

所以若 x,yx,y 不在同一连通块中，无解；若存在满足题意的路径，答案即为 11；否则必须经某个点中转，答案为 22。

（更多…）

More
  • 2022年11月16日
OI / 字符串 / 比赛日志

MOCK NOIP 20221108 日志

中规中矩的一场模拟赛。

T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。

T2 有我喜欢的马拉车 Manacher 算法，是印象里第二次在模拟赛应用。

然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。

简略题解

A – 石蒜反冲

这好像是很早以前的译名了。现在它叫《莉可丽丝》。

遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。

一些不应用就过不了的优化：

  • 二者数量之差可只记录到 n15\frac{n}{15}。1515 是两个串的总长度。
  • 转移时对于 ? s c a o 还有其他字符分类讨论，保证单次转移复杂度为 O⁡(1)\newcommand\bigO{\operatorname{O}}\bigO(1)。

时间复杂度 O⁡(n2)\bigO(n^2)。 （更多…）

More
  • 2022年11月16日
成都外国语学校高一 OIer。喜欢搞些杂七杂八的小项目。擅长长跑。常去骑车。

一言(ひとこと)

陽炎は黄泉に待たむと。

分类