Blog E

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

点分治水题

遇事不决点分治

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

四边形不等式优化学习笔记

学会,但没完全学会

参考 肖然的博客 四边形不等式 原形式 有一个双变量函数 $f(x,y)$,如果对于 $\forall a\le b\le c\le d$,都满足 $f(a,d)+f(b,c)\ge f(a,c)+f(b,d)$ 则称其满足 四边形不等式。 等价形式 对于 $\forall a<b$,都有 $f(a,b+1)+f(a+1,b)\ge f(a,b)+f(a+1,b+1)$。 这一形式的必要性显然,下证其充分性: 若 $a+1<b$ 则: \[\begin{aligned} f(a,b+1)+f(a+1,b)&\ge f(a,b)+f(a+...

斯特林数学习笔记

怎么感觉组合数用 C 几几更方便写

第一类斯特林数 几何意义 把 n 各不同的数放进为 k 个环的方案数,用 $\begin{bmatrix}n\cr k\end{bmatrix}$ 表示。 代数意义 \[\begin{aligned} x^{\overline{n}}&=\sum_{i=1}^n \begin{bmatrix}n\cr i\end{bmatrix}x^i\cr x^{\underline{n}}&=\sum_{i=1}^n (-1)^{n-i}\begin{bmatrix}n\cr i\end{bmatrix}x^i \end{aligned}\] 计算方式 $O(nk)$ 递推:...

斜率优化学习笔记

顺便学了个李超树

问题形式 用来优化一类 dp,其转移方程满足: \[dp_i=f_i(\max_{j<i}(k_j\times x_i+b_j))\] (式子中取 min 也可,与 max 类似,不再赘述) 其中 $k_j,b_j$ 是只与 j 相关的数,$x_i$ 是只与 i 相关的数,$f_i$ 是只与 i 有关的函数。 斜率优化就是优化的求 $\max_{j<i}(k_j\times x_i+b_j)$ 的过程。

【题解】寿司晚宴

最优解!

upd 2021.6.18: 修改公式符号,更加形式化,添加 50 分做法 介绍一种 $O(n \times 3^8)$ 的做法,目前是所有非打表代码中的最优解,其实只是把其他题解中的算法优化了一下。 定义 $fac_i$ 表示 i 的质因数集合 $P=\{x\mid x\ \text{is prime},\ x\le n\}$ 暴力 1 这题的暴力有很多种,在此只介绍可以优化成正解的暴力。 两个数互质,等效于他们没有共同的质因子,所以只需把每个数都分解质质因数,如下 dp: 状态:$dp(s1,s2)$ 表示考虑前 i 个数(i 被滚动掉了),小...

PKUSC游记

海星

Day 0 坐火车到余姚,晚上到余姚宾馆,颓了一会,复习了下教练说往年都考了的ntt和线段树合并,又打了一遍网络流和sa(然而都没用上),就睡觉了。 Day 1 到考场试机发现是windows系统,好在提供gvim安装包,不过由于我平时都用的是neovim,对gvim的配置不太熟,只好又现查了查,改了下之前背的vimrc。 第一题,发现每个矩阵只和它前一个矩阵每行每列的和有关,于是就推了下这个东西的递推方法,矩阵快速幂搞定因为交错题又wa又re的调了一个小时。 第二题,先写了个暴力,发现整体修改的部分分相当是把询问的l,r移一下,于是写了个st表,把询问离线之后从后往前,在单调...

一种很优雅的高斯消元写法

类似线性基

rt,自己胡出来的算法。用类似线性基的写法写,代码简短,常数小,并且对无解和无穷解的判断都很简单。 以下为毒瘤题 P2455 线性方程组 代码(之前用正常写法怎么都过不了,面向数据才过的。。): #include<bits/stdc++.h> using namespace std; const int MXN=105; const double eps=1e-8; int n; bool used[MXN]; double arr[MXN][MXN],tmp[MXN]; inline bool is0(double x){return fabs(x)<=eps;}...

USACO 2021 US Open 铂金组 T1 题解

想了挺久

United Cows of Farmer John 题意: 给定一个长度为 n 的数列 $a_i$,求符合下列条件的三元组 ${i,j,k}$ 个数: $1\le i < j < k \le n$ $a_i,a_j,a_k$ 的值在 $a_{[i,k]}$ 各只出现一次(即他们自己)。 思路: 为了方便描述,我们称 $a_i$ 为 i 点的颜色,记 $pre_i$ 表示 $a_i$ 的前驱(即 i 之前与 $a_i$ 相同的最后一个数),记集合 $last$ 表示右端点扫描到 r 时,每个颜色最后一次出现的位置。 朴素想法 考虑固定右端点 r,然后枚举左...

icon