动态连通性问题

“连通” 是一种等价关系，两个对象 p 和 q 是相连通的，意味着它具有：

• 自反性：p 和 p 是相连的
• 对称性：如果 p 和 q 是相连的，那么 q 和 p 也是相连的
• 传递性：如果 p 和 q 相连且 q 和 r 相连，那么 p 和 r 也是相连的

等价关系将对象分为多个等价类，在这个，当且仅当两个对象相连通时才属于同一个等价类。

0-1 背包

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

优秀 API 的特征

问题域建模

API 应该对它所解决的问题提供良好的逻辑抽象。当把 API 文档提供给用户时，他应该能够理解接口中的概念并且知道它的工作机制。

API 应该对问题域的关键对象建模，即面向对象设计。一般使用 UML 类图或对象图表示对象模型。

隐藏实现细节

API 应该隐藏所有的实现细节，避免修改 API 对已有的客户造成影响。

模板参数推导

函数模板类型推导

简单的函数模板：

1
2

template <typename T>
void f(ParamType param);

调用时：

1

f(expr);

在编译期间，编译器会推导两个类型：一个是 T ，另一个是 ParamType ，比如：

1
2
3
4
5
6

template <typename T>
void f(const T& param);

// 调用
int x = 0;
f(x);

T 推导为 int ，ParamType 推导为 const inst& ，T 的推导不仅取决于 expr 的类型，还取决于 ParamType 的类型。

苍山雪，洱海月，上关花，下关风

这句谚语意思是大理点苍山白雪皑皑，洱海湖月明水秀，石门关花团簇锦，龙尾关风光宜人。形容云南大理到处景色优美。

花了一个周末的时间去大理逛了逛，证实了上面的谚语没有说错。