Blog E

【题解】CF1710B Rain

抽象

说一个代码简单的做法。本题解数形结合，容易理解。题解首先，题目所求就是上述不等式对哪个 $i$ 成立。发现式中只有第 $2$ 项是随着 $i$ 而变化的。而第 $1$ 项虽然不变，但是较为复杂，与第 $2$ 项相减的结果不好快速计算，因此不妨将第 $2$ 项移项到右边。是不是突然发现这下不等式两边都比较简单了？如果看不出来，我们不妨把式子左右的图叠在一起看：下文中称 $(x_i,p_i+m)$ 点为蓝色山顶（图中标出）我们考虑右边能把左边盖住的条件：对于左边高度小于等于 $m$ 的点，显然不用考虑对于左边高度大于 $m$ 的某一点，蓝色...

Posted by ethan-zhou on July 27, 2022

NOI2016题解

题型新颖

T1 线段题意 $n$ 个区间，从其中选出 $m$ 个，使得全部 $m$ 个线段交非空。求这 m 个线段长度极差的最小值。 \[m\le n \le 5\times 10^5\] 思路线段按长度排序，随后双指针。开线段树表示每个位置被覆盖次数，最大值大于 $m$ 时合法。 T2 国王饮水记 (见之前题解) T3 旷野大计算题意：略一些关于 $S(x)$ 的性质（注意 S 函数非常有用）： $S^\prime(x)=\frac{e^{-x}}{(1+e^{-x})^2}$ $\lim_{x\to 0}S(x)=\frac 12$ $\lim_...

Posted by ethan-zhou on May 29, 2022

PKUSC2021题解

T1T2

一棵树题意题解 $k=0$ 不难，略。一个显然的想法是枚举断掉的边，然后看每条边的贡献。贡献分为两类，一类是新加的边的块间贡献: 这个不难算，另外一类是原先的边的块内贡献。不妨设虚线边断开，实线边把一个连通块分为大小为 $a,b$ 的两块，则这条实线边的贡献是上面的式子。于是在枚举了虚线边之后，分子树内，祖先，既非子树也非祖先三种情况讨论，不妨设 a 是虚线边较深的端点，b 是实线边较深的端点：可以发现，三个贡献的式子后两项都只和 a 有关，前两项都可以展开成和 b 有关的二次多项式，因此只需要维护下子树内，祖先上的 sz 的和，sz 的平...

Posted by ethan-zhou on May 16, 2022

【题解】P5979 [PA2014]Druzyny

考场上想出，挺有成就感

说一个 $O(n\log^2 n)$ 的 cdq 分治做法，常数不大，不用分类讨论，较为好写。一些符号记 $\operatorname{mxl}(l,r)$ 表示下标在 $l$ 到 $r$ 之间的所有区间的左端点最大值，$\operatorname{mnr}(l,r)$ 意义类似。记 $\operatorname{rng}(l,r)=[\operatorname{mxl}(l,r),\operatorname{mnr}(l,r)]$。暴戾首先是一个简单的 $O(n^2)$ dp： \[dp_i=1+\max_{[j<i]\land [(i-j)\in...

Posted by ethan-zhou on April 3, 2022

【题解】丁香之路

奇妙

感觉这题的思路非常奇妙，就算会做了也完全不知道为啥要这么想。。。题意有一个 $n$ 个点的无向完全图，边 $i\leftrightarrow j$ 的边权为 $|i-j|$，强制经过指定的 $m$ 条边，求起点为 $s$，终点为 $i\in[1,n]$ 的最短路径。$n\le 2500,m\le \frac{n(n-1)}2$。思路考虑在一个可重无向边集 $E$，如果： $\text{必须经过的}\ m\ \text{条边}\subseteq E$ 存在一条 $s\leftrightsquigarrow i$ 的欧拉路径那么就有符合题目要求的一条路径存在...

Posted by ethan-zhou on March 4, 2022

博科摆

物理作业

（所有插图系作者手绘，文字由作者原创）假象一个小人站在一个逆时针转动的旋转木马上，小人会感受到一个远离旋转木马的中心的力。这就是离心力，并不存在一个实在的东西对小人施加这个力，但是由于小人站在旋转木马这个旋转参考系下，惯性会使小人感受到这种力，这种力就叫惯性力。然而，如果小人还在旋转木马上走动，除了刚才的离心力小人还会受到另外一个力：它指向小人运动方向的的右侧，并与小人的运动方向垂直。这就是科氏力，另外一种惯性力。万一旋转木马是顺时针转的呢？假如人在竖直方向也有运动呢（比如在旋转木马上跳来跳去）？科氏力的方向又会怎样变化呢？事实上，我们有一个通用的方法来判断。首先...

Posted by ethan-zhou on February 20, 2022

讲题

P5323 光线两个玻璃的透光率和反光率可以合并，如下列式解方程即可： \[\left\{ \begin{aligned} B&=Ap_1+Dq_1\cr D&=Bq_2\cr C&=Bp_2\cr E&=Dp_1+aq_1 \end{aligned} \right.\] 解得： \[\left\{ \begin{aligned} p_{12}&=\frac CA=\frac{p_1p_2}{1-q_1q_2}\cr q_{12}&=\frac EA=...

Posted by ethan-zhou on February 14, 2022

国王饮水记

一道 nb 题

题意有一个长度为 n 的数组 H（元素互不相同），你可以进行 m 次操作，每次取若干元素，把他们都赋值为他们的平均值。求 $H_1$ 最终最大能达到多少，要求计算过程中保留到小数点后 p 位。简单观察贪心一下，大概就能感受出来最优解的搞法：将 $H_{[2,n]}$ 排序，选一个后缀，并划分为 m 个区间。把 $H_1$ 从小到大依次和这些区间内的数联通。这个感觉是对的，但是严格证明需要以下结论：小于等于 $H_1$ 的数没用（显然）假如每次操作都包含 $H_1$，每个数不会选两次（操作过之后就小于等于 $H_1$ 了）存在一个最优...

Posted by ethan-zhou on February 13, 2022

max加或卷积

卡常不过

定义 $C=A\times B$ 满足 $C_i=\max_{j\lor k=i}(A_j+B_k)$。约定 $\operatorname{concat}(A,B)$ 表示把 A，B 数组接起来，$\max(A,B)$ 表示 A，B 按位取 max。考虑用类似 karatsuba 的搞法。假设 A，B 长度都是 $2^n$，需要计算 $C=A\times B$，考虑按照下标的二进制最高位把 A,B,C 分成前后两半，即： \[\begin{aligned} A=\operatorname{concat}(A_0,A_1)\cr B=\operatorname{concat}...

Posted by ethan-zhou on February 11, 2022

USACO 2022 一月月赛铂金组 T1 题解

1 个 log，空间线性做法

题意给定一个序列 A，每次操作可以交换值相差不超过 K 的相邻元素。允许操作任意多次，求字典序最小的最终序列。暴力进行一个贪心，我们从 1 到 n，最小化最终序列的每一位。对于第 i 项，找到满足： \[j\in[i,n]且\forall k\in[i,j),|A_j-A_k|\le K\] 的最小元素 $A_k$，一路交换到 $A_i$ 的位置去。可以证明，使用任何其他搞法都不能得到字典序更小的答案。证明：不妨称序列中所有与 $A_i$ 相差超过 K 的元素为“障碍”。显然，障碍不能与 $A_i$ 交换。因此，在任意时刻，在数列中位于 $A_i...

Posted by ethan-zhou on January 29, 2022