方差 题解noip 2021
CSP-S 2021 补题
P7913 [CSP-S 2021] 廊桥分配 考虑对于国际航班和国内航班单独进行分配 对于国际航班 处理 \(res1[i]\) 数组作为给国际航班分配 \(i\) 个廊桥的最大飞机停靠数量 \(res2[i]\) 同理 对于每一种类的航班 我们维护一个 \(in\) 优先队列和一个 \(left ......
2023年石门中学NOIP模拟测试(2023.10.13)
再次被打爆... T1 sb 题,写个 \(\text{vector}\) 排序还挂了,服了。 T2 oh,我会推柿子。oh,我不会 \(\text{Lucas}\) 😃 写了 \(\text{1h}\) 纯是 fw。 T3 md,唇笔东西,设出状态不会转移。 ......
区间方差
# [P5142 区间方差](https://www.luogu.com.cn/problem/P5142) 单点修改,区间查询。 更新很简单,直接赋值,然后更新(注意 $y^2$ 可能爆 `int`)。 对于询问,我们考虑完全平方公式 $(a_i-a)^2=a_i^2-2aa_i+a^2$,我们发 ......
题解 P2188 小Z的 k 紧凑数
题目描述 小 Z 在草稿纸上列出了很多数,他觉得相邻两位数字差的绝对值不超过 \(k\) 的整数特别奇特,称其为 \(k\) 紧凑数。 现在小 Z 想知道 \([l,r]\) 内有多少个 \(k\) 紧凑数,希望你帮帮他。 具体思路 首先,要求数的个数,自然想到数位 dp。 然后可以用容斥原理拆询问 ......
CF1886C Decreasing String 题解
题面 \(S_n\) 由 \(S_{n-1}\) 去掉一个字母得到,\(S=S_1+S_2+...+S_n\) 给定 \(S_1\) 求 \(S\) 的第 \(N\) 位 solution 我们先考虑怎样去字母能保持字典序最小 显然,我们发现如果一个字母比前面那个字母小,那么我们就要删除前面那个字母 ......
CF1886A Sum of Three 题解
Question 给定一个正整数 N ,我们需要找三个不同的整数x,y,z,使得 N = x+y+z,其中下x,y,z不能被三整除 solution 我们把N%3会有一些余数,我们针对余数来讨论,其中我们只关注xyz的余数 如果余数为0 那么也就可能是1+1+1,或者2+2+2,但是考虑到xyz不同 ......
CF1886B Fear of the Dark 题解
Question Monocarp 在一个二维平面上,他的初始点在 \(O=(0,0)\) ,他需要到 \(P(P_x,P_y)\) 不幸的是,他能走的范围在两个圆内,我们给出了两个圆的坐标 \(A=(A_x,A_y)\) ,\(B=(B_x,B_y)\) 两个圆的半径相同,我们需要找到最小的半径让 ......
2023NOIP A层联测10 T4 子序列
2023NOIP A层联测10 T4 子序列 题面及数据范围 Ps:链接来自accoderOJ。 考场2小时才做完 T1,抱着试一试的心态看了 T4,然后想到做法了,调了 1 个多小时没调除了,赛后发现数组开小了,因为与正解做法稍有不同,于是又调了一下午…… 转移方程 设状压dp \(f[i][st ......
[NOI2014] 字符串(题解)
字符串(题解) 题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。 一句话题意:我们会处理kmp算法中的fail[]数组,来记录[1, i ]的真前后缀的最大 ......
[APIO2019] 路灯 题解
LG5445 把询问 \(x,y\) 看作平面上的点 记当前时刻 \(t\),\(l\) 是与 \(i\) 连通的最左端,\(r\) 是与 \(i+1\) 连通的最右端,可以通过 set 维护断边找到 连边 \((i,i+1)\) 时 \(x\in[l,i],y\in[i+1,r]\) 连通了,考虑 ......
CF963B Destruction of a Tree 题解
CF963B Destruction of a Tree 题解 洛谷题目链接 这里提供一个较为朴素的 DP 想法。 题意简述 给定一棵树,节点个数不超过 \(2 \times 10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。 思路分析 首先可以随便选一个点作为根。 其 ......
ABC214H Collecting 题解
前言 这是一道比较神仙的题目,其后半部分的建图是比较困难想到的,前半部分还是较为容易的。 题意 现在有一张\(N\)个点\(M\)条边的有向图,每个点有一个点权\(a_i\),现在要找出\(K\)条路径,使得这些路径的并集的点权和尽量大。现在求出点权和。 \(N, M \le 2\times 10^ ......
POD 题解
考虑每种颜色都只在一条链上出现这个限制。 考虑使用随机化 \(\text{hash}\),我们对每个点随机一个权值,使得每种颜色所有点异或值为 \(0\)。 这样一种颜色如果只在一条链上,那对两条链 \(\text{hash}\) 异或值的贡献就是 \(0\),否则就是两个随机值。 这样如果存在一个 ......
2023年石门中学NOIP模拟测试(2023.10.12)
又被打爆... T1 \(n\leq 10^3,q\leq 3\times 10^5\) 签到。竖着和斜着差分一下,最后从左往右扫一遍做完。 T2 做不出来这个显得很弱智...其实可以将整个游戏看成二叉树,然后每次的分左右儿子取决于 \(b_i\) 的倍数与否,接下来每一层的取值就看奇偶是 \(\t ......
T2【noip赛前20天冲刺集训 day4】正在打模拟赛
@@ 【noip赛前20天冲刺集训 day4】正在打模拟赛 @@ 题目描述 给定一棵包含 n 个点的树,每条边都有权值,同时给定一个整数 k。定义一个树上连通块的权值为其中边权之和。你需要求解满足以下条件的树上连通块的权值最大值:这个连通块至多包含一个度数大于 k 的点。 注意,这里的度数指的是连通 ......
CF938F Erasing Substrings 题解
Erasing Substrings 一个神奇的想法是设 \(f_{i,j}\) 表示在位置 \([1,i]\) 中,我们删去了长度为 \(2^k(k\in j)\) 的一些串,所能得到的最小字典序。使用二分加哈希可以做到 \(O(n^2\log^2 n)\),无法承受。 发现对于状态 \(f_{i ......
[ARC067F] Yakiniku Restaurants 题解
Yakiniku Restaurants 明显在最优方案中,行走方式一定是从一条线段的一端走到另一端,不回头。 于是设 \(f[i,j]\) 表示从 \(i\) 走到 \(j\) 的最优代价。明显,该代价对于不同的券相互独立。故我们依次考虑每一张券。 我们发现,假设有一张位置 \(k\) 的券,则所 ......
[AGC013E] Placing Squares 题解
Placing Squares 关键是将问题从抽象的“正方形面积”转为具象的形式:一段长度为 \(d\) 的区间,有两个不同的小球要放进去,则总放置方案就是 \(d^2\) ,且不同的区间间方案是通过乘法原理结合的,刚好是题目中 \(\prod d^2\) 的形式。 于是我们可以设计 DP:设 \( ......
洛谷P3713 [BJOI2017] 机动训练 题解
机动训练 这题的瓶颈,在于把 \(a_i^2\) 看作 \(\sum\limits_{i=1}^{a_i}\sum\limits_{j=1}^{a_i}1\),然后我们就可以看成“两两相同的机动路径都能贡献 1”。于是我们设 \(f_{x1,y1,x2,y2}\) 表示两条起点为 \((x1,y1) ......
P1864 [NOI2009] 二叉查找树 题解
二叉查找树 首先该树的中序遍历是唯一可以确定的(直接按照数据值排序即可)。 然后,因为权值可以被修改成一切实数,故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示: 区间 \([l,r]\) 中的所有东西构成了一棵子树,且树中最小权值不小于 \( ......
[AGC030F] Permutation and Minimum 题解
Permutation and Minimum 看到 300 的数据范围,再加上计数题,很容易就往计数 DP 方向去想。 为方便,我们将 \(n\) 乘二。 因为是两个位置取 \(\min\),于是我们便想到从小往大把每个数填入序列。于是DP数组第一维的意义便出来了:当前已经填入了前 \(i\) 小 ......
CF261D Maxim and Increasing Subsequence 题解
Maxim and Increasing Subsequence 首先,我们可以发现,当这个重复次数很大的时候,答案就等于序列中出现的不同权值个数。实际上,这个“很大”就可以被当作“大于等于不同权值个数”。 不同权值个数实际上是 \(\min(n,m)\) 级别的,其中 \(n\) 是序列长度,\( ......
CF979E Kuro and Topological Parity 题解
Kuro and Topological Parity 我们考虑在一张染色完成的图里,我们连上了一条边,会有何影响? \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边,但是出发点是个偶点(即有偶数条路径以其为终点的节点),终点的路径数增加了, ......
洛谷P3607 [USACO17JAN] Subsequence Reversal P 题解
Subsequence Reversal P 思路: 发现,翻转一个子序列,就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示: \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为: \(L>R\) 时, \(f=-\inft ......
洛谷P3576 [POI2014] MRO-Ant colony 题解
MRO-Ant colony 根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\),我们可以反 ......
CF264B Good Sequences 题解
Good Sequences 状态很显然,设 \(f[i]\) 表示位置 \(i\) 的最长长度。 关键是转移,暴力转移是 \(O(n^2)\) 的,我们必须找到一个更优秀的转移。 因为一个数的质因子数量是 \(O(\log n)\) 的,而只有和这个数具有相同质因子的数是可以转移的; 因此我们可以 ......
CF908D New Year and Arbitrary Arrangement 题解
New Year and Arbitrary Arrangement 思路: 期望题果然还是恶心呀! 我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便,设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfra ......
洛谷P3118 [USACO15JAN] Moovie Mooving G 题解
Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场(注意是场,不是部)电影时,已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了, \(21\%\)。 发现当一场电影结束后,无论这一场是在哪里看的都没关系。 ......
2020,2021 年 CF 简单题精选 做题记录
2023.10.12 开坑,打了几场 div.2 之后一直觉得这方面水平差太多,今天刚好在洛谷看到这个题单就准备开始做了,里面从黄到黑都有,我会尽量都做,并在这里记录。总共 49 题,我可能平时有时间就做一两题,估计是个长期坑了((。 题单链接 [Y] 表示独立完成,[N] 表示看题解之后完成。 ......
题解 AtCoder wtf22_day1_b【Non-Overlapping Swaps】
给定一个排列,要求交换最多 $n-1$ 对元素,使得这个排列变成 [1,2,...,n] 的有序排列。
当然没有那么简单,对于交换还是有限制的,对于相邻的两次交换,不妨叫做 $(l_i, r_i)$ 和 $(l_{i+1}, r_{i+1})$,必须满足**这两个交换所对应的区间,没有交集**,即... ......