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

trick杂记 例题

会把一些不太有分类的trick放在这里,弄得好乱啊!
其实感觉大部分算不上trick,就是一些思考的方向)

  • 组合数学。一些决策对总贡献没有影响,可以先钦定它们,在该局面下考虑对总贡献有影响的决策。

    • CF2092E She knows...
      在本题中注意到角与中心没有贡献 钦定为白色 计算此时总贡献\(w\) 同时统计已经填好的棱数\(cnt\)
      \(ans=\begin{cases}2^{n\times m-k-1}&\text{if }cnt=(n-2+m-2)*2\\\begin{cases}2^{n\times m-k}&\text{if }w\equiv 0\pmod2\\0&\text{otherwise}\end{cases}&\text{otherwise}\end{cases}\)
  • 抓住一些运算(异或)的交换律。

    • CF2066C Bitwise Slides
      异或加有数相等,应当想到异或和为0。注意到不管怎么操作,总和是不变的,加上有两个数相等的条件,就固定了三个数中的一个。然后大胆设状态,根据转移发现可以压掉一维用map存,复杂度也是对的。
  • 对于交互次数比较少的交互题,试图寻找突破点(这似乎不是trick 是废话)

    • CF2066A Object Identification
  • 一些直接想到用堆来维护的题目 尝试寻找新加点的单调性 可能可以通过开多个队列去掉log

    • P2827 [NOIP 2016 提高组] 蚯蚓
    • P6033 [NOIP 2004 提高组] 合并果子 加强版
  • 对于一些二维的,特别是有关曼哈顿距离的题 可以先考虑一维,把\(x,y\)的贡献分开来,或者拆绝对值考虑

    • CF2122C Manhattan Pairs一维前后配对,方案不唯一。二维在满足\(x\)前后配对的同时可以做到\(y\)也前后配对。
    • P5987 [PA 2019] Terytoria 对于每一维都有选中间/两边的两种情况,而且两维互不影响,所以考虑拆开来做,最后把每一维的最大贡献乘起来即可。
  • 一些区间贡献像递推一样的柿子,或者直接就是递推:考虑矩乘

    • 「LibreOJ NOI Round #2」单枪匹马 首先可以注意到不管怎么做分数都是最简。暴力推导过程\([l+1,r]\)\([l,r]\)\(\frac{x}{y}\)\(\frac{a_l x+y}{x}\)用矩阵表示
      \(\begin{bmatrix}x&y\end{bmatrix}\times\begin{bmatrix}a_l&1\\1&0\end{bmatrix}=\begin{bmatrix}a_lx+y&x\end{bmatrix}\) 行列式不为0,矩阵可逆 可以预处理矩阵前缀积 \(O(1)\)查询。注意:矩乘只有结合律,没有交换律,一定要注意柿子的前后顺序。 \(A=A\times B \times C \times C^{-1}\times B^{-1}=(A\times B \times C )\times (C^{-1}\times B^{-1})\) 所以逆矩阵的前缀积要倒着做,统计答案的时候也要注意顺序,括号反而无所谓。code
  • 有目标状态的期望题,考虑目标状态和当前状态哪些操作是无意义的,相当于没操作。然后可能把每一步可以转化成几何随机变量,有效步数固定的话直接累加期望即可。

    • CF1753C Wish I Knew How to Sort 目标状态很明确是前\(k\)个0,后\(n-k\)个1,注意到只有选到前\(k\)个的1和后\(n-k\)个的1交换才对目标状态有贡献(如果同前/同后换了也没用 和没换都是计一次步数)。
  • 对一个序列多次进行一样的操作,尝试考虑下标为i的进行一次操作会去哪里。

    • P2054 [AHOI2005] 洗牌 进行一次操作后,\(i\)\(i\times 2 \bmod (n+1)\)\(M\)次操作后变成\(i\times 2^M \bmod (n+1)\),列出\(i\times 2^M \bmod \equiv L\),用exgcd求解即可
  • 特别是对于排列,一些题考虑最值的贡献/答案可以少一个限制计算并且若有决策无后效性,则可以从值域的角度考虑,从小到大/从大到小依次做,一边做一边删,不断转化成子问题。

    • P1081 [NOIP 2012 提高组] 开车旅行 离散化形成排列。存在经典问题:寻找左右第一个大于该数的位置。考虑对于最小值当前所有数都比其大,只要找左右第一个数即可,少了"大于"的限制。然后删除使用链表维护。
    • D. Stay or Mirror 先钦定每一对逆序对的贡献在镜像前较小处计算=>保证了决策的无后效性。考虑当前最小值,若不镜像贡献为前面个数,镜像则为后面个数,由于前面计算贡献的约定,保证当前位最优的贪心就是对的。这个题中不用真的删除,\(n^2\)乱跑就好了。code
  • 在某一进制的连续自然数上做的东西,有时候存在可以分治的性质,同时看到这个如果是计数的话也要想到数位dp

    • CF1982E Number of k-good subarrays 记搜,有点类似数位dp,考虑当前最高位是否填1分成两段,本来是要多维护两个信息(左右最长)然后合并,但是注意到左边一段的右端点即为其最大bit值,所以左边只可能全成立或全不成立,而右边也有类似的性质(全成立或到2的某次幂,具体看代码)code
  • 见到乘积不大于某个值的形式,想到数论分块,其中较小值不大于\(\sqrt{n}\)

    • 统计约数个数
    • CF2006D Iris and Adjacent Products先考虑两种操作类型怎么做最优。第一种显然只要做一次,答案是“最大,最小,次大,次小……”注意要先大后小(对于n为奇数的情况更优)。第二种显然是把最大数变为1 。考虑整个序列满足条件等价于\(\forall i \in [1,\sqrt k],cnt[1,i]\geq cnt( \lfloor \frac{k}{i+1}\rfloor,k ]\),注意其中n为奇数时有边界条件(中间可以多一个)。卡空间离线下来,枚举i直接前缀和就线性空间了。一开始考虑一点点加上去非常麻烦,不如直接当作多个不等式取一下max。code
  • 找规律,有可能前几个是特例,要接着找

    • CF1924C Fractal Origami 写出一些\(W,V\),发现之后差都不变了,尝试解释这个现象:发现每次折完有2的幂次层,再折一次,新加入的折痕被分成等长的两份,总的增加量,长度先除以\(\sqrt 2\),再乘上2,原理也是层数多了一倍。把W柿子是否含\(\sqrt2\)的项拆开来然后等比数列,最后\(W=(2^{\lfloor \frac{n}{2} \rfloor +1}-2 )+(2^{\lceil \frac{n}{2} \rceil}-2)\sqrt2,V=W+2\sqrt2\),答案分母有理化一下就好了,\(a=\lfloor \frac{n}{2} \rfloor+1 ,b= \lceil \frac{n}{2} \rceil, ans=\frac{2^{a+1}-4}{2^{2b+1}-4+2^{a+2}-2^{2a}}\),(事实上把\(a+\sqrt b\) 封装起来可以避免计算错误).整个题抓住了折叠的对称性,或者说原本的层数的折叠结果。
  • 一些与两个区间有关的查询,可以通过差分拆成4个只与两个值以及1相关的询问。

    • P5268 [SNOI2017] 一个简单的询问 看到区间某数出现次数考虑莫队,拆了直接做就行
  • 处理一些可以抵消的东西判断可行性的时候,或者只关注相对大小关系,赋成+1,-1,或者1,0,可以排除长度影响。注:两种赋法,-1是为了消除长度限制(抵消),另一种常用于关注相对大小的弱化

    • CF1486D Max Median 只关注相对大小关系。
    • P2824 [HEOI2016/TJOI2016] 排序
      二分答案 1.将最优性向可行性转换;2.弱化问题…… 一些题目可以直接对答案进行二分,变成只关注相对大小关系的问题。通常是这样转化之后可以大幅优化操作什么的。对于这个题来说缩小一点同样是trick,区间排序\(O(n \log n )\)=>01区间排序\(O(\log n)\)。线段树维护即可。
  • 对于\(\geq k\)的长度限制,枚举钦定k的那一段,通过前后缀预处理优化复杂度。

    • CF1486D Max Median check中做一遍前缀和以及前缀max,然后线性枚举。
  • 一些无单调性的题不能二分而可以枚举/有单调性的不二分而枚举 可能是check的东西在枚举(扫一遍)的时候反而可以继承 可维护。

    • P3963 [TJOI2013] 奖学金 (无单调性)中位数的本质是一半比它大,一半比它小。没有单调性,从大到小枚举,需要保证左右奖金最少的\(\lfloor \frac{n}{2} \rfloor\)个之和加当前奖金小于等于限制。用堆跑两遍预处理。
    • P3101 [USACO14JAN] Ski Course Rating G (有单调性)
  • 两两关系,如果顺序不重要,注重连通性/能否到达=>并查集(可以维护块的大小、连通,以及一些可以有顺序、权值的带权并查集);顺序重要,有权值,含最优化=>建图

    • CF87D Beautiful Road 一开始想的是向两头跑,找到第一个大于的。考虑怎么连的不重要,只要连通即可,所以用并查集维护,从小到大一点点加边(这个应该有点常见)。然后发现处理不了相等的边。一开始想分开来处理,但是发现根本分不开啊!因为可以起到连上别的块的作用,不止它本身被统计进来了。正解是通过第二关键字深度排序保证一个连通块已经连完了,将其大小记下来c,然后把本深度的全部连完之后,维护联通块大小p,\(c \times (p-c) \times 2\)
  • 多个做法和不同值的复杂度有关,如果这些值互相牵制,可以考虑每次挑最小的那个做。

    • P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping
  • 形如每位有若干种填的值,有些为无限制的条件。无限制的可以考虑加起来,有限制的同样也可以考虑容斥成无限制减填别的。

    • P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping
  • 每位值域不大,有些位可以填的是一个范围,有些位是确定的,考虑SOSDP(特别是二进制状压一些固定是0,一些0/1均可的时候)

    • P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping
  • 多个操作,从操作顺序考虑简化,比如先做完某种再做某种不影响答案。

    • CF2133E I Yearned For The Mines 先做操作2,再做操作1.
  • 一些有覆盖/推平意味的操作,最后一次操作有显著特征,考虑从后往前倒推。

    • P3100 [USACO14JAN] Building a Ski Course G 厉害的枚举题。这样覆盖之后最后一步是一个相同的方阵,找到过的在之后的几轮枚举中都可以充当。每次这样找,最后取每一步的min即可。对于每次找不要暴力,考虑以当前点为右下角的全为1/0的方阵可以通过继承而来。
      \(f_{0,i,j}=\begin{cases}0 &\text{if }a_{i,j}=1\\ min\{f_{0,i-1,j},f_{0,i,j-1},f_{0,i-1,j-1}\}+1 &\text{otherwise}\end{cases}\)
      同时为了避免永远在同一个地方,须保证每次找到的方阵右下角位置不同。 code
  • 对于很多操作都可以转化成邻项交换(并且带有一定限制)的形式,一般来说要方便很多。

    • CF1898E Sofia and Strings 对于区间排序,转化成相邻两项按字典序交换,这样相当于冒泡完成一段区间的排序(充分性),同时能在对一个元素操作的同时尽可能的保留原有顺序,(因为执行操作一定是在减少逆序对 减少最后序列的可能性 这样可以尽可能保留原本序列之后可能有用的相对顺序)。剩下的就比较好做了,考虑一个一个归位,肯定是移动当前最靠前相同字符的更优,然后把前面更小的删去。(这应该是一个比较典的可行性问题考虑模式,一位位满足的同时保证是对后面归位损耗最小的操作方式)。每次配对完记得把配到的东西删除。什么时候没有东西配就无解了。code
      还有错误示范。一开始把每一位都配好了,后面多的舍弃了。但忘记了存在把前面的删掉,后面的替补的情况。这么想可能是想到了没有出现过的可以先删这个性质,其实没啥用,警示我们不要死磕一个性质
    • AT_agc001_f [AGC001F] Wide Swap 把一个有交换距离限制的排列逆一下,变成临项交换,有差值绝对值限制,思考顺很多,\(O(n^2)\)冒泡一下,正解改成归并。剩下的一车证明咕咕咕了,还没有看。
  • 化树为链。先考虑在链上怎么做。

    • CF2133E I Yearned For The Mines 在链上,可以用操作1从一端扫到另一端;如果有分支显然没法做了。然后把问题转化成割除最多\(\lfloor \frac{n}{4} \rfloor\)个点使剩下的形成链。然后染色构造。有三种颜色分别表示1.链的端点 2.链的转折点 3.切割点。怎么染抓住使得割出来的东西没有分支来做。证明个数考虑把切割点和别的捆绑。code
  • 对于一些形如\(\forall i \in [1,m],ans=\sum ans_i\)的东西,把i分段考虑和把答案分段考虑都要想到,分割点是单调的。有时候这个答案只有常数个,那就再套一只log。

    • CF1883G2 Dances (Hard Version)easyversion配一下对就好了,这个i可以用ab数组在数轴上划分开来分讨好多段每段情况是一样的。这个时候发现虽然情况一样的段有好多,但是答案不超过两个,直接二分转折点就做完了。总之被分讨死胡同击杀了。把i分段->把答案分段。
  • 一个排列或别的经过一些交换使其有序 -> 在一个个置换环中考虑。

    • CF1834F Typewriter 考虑一个置换环,它构成一个环,收尾相接,每次退回去要重置一次,其它直接连下去就好了。不同置换环中间(图待补),按最小值排序,每个从最小开始到最小结束,无需多余重置。
  • 构造最优方案(步数,操作数),首先考虑答案下界,然后证明能不能取到。证明很重要。

    • CF1834F Typewriter 下界:\(\sum [a[i]<i]\),证明见上。
    • SP9935 BC - Break the Chocolate 手掰是容易的,每次块数+1而且必然可以操作。刀切一开始认为是\(n+m+k-3\),然而这太不优了,一次切的太少,不值;然后认为是\(\lceil \log_2 {n\times m \times k} \rceil\),每次块数\(\times 2\)显然是一个下界,但是如果都是奇数就操作不了了,不太会证(?),发现有\(3 \times 3 \times 3\)就是反例,答案是$\lceil \log_2 n \rceil + \lceil \log_2 m \rceil + \lceil \log_2 k \rceil $,这个显然是能取到的。
  • 分类讨论,求最优值,注意如果某个分类的做法取不到最优值,但是这种取不到的实际最优情况可以被别的类别的包含,那就没有影响。

    • CF1834D Survey in Class 分成三类,盖了左边,右边,中间。中间的那一种只要取最大减最小就好了,如果并没有包含就被别的情况包括了,不用再去求严格包含的max。
  • 对一个序列做某种变化,如果每个新值和原序列相近下标的有关系,那么考虑子段/长度小的序列。

    • P13274 [NOI2025] 三目运算符 从长度为3的考虑,只有110,101会变,所以考虑这个子段如何扩展。
  • 对于二元二次不定整数解方程也存在递推的情况。

    • U110073 简单的规律 惊人的斐波那契数列。
  • 对于数乘之类的东西,注意较高位不影响较低位,可以考虑从低向高存在无后效性。

    • P1050 [NOIP 2005 普及组] 循环 高位不影响低位,所以一段较长后缀的循环节必然是其后缀的倍数。考虑如果暴力地判无解,不知道做到什么时候结束,但是如果只要考虑以为,做10次就好了。然后就从低位到高位考虑,已经求得了长度为p的后缀循环节为x,要求加一位的,把原来的乘数^x,现在忽略了后p位的影响,重新跑10遍就好了。
  • “回路”是一个环,如果计算贡献在哪里断开都差不多。

    • U248238 9.28 Highprice 求一个代价最小的哈密顿回路,起始位置是1没有什么用。按a排序之后标记为\(p_1,p_2...p_n\),考虑最后形成的环,从1和n处断开(这步想不出道理),然后考虑起始终止位置固定为\(p_1,p_n\)怎么排代价最小:令\(q_i=\lfloor \frac{1000}{p_i} \rfloor\)\(p_1<p_2<...<p_{n-1},q_2>q_3>...>q_n\)(这里下标范围固定是因为固定了起止),根据排序不等式\(p_i\)\(q_{i+1}\)配对显然最优(感性理解为和一定,差越大,积越小),这对应了有序的构造方式。起止位置反一下亦然。然后转化成把\(p_i,i \in [2,n-1]\)分配到两条链里,这个可以用dp解决,我们计算贡献只需要链顶,所以只记录链顶就好了。\(f_{i,j}\)表示两条从小到大构造的链顶分别为i,j的最小代价。一个小trick,边界设成\(f_{1,1}=0\)可以避免分讨,但是我写码的时候并没有想到。code
  • 位运算和加减出现在一起,求某一个运算出现值的次数/总和,可以分讨每一位奇偶性进行记搜(或者数位dp 没写过),但是要计算保证状态数,复杂度。

    • CF1815D XOR Counting 注意到相同值就算一遍。从值的角度考虑,考虑能否构造出来,容易发现异或和、和的奇偶性相同,尝试构造出与n奇偶性相同的x作为异或和,当\(m\geq3\)时,\(x \oplus \frac{n-x}2 \oplus \frac{n-x}2 = x\)\(m=1\)答案为\(n \bmod p\)\(m=2\),分讨最后一位奇偶性,记录总和与方案数。复杂度计算考虑偶数分出的两个必然一个是奇数,再分下去会和偶数的其中一个合并(分讨一下就行)。这样不会数重还是用了异或和与和的奇偶性相同这个性质,奇数分下去显然不会重,偶数两种情况是一奇一偶,所以也不会重。
  • dp,搜索等记录当前状态,都考虑我们只关心什么。

    • U111198 他说小于P 生成新数,判断合法都只关心余数,相同余数保留最小的显然最优,优化状态。
  • 用几个数生成从小到大的数,从高位到低位,每次在后面加新数(注意先导零)。

    • U111198 他说小于P 宽搜实现。
  • 区间合并 -> st表上套并查集。主要思想是把一个大区间分成log个小区间,相同长度合并。之后把\(2^k\)分成两段下放到\(2^{k-1}\)上,最后回归到点。

    • P3295 [SCOI2016] 萌萌哒 板题。最后答案统计的$9\times 10^{cnt-1} $也是显然的。code
  • 在取模意义下依旧要考虑大小关系 \(\rightarrow\) 考虑保留相对大小,取模意义下绝对大小另存。需要保证这个相对大小的范围可接受。

    • CF1805F1 Survival of the Weakest (easy version) 符合上述条件。考虑进行一次操作,把所有值都减去\(a_1\),最后并出来的东西每个实际值都差了\(a_1\),不影响,且新的min和max差距不大于\(a_n-a_2\),依旧在原来范围内,所以一直这样迭代就行,sum的意义是上一次\(a_1\)的实际值。
  • 两个栈互相出入 考虑把栈顶接起来(相对位置不变)

http://www.hskmm.com/?act=detail&tid=11056

相关文章:

  • 代码随想录算法训练营第四天 | leetcode 24
  • 网络流 最小割、费用流
  • DP tricks
  • 碎碎念(十七)
  • OpenCV的一些API的使用
  • 2971:抓住那头牛
  • 高效测试的第一步:5个用例设计基础思维模型
  • MFC Button 控件完全指南:从基础到进阶 - 指南
  • Python笔记总结
  • vulnhub靶机:GoldenEye-v1
  • 8465:马走日
  • 性能调优之NUMA调优
  • 深入解析:SpringMVC静态资源与Servlet容器指南
  • CCPC Online 2025 游寄
  • CentOS 7 容器时遇到了 yum update 报错
  • MIT新论文:数据即上限,扩散模型的关键能力来自图像统计规律,而非复杂架构
  • 基于MATLAB的视频动态目标跟踪检测搭建方案
  • U522155 数据生成(小心电脑)
  • 实用指南:OSG中osgFX库
  • 如何将带有线网卡和无线网卡的台式机作为网关/路由器
  • 2025.9.20——1橙
  • 日期
  • 【GAN网络解惑】面向产品的优化:推理裁剪、蒸馏、INT8/FP8 量化,GAN 的真实延迟如何打下来? - 教程
  • 资本与资本主义
  • 202509_NBWS_encoded_csv
  • 滑雪
  • 守序者的尊严
  • 在Ubuntu22.04平台上交叉编译针对Rv1126架构的GCC13.2.0编译器
  • 深度学习(DBBNet重参数化)
  • CAR 细胞疗法:肝癌治疗的曙光与荆棘