ShwBlog

题目传送门：Link

题面描述

用来爬历史天气。

原题链接：Link

原题链接：Link

题目描述

原题链接：Link

原题链接：Link

题目简介

简单来说，如果在一个序列 \(A\) 中，对于每一个 \(i > 2\) ，都有 \(A_i \ne A_{i-1}+A_{i-2}\) ，那么 \(A\) 被称为反斐波那契数列。就是不符合斐波那契数列要求的数列。题目要求构造出 \(n\) 个这样的数列，每一个数都要在 \(1 \sim n\) 之间。

T1

题面描述

有 \(n\) 块冰霜石和 \(n\) 块猩红石，给出 \(m\) 个不组合关系 \((i, j)\) ，表示第 \(i\) 个猩红石和第 \(j\) 个冰霜石不能组合在一起。现在你希望将冰霜石和猩红石配对，以发挥他们的最大效用，求最多可以将几对冰霜石和猩红石配对成功？

思路

Cms大佬说可以拿网络流骗分呢！

但是显然网络流不可能是我们这种蒟蒻打的模拟赛的T1的正解。

所以考虑面向数据编程：

最简单的数论。

碎碎念

• 感觉和图论有关的时候先考虑匈牙利再考虑网络流
• 区间 DP 不要死脑筋，答案可以不在 dp[1][n] 里，比如 P3146。
• 区间 DP 注意有负数的时候分类讨论取最大最小。P4342。
• 当看到跟点有关的连通性问题时可以考虑拆点建图，一个点负责入边，另一个点负责出边。P1345
• ISAP 注意两个优化：
  1. 当有一个 gap 为 0（也就是某个深度没有点）时，直接结束算法（将 dep[s] 设为 n）
  2. 当前弧优化
• ISAP 考虑清楚 dep 如何初始化以及更改。
• ISAP 注意边界条件 u == t
• ex_gcd 其实没有必要写返回值。