Blog E

路漫漫其修远兮,吾将上下而求索。

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_{...

PKUSC2021题解

T1T2

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

考试注意

惨痛教训

重要公式 gyh 总结 矩阵树 无向图 矩阵形式: $A(i,i)=\deg(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重边数量)}$ 有向图 矩阵形式: 内向树:$A_{out}(i,i)=\deg_{out}(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重边数量)}$ 外向树:$A_{in}(i,i)=\deg_{in}(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重...

【题解】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...

【题解】丁香之路

奇妙

感觉这题的思路非常奇妙,就算会做了也完全不知道为啥要这么想。。。 题意 有一个 $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$ 的欧拉路径 那么就有符合题目要求的一条路径存在...

博科摆

物理作业

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

讲题

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=...

国王饮水记

一道 nb 题

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

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}...

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...

icon