Blog E

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

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

点分治水题

遇事不决点分治

CF1260F Colored Tree 题意 一颗有 n 个节点的树,每个节点 v 有颜色 $c_v$,这个染色方案的权值为 $\sum\limits_{u,v\in[1,n],v>u,c_v=c_u}\operatorname{dis}{(u,v)}$。 现在知道每个节点 v 可以染成 $[l_v,r_v]$ 中任意颜色,求所有染色方案的权值之和。 $n\le 10^5$,时限 2.5 秒。 思路 一个显然的想法是考虑每一条路径的贡献,于是自然的想到点分治。考虑过分治中心一条路径的贡献(为方便起见,后文都算的是权值期望)。 显然贡献为: \[(d_u+d_v...

浅谈容斥

不会数数

【本文未完待续】 在前几周学长教了我一道容斥题之后,我发现:我好像没学过容斥! 从全错排开始 全错排有一个通项公式,这个式子固然可以用组合方式证明,但这里用代数方式再来推一遍,更加本质一些。 \[\begin{aligned} Ans & = \sum _{所有排列p}\prod_{i = 1}^n [p_i\neq i] \cr 因为&[p_i\neq i]的条件不好弄,考虑将其转化为[p_i = i]\cr & = \sum _{所有排列p}\prod_{i = 1}^n (1-[p_i = i])\cr & = \sum _{所有...

浅谈tarjan

野鸡题解

我向来玩不明白 Tarjan,每年复习都要理解半天,再写半天,再调半天。 每年都会看到一些野鸡博客,搞得我迷惑半天,今年也是,最终还得感谢 @_Guoyh_ 帮我搞明白了。 为了避免之后继续迷惑,我打算把我迷惑的点记下来。 注意:本博客是作者自己的理解,可能也是野鸡博客,如有错误,还请指出。 代码第6行的含义 inline void tj(int p){ dfn[p]=low[p]=++dfsc; st.push(p),instk[p]=1; for(int nx:e[p]){ if(!dfn[nx])tj(nx),low[p]=min(...

icon