Skip to content

Latest commit

 

History

History
368 lines (356 loc) · 21.9 KB

exercises.md

File metadata and controls

368 lines (356 loc) · 21.9 KB
Raw

做题记录

很多题会综合运用几种算法，我把它归到思维难度（对于这道题，而不是知识点本身）最大的那一类里。当然要是你点开一道题发现它是黄的或者绿的，那大概要么是这道题很典看标题就想起来了，要么就是有一些思想在里面。

图

贪心

  • 区间覆盖
  • 反悔
  • 邻项交换排序 ouuan: 应用及注意事项
  • 模拟工厂 枚举
  • Strange Train Game 反悔贪心 还有一些区间到图的转换思想
  • The Enchanted Forest
  • 排队接水 纯粹的排序不等式
  • 猫耳小 当时想复杂了。遍历，删除使 mex 为 $k$ 的数即可
  • 骑士的工作 尽可能让 zi 小的人砍尽可能小的头。
  • 小A的糖果 从 2 个和 3 个盒子开始递推，每遇到多的就把它吃掉
  • 跳跳！

    只需要证明第一步跳到了 $H=\max h$. 假设存在更优解，第一步是 $h_0(h_0\ne H)$.

    • 若 $H$ 是终点，把顺序全部反过来，总贡献增大 $H^2-h^2$.
    • 若 $H$ 不是终点，设第 $k$ 步跳到了 $H$，第 $(k+1)$ 步跳到了 $h'$. 把第 $1\sim k$ 步反转，总贡献增大 $$H^2-h_0^2+(h_0-h')^2-(H-h')^2=2h'(H-h)>0.$$
  • Strange Cake Game 2 人决策，先考虑后手，分析先手的策略。
  • 游戏预言

    假设 J 总是把牌从大到小出，其余所有的牌都拿在一个人 F 手里，每次出 $(m-1)$ 张。如果 F 有牌能赢得这轮，剩下要出的 $(m-2$ 张牌拿最小的占位即可。

    之后从大到小枚举每一张牌。对于 $i(1\le i\le mn)$ 号牌：

    • 它不是 J 的牌，把它标记为 F 的牌。
    • 它是 J 的牌。如果 F 的牌至少有 1 张能够压住 J，那么 F 总是应该选择压上。因为对于 F 的任意 2 张比 J 的这张大的牌，用哪张盖上 J 的这一张牌，另一张都可以在后续回合里继续创造胜利。

    用桶存下 J 的每一张牌，从 $mn$ 到 1 反向枚举，如果是 F 的牌则加入储备牌库（$c\gets c+1$）；是 J 的就看看牌库有没有牌，如果有 $c\gets c-1$，否则 $a\gets a+1$。

hash

dp

数据结构

数据结构不是看完题想用什么实现合适，而是先想清楚要维护什么，再选择对应的数据结构。

模拟

构造

  • 周期相关
  • 反回文串
  • 均分纸牌
    1. 算平均数；
    2. 求每堆纸牌与平均数的关系（多1记为1，少1记为-1）；
    3. 允许纸牌数量为负数情况下强行从右边的拿（可撤销贪心）。
  • Sherlock and his girlfriend 质数一个色，合数一个色。
  • Vladik and fractions $\frac2n=\frac1n+\frac1{n+1}+\frac1{n(n+1)}$
  • Milena and Admirer
  • Coloring Edges

    每一个环上一定含有在与不在 DAG 上的两种边。DAG 一种颜色，其它边另一种颜色即可。没有环的话直接全部同色，有环时拓扑序可以任意规定。

    无重边的无向图里 DAG 对应生成树，每一个环一定经过树边和非树边。有重边情况就多了。

  • Strange Madoka Game
  • 神奇的幻方 就题意而言其实是模拟，但这也给出了一种构造幻方的方法。
  • 格雷码
  • Center of the Earth
  • Happy Card 观察到删 4 个和删 3+1 是同一类，然后只要处理重复 1 2 3 次的牌即可。
  • 三国游戏 找每行次大值的最大。能更优的只能是某行最大值，这时它这一列一定有比它更大的，因为对称，这个数会在它这列标对应的行标以次大值出现。
  • TABOVI 差分，记得从整体上考虑。

搜索

数学

基础算法

todo