当前位置: 首页 > news >正文

solutions

edit

做個備份

  • 構成樹考慮每個節點的父親的選擇方法。
  • 區間移動一個,考慮滑動窗口,即使單調隊列。
  • 點分治每個子樹的處理按照從小到大來。
  • 有顏色的貢獻,按照排序處理,因爲每個前面只有可能一種相同顔色。
  • 有固定的出現次數,思慮鴿巢原理。處理最簡情況。
  • 弄成將成爲以後必選的形式(題別讀錯)。
  • 博弈的選擇可能是一段連續的區間,可能區間的最值為答案(都遇見 \(2\) 次了)
  • 差分約束的轉換關係通常爲:有不等關係至少、至多;區間信息的這種關係,最優先考慮前綴和構造相減。
  • 差分約束,跑最短路求最大值;最長路求最小值。
  • 差分约束还应考虑每一个单点的限制是什么。
  • 可以從後往前做 DP,就有預知性。
  • 平均數、中位數二分答案,值域稍微大點
  • 區間的權值極差問題,考慮尺取法

一般是求解最小值, 由於中間取值不管,先排序, r 指針一直跳,判斷解,l 指針跳。(因爲前面小的取不到最小值,後面的話就會更大)

  • 偏序問題先排序確認某一維的合法。
  • 括號的匹配,有如下合法限制:
    \(sum_r-sum_{l-1}=0,\forall sum_i-sum_{l-1}\geq0\)
  • 有兩端點這類問題可以枚舉一個端點,然後另一個端點隨之移動,并判斷。(好像也是遇見了多次)
  • 唐死了,有時候真的補補 dp
  • \(\max\min\{f_i,f_j\}\),盡可能使 \(f_i,f_j\) 接近,因爲這樣使得取最小值不會太小,就保證最大值更大
  • 你發現 dp 答案不會太大時,可以把答案作爲一個狀態
  • 遍歷一個點的相鄰坐標,直接使用循環展開。(在可能充不過的情況下)
  • dp 狀態設計考慮所有的情況(0/1 選不選、在 A/B 裏面……)
  • 求極差的最小值,且可以支持修改(只會是使一個數增大),從大的入手(他被別的更改指揮使極差更大?所以用它更新小的),判斷他的周圍,更新後丟進隊列裏面,重複即可
  • 帶有操縱的 dp,把操縱次數設入狀態
  • 既然帶有操縱兒子,那麽可能還要設計這個與父親的是否操縱的狀態(\(f_{u,i,0/1}\) 表示 \(u\) 的子樹切斷了 \(i\) 條邊切不切父親)
  • 多個 \(a_i=a_{a_i}\) 的限制需要滿足,就把下標連邊 \(i\rightarrow a_i\)
  • 固定了左端點,向右遷越區間 \(\gcd\) 減少較快,減少 \(\log V\) 次就為 \(1\) 了,而且只有 \(\log V\)\(\gcd\)
  • 序列選數、有限制,求最值,就有時候可以 dp
  • 模數 \(p\) 為質數,那麽 \(a^b \equiv a^{b~\text{mod}~{p-1}}~(\text{mod}~p)\),就是用來降冪的
  • 矩陣的階:若 \(d\) 為階,且最小,滿足 \(A^d=I~(\text{mod}~p)\),所以有 \(A^b\equiv A^{b~\text{mod}~d}~(\text{mod}~p)\),感覺絕大多數的情況降冪是用模數 \(p-1\),但任要考慮到 \(p\) 為模數的情況
  • 每個 \(i\) 可以給 \(j\) 加貢獻,考慮每個 \(i\) 最終得到的貢獻
  • 選不選的,選那些,使用 dp 背包
  • 組合數的一般遞推:\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)
  • \(C_n^m~\text{mod}~2=1\) 當且僅當二進制下 \(m\)\(n\) 的子集,\(m~\text{bitand}~n=m\)
  • \(n\times 2^{n-1}=\sum_{i=1}^n i\times C_n^i\)
  • 計數把每一位的貢獻算出,所有位再乘起來
  • 又做到了小狀壓的題目,區間節點是一個二進制數,表示一些訊息,區間的合併如果是求並集、交集,使用 \(\text{bitset}\) 較為容易做基礎,可用 \(\text{ST}\) 表,線段樹
  • 區間 \(\text{mex}\)\(O(Q(\sqrt N+\sqrt V))\) 做法,莫隊離線下來,值域分塊維護
  • 莫隊塊長至少為 \(1\),不然除以塊長為 \(0\) 可能會\(\text{\color{#9933FF} RE}\)
  • 區間貢獻考慮轉換成前綴貢獻,維護這個前綴貢獻
  • 循環序列複製成雙倍
  • 後綴數組的 \(\text{height}\) 運用,\(\text{lcp}(sa_i,sa_j)=\min\{\text{height}_{i+1,..,j}\}\)
  • 求字符串的不同子串個數,是總個數 \(\frac{n(n+1)}{2}\) 減去重的 \(\sum_{i=2}^n \text{height}_i\)
  • AC 自動機上 dp 的套路狀態是:設 \(f_{i,j}\) 表示在自動機上走了 \(i\) 步,在 \(j\) 節點
  • \(\text{dep}[\text{lca(u, v)}]\) 可以表示為將 \(u\) 到根的路徑都 \(+1\),然後求 \(v\) 到根的路徑和
  • 樹有了 \(\text{dfn}\) 序,就變得有萬能了,支持一些數據結構
  • 區間處理有可能離線
  • 樹加邊詢問操作,將加邊都執行,離線按照詢問處理
  • 線段樹合併,合併玩的點要現場使用,不然參與父節點的合併可能會被覆蓋一些節點
  • 哎不是,重心的一些性質:如果 \(u\)\(\text{root}\) 子樹的中心,則:\(u\)\(\text{root}\) 的重鏈上,且最深,滿足 \(2\times sz_u>sz_{\text{root}}\)(除 \(\text{root}\) 為葉子節點),一般來説就是因爲重鏈上可以求 \(dfn\) 序,且是連續的,所以還可以二分求答案
  • 以樹的重心為根時,所有子樹的大小都不超過整棵樹大小的一半
  • 樹鍊剖分的點權維護邊權,在詢問兩點路徑時,會把它們 \(\text{lca}\) 的點所對應邊改動或查詢到,所以要特殊處理
  • 斐波那契的維護多爲矩陣轉移
  • \(\text{Dsu~on~Tree}\) 具體步驟是:遞歸所有輕兒子,答案貢獻更新後要刪除;遞歸重兒子,保留答案貢獻;兒子遍歷完,重新計算自己和輕兒子子樹的貢獻;如果是父節點的輕兒子,則刪除此子樹的所有貢獻,回溯
  • \(\text{Dsu~on~Tree}\) 適合用於求子樹的信息
  • \(k\) 個點的最短路的最小值求法把一些點分別放進 \(S,T\) 集合,邊權為 \(0\),那麼從 \(S\)\(T\) 的最短路就是有可能是兩個點的最短路最小值
    如何分配點進入 \(S,T\) 集合,考慮枚舉 \(n\) 的二進制位 \(i\),以 \(k_j\) 的二進制第 \(i\) 位是否為 \(1\) 放入集合。
    那麼如果 \(x,y\) 是答案的話,則它們在不同集合,二進制有一位不同,就統計到了。
    如若不是,則有滿足上述的條件的其他點成為答案
  • 樹鍊的點或邊是否能構成回文,記 \(dis_u\) 為從根到 \(u\) 的字母構成的集合,用一個二進制數表示,二進制位 \(i\)\(1\) 表示第 \(i\) 位是出現奇數次,所以 \(dis_u\oplus dis_v\)\(0\) 或 二進制位只有一個 \(1\) 就是能構成回文,對 \(u\) 的子樹,先求解,再加成貢獻,因為不然可能加到自己子樹的值
  • 邊聯通分量可以通過重定向每一條邊使它變成一個強連通分量
  • 圖進行了tarjan操作,就變成,便於操作
  • 選最優情況的題型有可能用優先隊列
http://www.hskmm.com/?act=detail&tid=28197

相关文章:

  • 技术面:Spring (事务传播机制、事务失效的原因、BeanFactory和FactoryBean的关系)
  • 安装与配置MySQL 8 on Ubuntu,包括权限授予、数据库备份及远程连接
  • 04-最简单的字符设备驱动
  • 完整教程:手机可视化方案(针对浓度识别)
  • AI元人文系列文章:决策范式与无为而治
  • SAP导入证书
  • Kubernetes存储卷:保障有状态应用的数据持久化
  • MySQL的查询操作语法要点
  • 华为链路聚合配置
  • 手机adb 调试自己
  • 离线安装 mysql
  • what is a good parent
  • 2025 年公共/商场/学校/地铁/电影院/会所/机场/卫生间隔断厂家选购指南:优质厂商推荐与实用选择策略
  • 为什么不该用 Double 表示金额及解决方案
  • Windows开发环境安装备忘录
  • Vue.use(Vuex)
  • [Gym-100343E]Convex Permutominoes 题解
  • MyBatis 中的动态 SQL 的相关使用方法(Javaee/MyBatis) - 教程
  • 网络优化问题
  • Java环境安装备忘录
  • 深入解析:【Spring MVC终极指南】一文掌握请求处理与响应!从Servlet原生方式到SpringMVC高效优雅写法
  • foobar2000 v2.25.2 汉化版
  • 比特币地址投毒攻击深度剖析
  • 为什么大家都爱用微擎?这几点真的太香了
  • 【JS逆向百例】某坤行 1101,雪球 1038,新 acw_sc__v2 逆向分析
  • JAVA 的模板方法模式解析
  • 《构建之法-现代软件工程》 -阅读和提问作业1
  • 计算机视觉与AI在人体成分分析中的技术突破
  • 2024-网鼎杯web-PyBlockly
  • 关于微信小程序申请地理位置接口申请