\(\bf Coding\ Notes\ (From\ 2022.11.11)\)
\(\bf Some\ Notes\ To\ Help\ Me\ Do\ Better!\)
\(\bf My\ Achievements:(Only\ Questions\ Which\ Has\ A\ Difficulty\ Judgement\ By\ Luogu\ will\ be\ Included)\)
\(\bf\color{#FE4C61}{Red}\) | \(\bf\color{#F39C11}{Orange}\) | \(\bf\color{#FFC116}{Yellow}\) | \(\bf\color{#52C41A}{Green}\) | \(\bf\color{#3498DB}{Blue}\) | \(\bf\color{#9D3DCF}{Purple}\) | \(\bf\color{#0E1D69}{Black}\) | \(\bf\color{#BFBFBF}{Grey}\) | |
---|---|---|---|---|---|---|---|---|
\(\bf Number\) | \(\bf\color{#FE4C61}{2}\) | \(\bf\color{#F39C11}{8}\) | \(\bf\color{#FFC116}{10}\) | \(\bf\color{#52C41A}{10}\) | \(\bf\color{#3498DB}{14}\) | \(\bf\color{#9D3DCF}{8}\) | \(\bf\color{#0E1D69}{0}\) | \(\bf\color{#BFBFBF}{5}\) |
\(\bf\color{#FE4C61}{Red}:\ CF1761A,\ CF1764A\)
\(\bf\color{#F39C11}{Orange}:\ P3378,\ CF1761B,\ P1540,\ CF1764B,\ CF1557B,\ P8918,\ P8924,\ P8925\)
\(\bf\color{#FFC116}{Yellow}:\ CF1761C,\ P5788,\ CF20C,\ CF1764C,\ P2880,\ P2251,\ P1816,\ CF1606C,\ P8306,\ P2580\)
\(\bf\color{#52C41A}{Green}:\ P2629,\ CF1764D,\ P8818,\ CF1617D1,\ P5656,\ UVA11526,\ P4343,\ CF1675F,\ CF1671E,\ P8926\)
\(\bf\color{#52C41A}{Green}:\ P8927\)
\(\bf\color{#3498DB}{Blue}:\ CF1761D,\ CF1761E,\ CF1764D,\ P3092,\ P2897,\ CF1747D,\ P3384,\ P3178,\ P8817,\ P3919\)
\(\bf\color{#3498DB}{Blue}:\ P2261,\ SP14168,\ P3396,\ P4551\)
\(\bf\color{#9D3DCF}{Purple}:\ P3850,\ P3278,\ P2042,\ P3165,\ P2710,\ P8819,\ P3203,\ CF13E\)
$\bf\color{#0E1D69}{Black}:\ $
\(\bf\color{#BFBFBF}{Grey}:\ CF1760A,\ CF1760B,\ CF1760C,\ CF1760G,\ CF1759G\)
\(\bf Part 1-Questions\ In\ Luogu\)
\(\bf 1.\ \color{#9D3DCF}P3850\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 利用平衡树结构确定唯一大小序列的特性和 merge()
默认左小右大的性质,可以不记录下标,只通过自动的寻找正确位置插入实现。
\(\bf 2.\ \color{#9D3DCF}P3278\)
\(\bf Knowledge:\) 带参数平衡树
\(\bf Tricks:\) 平衡树与线段树的 lazy
结合,维护移位和区间加乘。
\(\bf 3.\ \color{#9D3DCF}P2042\)
\(\bf Knowledge:\) 究极带参数平衡树
\(\bf Tricks:\) ①平衡树与线段树的 tag
结合,维护奆多操作。②一次插入许多数时 \(O(n)\) 建树再插入的方法。③ update
的时候需考虑是否需要判有无左/右子节点
\(\bf 4.\ \color{#9D3DCF}P3165\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 按排名分裂的平衡树可以利用维护 minn
以达到查询最小值在数列中的排名。(通过根左右的 minn
判断最小值在左子还是右子)
\(\bf 5.\ \color{#3498DB}P2897\)
\(\bf Knowledge:\) 神仙的单调思想模拟
\(\bf Tricks:\) 由于水从高到低流,又需要找到现在和接下来哪个水面在增加,可以利用单调思想(低的没填完不会填高的),每个平台只会被经过两次,达到 \(O(n)\)
\(\bf 6.\ \color{#9D3DCF}P8819\)
\(\bf Knowledge:\) 随机权值哈希
\(\bf Tricks:\) 随机赋值 \(w\) 数组,通过 \(a_1w_1+a_2w_2+\cdots+a_nw_n=\sum w_i\) 做到 \(O(1)\) 判断 \(a\) 数组全为 \(1\)。
判断动态数组相等 \(\texttt{Hash}\),若 \(w\) 随机,
\[\sum_{i=1}^n w_i\times a_i=\sum_{i=1}^n w_i\times b_i\to a_i=b_i \]\(\bf 7.\ \color{#9D3DCF}P3203\)
\(\bf Knowledge:\) 分块
\(\bf Tricks:\) 对于某些问题,需要从一个点更新到结尾,要么查询 \(O(n)\) 更改 \(O(1)\),要么更改 \(O(n)\) 查询 \(O(1)\),我们可以利用分块思想,每一个点只更新到段尾,尝试用段间进行关联求解,做到查询更改 \(O(\sqrt{n})\)(对两种暴力的折中)
\(\bf 8.\ \color{#3498DB}P4185\)
\(\bf Knowledge:\) 并查集
\(\bf Tricks:\) 对于非标准数据结构形式的题目,又有类似数据结构的特征,可以考虑离线并以特殊的顺序回答询问。
\(\bf Part 2-Questions\ In\ Codeforces\)
\(\bf \color{#5EB95E}{[1700,2100]:(Total:\ 6)}\ CF1760G,CF1761D,\ CF1764D,\ CF1747D,\ CF1617D1,\ CF1675F\)
\(\bf 1.\ \color{#3498DB}CF1761D\)
\(\bf Knowledge:\) 组合数,数学
\(\bf Tricks:\) 组合数题目需一层层去掉限制条件,变为朴素计数(主要是多做...)
\(\bf 2.\ \color{#3498DB}CF1761E\)
\(\bf Knowledge:\) 思维题
\(\bf Tricks:\) 从简单情况开始考虑(什么图 \(1\) 步搞定,什么图 \(2\) 步?)
\(\bf 3.\ \color{#3498DB}CF1765D\)
\(\bf Knowledge:\) 组合数,数学
\(\bf Tricks:\) 先通过设变量剥离限制条件,再处理影响最大的先算(比如本题的最后一个选的点,因为导致了超过一半连续,所以是特殊的点,应先考虑)
\(\bf 4.\ \color{#3498DB}CF1747D\)
\(\bf Knowledge:\) 思维题
\(\bf Tricks:\) 从简单情况开始考虑(什么序列 \(ans=-1\)?什么序列 \(ans=1\)?什么序列 \(ans=2\)?)
\(\bf Part 3-Questions\ In\ AtCoder\)
\(\bf Part 4-Questions\ In\ RMJ\)
\(\bf 1.\ \color{#3498DB}SP14168\)
\(\bf Knowledge:\) 整除分块
\(\bf Tricks:\) 遇到约数和不好考虑时可以考虑为转而枚举约数,可能能降到 \(O(\sqrt{n})\)。
\(\bf Part 5-Self-owned\ Questions\)
\(\bf 1.\ \color{#9D3DCF}T294199\)
\(\bf Knowledge:\) 图论,缩点,dfs
,二分答案
\(\bf Tricks:\) ①对于答案求 \(ans\) 极值,且 \(ans\) 取值只有一个转换点,可以考虑二分答案。(例如本题 \(k\),只会随着 \(k\) 变小而从 Yes
转为 No
,这样一个转换点)②对于树上 dp
需要用子节点值更新父亲节点的题目,可以 dfs
回溯过程中更新
\(\bf 1.\ \color{#9D3DCF}T297651\)
\(\bf Knowledge:\) 平衡树
\(\bf Tricks:\) 区间加等差数列,不一定要差分,也可以用首项 & 公差标记解决(具有可加性)
\(\bf 3.\ \color{#3498DB}T297652\)
\(\bf Knowledge:\) 线段树
\(\bf Tricks:\) 对于非标准线段树/平衡树形式的题目,又有类似数据结构的区间等特征,可以考虑离线并以特殊的顺序回答询问。
标签:bf,Knowledge,color,Notes,9D3DCF,Coding,3498DB,My,Tricks From: https://www.cnblogs.com/yinhy09-OI-blog/p/notes1.html