中二病也要打OI

12.1：【CF2158E Sink】、【CF2158F2 Distinct GCDs】、【CF2164E Journey】、【CF2156E Best Time to Buy and Sell Stock】、【CF2154E No Mind To Think】、【CF2039F2 Shohag Loves Counting】、【CF2029E Common Generator】

  1. 把 "修改" 变成增加/删除。

  2. 构造题如果将题意变成另外一个模型，可以给模型自己添加一点限制，在构造时去满足它。

  3. 固定一些变量后观察最优。

  4. 看到 gcd 得想起来莫比乌斯反演。为了避免处理 corner case 修改一下 dp 的初值之类。

  5. 考虑一些特殊的位置：\(2\)。

12.2：【CF2029F Palindrome Everywhere】、【CF2029G Balanced Problem】、【AGC059C Guessing Permutation for as Long as Possible】、【CF1305H Kuroni the Private Tutor】、【CF173D Deputies】、【CF1870F Lazy Numbers】、【CF1566F Points Movement】

  1. 奇偶分析。

  2. 还没把条件推清楚，就直接对着刻画了一半的结构 dp？

  3. 考虑对称性。

  4. 不要以为后推出的式子就一定是好用的。并不是！要根据面临的困境，从以前做出的所有成果里挑好用的。

  5. 从简单情况入手。

  6. 得想起来 2-sat 啊 ……

  7. 2-sat 计数：并查集？

  8. 一个复杂对象的最优，能否拆成若干个独立的简单部分，每个部分分别取最优？

    判定在限制条件下能否构造出一个复杂对象，能否先拿出一个部分，让它取成 "最容易构造" 的形态？

  9. 异或同时是不进位加法和不退位减法，或是不进位加法。

  10. 构造：先讨论一些简单的情况，复杂的情况看看什么情况下可以转化回去。

  11. 考虑补图。

  12. 不要老想着贪心去做构造，能不能用可行性 DP 构造？

  13. 字典序考虑 Trie。

  14. Trie 是树，当然也可以并且应该考虑 dfs 序。【Trie 上 dfs 序等于字典序排序的 rank】

12.3：【AGC040C Neither AB nor BA】、【AGC073A Chords and Checkered】、【AGC073B Cyclic Jump】、【AGC031C Differ by 1 Bit】、【AGC031D A Sequence of Permutations】

  1. AB,BA 转成 AA,BB。

  2. 经典：删除相邻两个不相同字符，能否删空，考虑众数。

  3. 刻画方式：静态转动态考虑。加入一条弦，取反半边。

  4. 神秘。

12.4：【vp CF2170】（F：离线扫描线，交换定义域值域）、【AGC031E Snuke the Phantom Thief】、【AGC031F Walk on Graph】、【CF2155F Juan's Colorful Tree】、【CF2152G Query Jungle】、【AGC032F One Third】、【CF2119E And Constraint】、【AGC068E Sort and Match】

  1. 交换定义域、值域。

  2. 切换限制主体。

  3. 先拆点。再考虑观察性质把点数缩小。

  4. 这种东西经常考虑反复走。

  5. 取模是非常循环的结构。

  6. 考虑转化为一些非常经典的问题。而经典问题没有公认的优秀解法就考虑一些暴力：指数、根号啥的。

  7. 把贡献拆独立。

  8. 【AGC032F One Third】的人类智慧转化方式。

  9. 傻逼，你怎么还在贪心，别jb捣鼓你那个修修补补也不对的贪心了，用dp不好吗

  10. 矩阵 => 能不能是邻接矩阵？

  11. 构造与图论结构的一一映射。钦定顺序去重。

12.5：【CF2165】、【CF2143E Make Good】、【CF2134D Sliding Tree】、【CF2133E I Yearned For The Mines】、【CF2119F Volcanic Eruptions】、【CF2131H Sea, You & copriMe】、【CF2060G Bugged Sort】

  1. 能不能建模成匹配问题？变成匹配了，能不能贪心？

  2. 找不变量。

  3. 构造题猜猜上下界。

  4. 考虑直径。

  5. 交互题：考察在什么情况下能用一个操作达成目的，再用另一个操作达成那个情况。

  6. 感受题目的条件：特别难满足，考虑怎么满足；特别容易满足，考虑怎么不满足。

12.6：【CF2111F Puzzle】、【AGC055F Creative Splitting】、【AGC038D Unique Path】、【CF2107F2 Cycling】、【CF2091G Gleb and Boating】

  1. 枚举一个不好找另一个上下界，考虑枚举另一个。

  2. 优化转移：把一个整段的转移拆开，只要拆开能覆盖到原来的就行。

  3. 先拆点，再优化状态数。

12.7：【AGC035E Develop】

12.8：vp CF2140、【CF2174B,C2,D,F】、【AGC035C Skolem XOR Tree】、【P10591 BZOJ4671 异或图】

  1. 值域小，考虑是否有用的位置不多？贪心调整。

  2. 平方的组合意义。

  3. 二分把任意值变成01.

  4. \(2\mid x\Rightarrow x\oplus 1=x+1\)。考虑一些简单的构造。

  5. 考察题目的操作怎么用，可能只在局部发挥作用就能解决一堆情况？

  6. 斯特林反演。

12.9：【P9330 JOI 国的节日 2】、【CF2025F Choose your Queries】、【CF2174F Mosaic Tree】、【P11834 岁月】、【CF2013F1 Game in Tree】、【CF2005E2 Subtangle Game】

  1. prufer 序列。

12.10：【CF2004F Make a Palindrome】、【CF2003E2 Turtle and Inversions】、【CF1998E2 Eliminating Balls With Merging】、【CF1997F Chips on a Line】、【CF1984E Shuffle】、【CF1984F Reconstruction】、【CF1981E Turtle and Intersected Segments】、【CF1969E Unique Array】、【CF1956E2 Nene vs. Monsters】

  1. 刻画最小代价：搞出一个正确的贪心，然后观察在什么情况下这个贪心会使得代价不取上界。

  2. 用 01 刻画！！！

  3. 最优化：考虑判定一个局面能否达到。

  4. 有两个方向的限制（前后缀？）：整体减去后缀变成前缀。类比：AGC031E

  5. 考虑简单情况。考虑局部。

  6. 直觉上，暴力的复杂度并不高？

12.11：【P7559 IOI 熱の感染拡大】、【CF1967E2 Again Counting Arrays】、【ARC176D Swap Permutation】、【ARC173D Bracket Walk】、【ARC179D Portable Gate】、【ARC168D Maximize Update】、【ARC198D Many Palindromes on Tree】、【ARC144D AND OR Equation】

  1. 考虑：一个点如何进入影响范围？什么情况下一定不会进入影响范围？

  2. 考虑：图论建模，简单的贪心？

  3. 一类经典的处理随机交换两个位置的方法：【ARC176D Swap Permutation】

  4. 主元法？

12.12：【ARC147E Examination】、【ARC146E Simple Speed】、【CF2176D Fibonacci Paths】、【ARC163D Sum of SCC】、【CF2176E Remove at the lowest cost】、【AGC035F Two Histograms】、【CF1039D You Are Given a Tree】

  1. 要把结构明晰了，优化的道路才会敞开！

12.13：【无题号 网格选数】、【CF1103D Professional layer】、【qoj10094 Slot Machine】、【CF1806F2 GCD Master】、【CF2176F Omega Numbers】

12.14：【ARC157E XXYX Binary Tree】、thupc、【ARC168E Subsegments with Large Sums】

  1. 最大化段数不会做：给每个段r-l的代价，最小化代价。

12.15：【CF1067D Computer Game】、【qoj15309 Dumb Problem II】、【qoj15304 Diameter of a Tree】

  1. 一个暴力 DP，考虑在 DP 时什么是常数？能不能写成凸包形式？

  2. 思考怎么刻画答案，把答案拆成很多小的部分，一些小部分归类一起算。

  3. 所有直径的中点相同。

  4. 经典 trick：按 \(l\) 的间隔标记点，在被标记的点处算贡献，这样复杂度变成调和级数。

12.16：dmy模拟赛（qoj15415 Infection Investigation、qoj10480 Beyond the Former Explorer、qoj15618 Minimizing Wildlife Damage）、【qoj15502 字符串问题】、【qoj15309 Dumb Problem II】、【qoj15306 Challenge NPC II】

  1. 近似算法：考虑给答案找一个界 \([l,r]\)，让 \(r=\varepsilon\cdot l\)。

  2. 高妙的行列式使用方法（刻画图的连通性、行列式配合DP求、主元随机赋值）。【qoj15306 Challenge NPC II】

12.17：【CF2133F Flint and Steel】、【qoj15303 Basic Counting Practice Problems】、【CF464D World of Darkraft - 2】、【P13782 Where Is the Root】

  1. 重链剖分优化dfs序DP，复杂度分析：【qoj15303 Basic Counting Practice Problems】

  2. 发现题目允许误差：把一些出现概率很小的情况直接丢掉。【CF464D World of Darkraft - 2】

12.18：dmy模拟赛（qoj10678两个环长相同的排列，对应的方案数也一定是相同的、ajo2025_final_d转移写成多项式矩阵相乘的形式，用二阶差分维护，折半后系数是一个范德蒙德卷积、ajo2025_final_e转最小割瞪眼观察出决策单调性和各种奇怪的单调性）、【qoj4565 Rarest Insects】

  1. 从暴力做法出发，考虑哪些状态是相同的。qoj10678

  2. 二阶差分可以维护系数为等差数列的多项式。ajo2025finalD

  3. 范德蒙德卷积拆组合数。 ajo2025finalD

  4. 感受。ajo2025finalE

  5. 优化二分：考虑哪些位置可以固定。

12.19：【qoj1813 Joy with Permutations】、【P5208 I 君的商店】、【qoj7535 Limited Shuffle Restoring】

  1. 交互题，考虑缩小询问涉及的范围。qoj1813

  2. 思考如何结合两个做法。P5208

  3. 搜出决策树的方法。

12.20：【AGC038F Two Permutations】、【qoj6774 Ancient Machine 2】、【qoj5090 妙妙题】、【P5473 I 君的探险】、【qoj4884 Battleship New Rules】、【CF1979F Kostyanych's Theorem】、【P3641 最大差分】、【CF1970D3 Arithmancy】

  1. 神秘问题考虑最小割，切糕模型，翻转变量定义的经典手法。

  2. 这种交互，根本不知道怎么做啊。

  3. 归约法，不一定要归约到 \(n-1\)，也可以归约到 \(n-2\)！【CF1979F Kostyanych's Theorem】

  4. 抽屉原理？【最大差分】

  5. 感受需要的条件，然后找一个最简单的版本，万一就直接构造出来了？【CF1970D3 Arithmancy】

12.21：【CF1896F Bracket Xoring】、【CF1764F Doremy's Experimental Tree】

  1. 考虑简单情况，然后用一些步数变成简单情况。

12.22：【qoj9561 树数叔术】、【qoj9607 熟练】、【CF2181K Knit the Grid】、【qoj14759 Rozwiązanie pokojowe】、【CF2181C Cacti Classification】、【CF2181E Elevator Against Humanity】

  1. 延迟决策。

  2. 弦图。

  3. 点边互化的思想。差分的思想。想起来 2-sat。

  4. 操作可逆 => 转化为一种局面。

  5. 神秘交互。

  6. 转化为好分讨的形式。

12.23：【qoj14575 集你太美】、dmy模拟赛（T1弱智了、笛卡尔树随机树高log那直接记深度即可，T2类比阴阳阵法、考虑怎么算答案）

12.24：【P11831 追忆】、【qoj14573 携春同行】、【P11369 弥留之国的爱丽丝】

12.25：【CF2173E Shiro's Mirror Duel】、【P1224 向量内积】、【P10016 虹】、【CF2163D2 Diadrash】、dmy模拟赛（不好评价，t1还真是树套树，t2还可以笛卡尔树上DP，t3稍微科技重工业）

  1. 配对思想。

  2. 人类智慧随机化，构造判断标志。怎么分析错误概率来着？

12.26：【P7450 巧克力】。做点简单题找手感。

2300，【CF1989E Distance to Different】、【CF2006C Eri and Expanded Sets】、【CF1988E Range Minimum Sum】
2500，【CF1946F Nobody is needed】、【CF1922F Replace on Segment】、【CF1758E Tick, Tock】
2700，【CF1804F Approximate Diameter】

重启zxy的思维技巧：【ABC219H Candles】

12.27：【CF1895F Fancy Arrays】、ucup、【P6847 Magic Tree】

12.28：【qoj9575 P ⊕ Q = R】、【CF1569F Palindromic Hamiltonian Path】

12.29：【P8522 地牢游戏】、【HDU7301 King's Ruins】、【qoj9518 观虫我】、【P5313 WBLT】、【uoj1016 成王败寇】、【CF2178G deCH OR Dations]

2300，【CF2035E Monster】
2500，【CF2038F Alternative Platforms】
2700，【CF1987F2 Interesting Problem】

12.30：dmy模拟赛，【CF2002E Cosmic Rays】、【CF2182D Christmas Tree Decoration】、【CF2178H Create or Duplicate】

12.31：【CF2182E New Year's Gifts】、【CF2182F2 Christmas Reindeer】、【ARC158D Equation】

1.1：【qoj6504 Flower's Land 2】、【P5406 找树】

1.2：【CF1526F Median Queries】

1.3：【P8340 山河重整】、【CF2103F Maximize Nor】、【qoj14583 这里是，终末停滞委员会。】

1.4：【AGC076A Hamming-Distant Arrays】、【CF1097G Vladislav and a Great Legend】、【CF2178I Numbers or Fireworks】、【qoj11713 Subsequence Queries】

1.5：【P7163 Svjetlo】、【ARC121F Logical Operations on Tree】、【ABC412G Degree Harmony】、【ARC161E Not Dyed by Majority (Cubic Graph)】、【qoj8613 Cardinality】

1.6：dmy模拟赛（t1简单dp，t2分块应该做出来的，t3的3log应该做出来的更多还是分析条件）、【CF1286F Harry The Potter】

1.7：【qoj14579 火花】、【ARC210E Subset Sum Gaps】、【AGC076B Split and Reverse】、【AGC076C Slime Eat Slime】

1.8：vp CF2183、P14001、写【火花】、【P12030 [USACO25OPEN] OohMoo Milk G】

1.9：dmy模拟赛（T1【qoj16210 CheapAI】、T2怎么正解和2-sat完全无关要神秘贪心、T3完全不懂啊）

1.10：ucup

1.11：【P13535 Souvenirs】、【ARC194E Swap 0^X and 1^Y】

1.12：vp CF2180、【无题号 连通】、【ARC195E Random Tree Distance】、【ARC200D A + A】

1.13：dmy模拟赛（T1拆分数，T2智慧观察，T3怎么是错题）、USACO

1.14：【P10138 Cowmpetency G】、【P9018 Moo Route G】、【P9191 Tree Merging G】、【CF1762F Good Pairs】、【qoj9532 长野原龙势流星群】、【CF1919E Counting Prefixes】

1.15：【代码源2026-1-15模拟赛T1 糖】、【P3447 KRY-Crystals】、【P5644 猎人杀】

1.16：【P10104 异或图】

1.17：ucup、【CF1336E2 Chiori and Doll Picking】、

1.18：白天whk晚上jk

1.19：【CF2096H Wonderful XOR Problem】、【代码源2026-1-15模拟赛T2 回】、【代码源2026-1-15模拟赛T3 棋】

1.20：dmy模拟赛、【CF2190B1 Sub-RBS】、ucup稍微补了下题

1.21：【CF2191E Comparable Permutations】、【ARC210D Independent Set Game】、【qoj14581 少年汹涌】

1.22：【qoj6366 Message】《qoj16263 Задачечка на подстрочечки》【P12403 象掌兽 Lirili Larila】

1.23：【ARC177F Two Airlines】、【P5985 Muzyka pop】

1.24：睡觉。

1.25：【ARC153D Sum of Sum of Digits】

2.5：重回 OI。【CF1615G Maximum Adjacent Pairs】

2.6：【P13497 墓碑密码】

2.7：【CF2189E Majority Wins】

2.8：【CF901D Weighting a Tree】

2.9：【P14983 Hoof, Paper, Scissors Triples P】、【AGC038C LCMs】、【AGC039C Division by Two with Something】、【AGC039D Incenters】

2.10：【AGC058F Authentic Tree DP】、【P9019 Tractor Paths P】、【CF2194E The Turtle Strikes Back】、【AGC045C Range Set】、【AGC046C Shift】、【loj2999 Keys】

2.11：【CF1307F Cow and Vacation】、【AGC039E Pairing Points】、【CF2190D Prufer Vertex】、【无题号 不连续子串】

2.12：【P4707 重返现世】、【pjudge21741 青鱼和区间】、【qoj9984 The Mysterious Shop】

2.13：【ABC306H Balance Scale】、【P10547 排列游戏】

2.14：ucup、【P6383 Resurrection】、【uoj216 Jakarta Skyscrapers】、【P8100 Counting Haybales P】

2.15：【CF2196B Another Problem about Beautiful Pairs】、【CF2196A Game with a Fraction】、【CF2196C2 Interactive Graph】、【qoj8049 Equal Sums】

2.16：【CF2196D Double Bracket Sequence】、【无题号 数环】

2.17：【P11458 All Pairs Similarity P】

待：CF2189、dmy若干题单和模拟赛、cyf题单

{Magnet}

待补：NOIP t3t4、ranklist sorting、qoj15308 Random Shuffle（12.15dmy课）、【Do Use FFT】

posted @ 2025-12-01 09:00  FLY_lai  阅读(56)  评论(0)    收藏  举报