zcmimi's blog
avatar
zc
2020-03-07 20:32:00
查看原题

点击跳转

扩展中国剩余定理

给定方程组:

\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ m_n) \end{cases}

求最小的非负整数x

假设我们求出了前i-1组的解x_{i-1}

M=\operatorname{lcm}(m_1,m_2,\cdots,m_{i-1})

x_{i-1}+\lambda M \equiv a_{i-1} \pmod{m_{i-1}}(\lambda \in \Z)

那么我们需要求出最小的非负整数t使:

x_{i-1}+tM\equiv a_i \pmod{m_i}

也就是Mt\equiv a_i-x_{i-1} \pmod{m_i}

可以使用Exgcd求解t (ax\equiv c \pmod b)

如果无解,则整个方程误解

若有解,x_i=x_{i-1}+tM

avatar
zc
2020-03-02 02:05:00
查看原题

点击跳转

线段树合并的时候取\min(\text{交换前},\text{交换后})

avatar
zc
2020-03-01 19:36:00
查看原题

点击跳转

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并

avatar
zc
2020-03-01 14:52:00
查看原题

点击跳转

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,lca(x,y),f_{lca(x,y)}w位置-1

统计的时候不断向上线段树合并

具体看代码

avatar
zc
2020-03-01 11:57:00
查看原题

点击跳转

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

avatar
zc
2020-03-01 00:37:00
查看原题

点击跳转

题意:

给一棵trie树,可以删掉某一层的所有边

求删掉哪一层边后合并出的trie树最小?

解法:

trie的启发式合并

avatar
zc
2020-02-29 13:32:00
查看原题

点击跳转

题目的意思就是相同子树中的点不能分配到同一段内存

每个点都开一个大根堆

合并一个点和它的子节点的时候最大值互相对应

启发式合并

具体看代码

avatar
zc
2020-02-28 21:34:00
查看原题

点击跳转

其实可以说是前向星

每次都把短的链表接到长的链表上

统计短的链表上每个元素改变后造成的影响

avatar
zc
2020-02-28 17:31:00
查看原题

点击跳转

可以想到贪心:

如果目前有可以摧毁的目标水晶,那么摧毁最靠后的

否则摧毁第一个水晶

证明:

如果一个水晶目前无法摧毁,它必须等前面若干个水晶被摧毁它才能移动到目标位置

所以当目标水晶没有可以摧毁的时候,摧毁序列第一个可以移动最多的目标水晶

当有超过一个目标水晶可以摧毁的时候,从后往前摧毁显然是最优的

那么要如何实现这个贪心呢?

很容易想到数据结构

  1. 平衡树暴力操作: 数据范围3\times 10^6,显然是不行的

  2. 线段树 目标水晶最多1.5\times 10^6,且线段树常数不大,可行

实现:

  1. 线段树维护

维护d_1,d_2,\dots,d_{cnt}表示目标水晶到可以摧毁的位置的距离

维护最小值

若最小值为0,这找到最靠后的d_x=0,摧毁,也就是距离赋值为无穷大,然后将d_i,i\in[x+1,cnt]都减去1

否则一直摧毁第一个水晶直到最小值为0,也就是所有d_i都减去min(d_i)

代码如下:

avatar
zc
2020-02-27 22:12:00
查看原题

点击跳转

能凑出的钱: 使用多重背包(二进制优化)

找零: 使用完全背包

27/73
Search
search