模板 杂项

发表于 |
字数统计: 833 字

这里收录的是一些并不特别属于某个类别的算法的模板。

时间类

计算星期几

使用 Zeller 公式计算。

首先有一个历史背景：罗马教宗在 1582 年 10 月 4 日颁布新的历法，把该日的后一天改为 1582 年 10 月 15 日。因为这个因素的存在，我们可能需要在具体情况下具体分析。不过一般要求的星期都是在那一天之后的。

在 1582 年 10 月 4 日之后，计算星期的公式为

在该日及之前，计算公式为

其中 $w$ 如果为 0 就表示星期日，其他分别表示星期一到星期六。$c$ 为年份的前两位数，$y$ 为年份的后两位数。$m$ 为月份，1 月和 2 月分别对应上一年的（这意味着要把年份减一）13 和 14 月，3 月到 12 月分别对应当年的 3 到 12 月。

下面的代码只给出了第一个公式的实现，因为实际上第二个公式很少用到。

1
2
3
4
5
6
int weekd(int y, int m, int d){
    if (m <= 2) m += 12, --y;
    int yc = y / 100, yy = y % 100;
    int t = 7 + (yy + (yy >> 2) + (yc >> 2) - (yc << 1) + (26 * (m + 1) / 10) + d - 1) % 7;
    return (t > 7 ? t - 7: t);
}

日期之差

计算两个给定日期的差可以改成算出两个日期分别到公元元年第一天的差，然后相减。

调试类

下面的一些代码或者指令只针对线下调用的时候使用，平时不建议使用。

扩展栈空间

在编译指令中加入下面的指令以开大栈空间：

1
-Wl,--stack=1000000000

一般这个

游戏类

n * m 魔板

一般这种题目就是要求两个局面之间的可达性或者是直接要求变化的最短路径。要求最短路径，我们可以通过搜索得出；而要求是否可达，就有更加简便的判别方法。

方法就是：先把魔板中的数（不包含 0）按照行从小到大写成一行，然后统计逆序对数。对两种局面都做一次。然后分类讨论：

  1. 如果列数为奇数，那么只需要两种局面的逆序对数奇偶性相同即可。直观的解释是，因为 0 的移动会造成偶数个逆序对数的变化，所以只需要保证这一点即可。
  2. 如果列数为偶数，那么只需要起始局面逆序对数加上前后 0 的行数的变化值和结束局面的逆序对数的奇偶性相同即可。直观的解释是，因为 0 的移动会造成奇数个逆序对数的变化，所以上下移动一行会导致逆序对数奇偶性变化。所以需要额外加上 0 行坐标的变化。

不仅可达性可以被判定出来，事实上最短路径的长度也存在上界。

编码类

格雷码

前后两个格雷码有且只有一位不同。在某些时候会很有用处。

这里直接给出构造方案：第 $i$ 个格雷码为 i ^ (i >> 1)。

1
2
3
4
5
void grey_code(int n){
    int lim = (1 << n);
    for (int i = 0; i < lim; ++i)
        printf("%d\n", i ^ (i >> 1));
}