ACM Trick Points (持续更新)

函数

memset 赋值

们在设计程序时经常会使用memset(array, val, sizeof(array))来初始化一个int数组array,因为memsetstring.h中的函数所以其填充对象也是字节,会将数值val(或者是字符val)填充到array的每个字节上,因此用memset只能赋值出每字节都相同的int

因此,我们如果想要将某个数组初始化为INF,则能赋值出的最大数值为0x7fffffff。但是为了避免加法算术溢出或其他判断,我们通常选择将数组的每个int初始化为0x3f3f3f3f。这个数值满足以下两个条件:

  1. 整数的两倍不超过0x7fffffff(即INT_MAX)。
  2. 整数的每8位都相同(恰好可以用memset填充)。

因此我们通常使用memset(array, 0x3f, sizeof(array))来初始化int数组。

scanf 读取数组元素

输入括号需要来回切换光标,十分麻烦…如果不想输入类似&a[i]的符号,可以使用指针形式来简化输入: scanf("%d", a + i);

这个方法也适合在读入字符串时将其存储在并非数组开头的位置。

数学

余式定理

对多项式$P(x) $,有$\frac{P(x)}{x-a}$之余式为$ P(a)$。

更一般地,假设对于多项式除法$\frac{P(x)}{M(x)}=Q(x)+R(x) $,其中商是$Q(x) $,余式是$R(x) $,若$ M(x)$是n次式$ (n \geq 1)$,则可将其$ n$个根列出联立方程

$$\P(a)=R(a) \P(b)=R(b) \P(c)=R(c) \ \cdots$$

证明

考虑$\frac{P(x)}{x-a}=Q(x)+R(x)$。

由除法定理有$P(x)=(x-a)Q(x)+R(x) $。且因为$x-a $是1次式,故$ R(x)$为常数,记为$ r$。

此时代入$x=a $,可得$ P(a)=r$。证毕。

Attention Points

运算符优先级

一些运算符的优先级由高到低如下表所示,最需要注意的点是:大小关系比较运算符的优先级高于“位与”“位或”“位非”运算符。

加减移位比较大小位与异或位或
+, -«, »>, <, ==, !=&^位或

vector 的 push_back 相关

在没有显式为某个vector分配空间时,绝不能用下标访问其元素而应使用push_back

阴险的出数据方式

POJ 3263

一条关系$ (A_{i}, B_{i})$ 可能会输入多次(即输入重边),刻意影响区间操作。

updatedupdated2023-03-112023-03-11