OI

组合数学 / 题解

洛谷题库 P6031 Cards 加强版 – 题解与思路重现

洛谷题库 P6031 Cards 加强版

对于每一轮对局的 m!m! 种排列，对于编号为 aa 的牌，恒有 (m−1)!(m-1)! 种是以牌 aa 为首的。因此一轮可以归为 mm 种情况，首张为王牌的概率为 1m\frac{1}{m}。

这是某场模拟考试给出的部分分： SubtaskConstraintsPointsDependencies1n,m,k≤522k=123k≤5000101,24m≤1001015n≤k56k≤105101,2,37k≤5×106201,2,3,68411∼7 \begin{array}{cccc} \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline 1&n,m,k\leq 5&2&\\ 2&k=1&2&\\ 3&k\leq 5000&10&1,2\\ 4&m\leq 100&10&1\\ 5&n\leq k&5&\\ 6&k\leq 10^5&10&1,2,3\\ 7&k\leq 5\times 10^6&20&1,2,3,6\\ 8&&41&1\sim 7 \end{array} （更多…）

More
  • 2023年1月31日
数据结构 / 算法

高维莫队

我们可以将莫队算法从一维扩展到更高维度。

考虑正在维护 kk 维结构的信息，且每一维的大小分别为 n1,n2,⋯ ,nkn_1,n_2,\cdots,n_k。为了下文叙述方便，我们将维度大小序列复制一份，得到 nk+1,⋯ ,n2k(ni=ni−k)n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})。我们同时维护 2k2k 个指针，第 i  (i≤k)i\ \ (i\leq k) 个指针维护第 ii 维左端点，第 i  (k<i≤2k)i\ \ (k<i\leq 2k) 个指针维护第 i−ki-k 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 （更多…）

More
  • 2023年1月24日
字符串 / 数据结构 / 比赛日志

MOCK quasi-PTS 20230102 日志

又来了，要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了，要是考场上遇到这种根本没办法查出来的语言相关问题，不就三年 OI 一场空了么？

不过，正是因为考试前从没“用过”悬置指针，才会诱发这样的问题。这再次提醒我们，考场上千万不要使用不熟悉的语法糖，使用平时经大量验证的写法，纵使排版稍欠美观、或代码量增长少许，也是稳定而完备的。

不得不说，这几场“主题模拟赛”的题面中，唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里，又不使其过分冗长而消磨选手耐心。 （更多…）

More
  • 2023年1月23日
数据结构

吉司机线段树（Segment Tree Beats!）复杂度分析

这是原论文中证明的简化版本，但不失其正确性。

记 mxx\newcommand\mx{\text{mx}}\mx_x 为 xx 子树中最大值，smxx\newcommand\smx{\text{smx}}\smx_x 为 xx 子树中严格次大值，fa⁡(x)\newcommand\fa{\operatorname{fa}}\fa(x) 为 xx 的父亲。称节点 xx 为关键点，当且仅当 xx 是根节点，或 mxfa⁡(x)≠mxx\mx_{\fa(x)}\neq \mx_x。设变量 Φ\Phi 表示目前线段树上关键点个数。 （更多…）

More
  • 2023年1月23日
字符串 / 题解

CF356E – Xenia and String Problem – 题解

CodeForces CF356E – Xenia and String Problem

这是一种不需要任何数据结构和处理字符串的工具，但细节繁多的做法。

设全串为 s1…ns_{1\dots n}。不难发现，Gray string 的串长必然是 2w−1(w≥1)2^w-1\quad (w\geq 1) 的形式。若其长为 2w−12^w-1，我们称其为 w−1w-1 阶 Gray string。

同时用归纳法可以证明，设一个 ww 阶 Gray string 的起始位置为 x+1x+1（其终到位置为 x+2w+1x+2^{w+1}），那么必然有 ∀k∈{0,1,⋯ ,w},sx+2k=sx+2k+2k+1=sx+2k+2×2k+1=⋯=sx+2k+(2w−k−1)2k+1∀i,j,0≤i<j≤w,sx+2i≠sx+2j \forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\ \forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j} 成立。例如一个 33 阶 Gray string 可以被描述为 abacabadabacaba\mathtt{abacabadabacaba}。 （更多…）

More
  • 2023年1月5日
组合数学 / 题解

AtCoder AGC058D – Yet Another ABC String – 题解

AGC058D – Yet Another ABC String

将 A,B,C\mathtt{A,B,C} 换成 0,1,20,1,2。记 a,b,ca,b,c 是题面中 A,B,C\mathtt{A,B,C} 的数量，n=a+b+cn=a+b+c。我们称位置 ii 不合法，当且仅当 Si−2+2≡Si−1+1≡Si(mod3)S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3。将其视为两条边 (i−2,i−1),(i−1,i)(i-2,i-1),(i-1,i)，那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 (−1)c(-1)^c，cc 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 f(l,0)f(l,0) 表示“大小为偶数，且能够连成长度恰为 ll 的链”的非法位置集合数量；f(l,1)f(l,1) 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 (l1,l2,⋯ ,ls)(l_1,l_2,\cdots,l_s)（此处的“链”长度均不小于 33），答案即为 ∑(l1,⋯ ,ls)染色方案数⁡((l1,⋯ ,ls))∏i=1s((−1)f(li,1)+f(li,0))\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right) （更多…）

More
  • 2022年12月16日
操作系统与硬件 / 比赛日志 / 组合数学

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日
成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录