这是几乎全部机翻的版本。几乎可以肯定的是,这个翻译需要改进。

先决条件

  • 图论
  • 最短路

工具

本节讨论了几种用于计算各类几何属性的算法,主要基于下面描述的两种操作:叉积和反正切。

叉积

u和v的叉积写作u x v。在计算中,两个三维向量u和v的叉积是下列矩阵的矢量行列式(其中i、j和k分别是x、y和z方向的单位向量):

1
2
3
| i  j  k  |
| ux uy uz |
| vx vy vz |

这个式子的值为:

(uyvz-vyuz)i + (uzvx-uxvz)j + (uxvy-uyvx)k

通过将三维向量的z分量置为0,这一定义可用于二维向量。得到的向量只有z分量有值。

叉积有三条性质:

  • 两个向量的叉积垂直于这两个向量。
  • 叉积的长度等于以下几项的乘积:
    • u的长度
    • v的长度
    • u和v夹角的正弦值

在与u和v垂直的两个不同方向中,叉积指向的方向取决于u是在v的“右边”还是“左边”。

这就是右手定则吧。

点积

两个向量u和v的点积是写作u·v的标量。在计算中,它在三维向量中定义为: uxvx + uyvy + uzvz

点积实际上等于以下几项的乘积:

  • u的长度
  • v的长度
  • u和v之间夹角的余弦值。

假定u和v不为零,如果点积为负,则u和v的夹角大于90度。如果它为零,则u和v垂直。如果点积为正,则两个向量的夹角为锐角。

反正切

反正切函数计算其正切值等于它的参数的角度,通常返回-pi/2和pi/2之间的一个实数。C中的函数atan2接收两个参数:y轴的差值和x轴的差值(按此顺序!)。它确定给定向量和x轴正半轴之间的角度,并返回一个-pi和pi之间的值。这可以解决除零或需要撰写代码处理x轴负半轴的问题。该atan2函数几乎总是比简单的只有一个参数的反正切函数容易使用。

显然如果只接收一个参数,无法处理向量和x轴垂直的情况(因为会发生除0问题),而且只有正负也无法说明是和正半轴还是负半轴的夹角。

调试中的特殊问题

计算几何题的主要问题是它们会产生许多特殊情况。请留意这些特殊情况,并确保你的程序适用于所有这些情况

浮点数计算也会产生很多新问题。浮点计算很少是精确的,因为计算机只准确保留了若干比特(位):要注意这一点。特别注意,在检查两个值是否相等时,不要检查它们是否精确相等,而是检查它们之间的差值是否小于某个范围。

计算几何算法

下面是一些可以帮助你解决计算几何问题的代码片段。

三角形面积

要计算顶点为(a,b,c)的三角形的面积,选择一个顶点(比如说a),并创建从a指向另外两个顶的向量(令u = b - a,v = c - a)。则三角形(a,b,c)的面积是u和v叉积长度的一半。

另一种计算三角形面积的方法是海伦公式。如果三角形的三条边长度分别为a,b,c,令s = s = (a+b+c)/2,则三角形的面积为

sqrt(s*(s-a)*(s-b)*(s-c))

两条线段是否平行?

为了检查两条线段是否平行,请沿每条线段创建向量,并检查它们的叉积是否(几乎)为零。

多边形面积

顶点为(x1, y1), ...,(xn, yn)的多边形的面积等于行列式:

1
2
3
 1   | x1 x2 ... xn |
--- | |
2 | y1 y2 ... yn |

其中行列式的定义类似于2*2的行列式:x1y2 + x2y3 + ... + xny1 - y1x2 - y2x3 - ... - ynx1

不过我觉得我一般只会把多边形分成若干个三角形来算……

点到直线的距离

从点P到线段AB的距离等于叉积的大小,即d(P,AB) = |(P-A)x (B-A)| / | B - A | 。

为了确定从点P到由点A、B和C定义的平面的距离,令n =(B-A) × (C-A)。下列等式即给出距离:d(P,ABC) = (P - A) · n / |n|。

点在直线上

点在直线上当且仅当点到直线的距离为0。

在直线同一侧的点

这个概念只对二维平面有意义。要检查C点和D点是否在直线AB的同一侧,计算(B - A) x (C - A)和(B - A) x (D - A)的z分量。如果z分量具有相同的符号(即它们的乘积是正的),则C和D位于直线AB的同一侧。

点在线段上

为了计算点C是否在线段AB上,检查C是否在直线AB上。如果是,则检查AB的长度是否等于AC和CB的长度之和。

点在三角形中

为了检查点A是否在三角形中,找到三角形内的另一个点B(三个顶点的平均值就可以)。然后,检查点A是否和点B在由三角形的边定义的三条直线的同一侧。

点在凸多边形中

同样的技巧适用于凸多边形:

四(或更多)点共面

为了确定点集是否是共面的,选择三个点,A、B和C。如果对于任何其他点D,((B - A) x (C - A)) · (D - A) ≈ 0,则该点集共面。

先算出三个点对应的平面的法向量……

两条直线相交

在二维平面中,两条线相交当且仅当它们不平行。

在三维中,当直线AB和CD不平行且A、B、C、D共面时,AB和CD相交。

两条线段相交

在二维平面中,线段AB和CD相交,当且仅当A和B位于直线CD的不同侧且C和D位于直线AB的不同侧时。

请注意,两个检查都是必要的,因为在上图中最后一种情况中,一个检查返回true,而另一个检查才能证明AB和CD不相交。在三维情况中,求解下面的方程组,其中i和j是未知数:

1
2
3
Ax + (Bx - Ax) i = Cx + (Dx - Cx) j
Ay + (By - Ay) i = Cy + (Dy - Cy) j
Az + (Bz - Az) i = Cz + (Dz - Cz) j

如果该方程组具有解(i,j),其中0 <= i <= 1且0 <= j <= 1,则线段相交于点(Ax + (Bx - Ax)i, Ay + (By - Ay)i, Az + (Bz - Az) i。

两条直线的交点

对于二维平面中的直线AB和CD,计算它们交点的最直接方法是求解以下两方程两未知数的方程组:

1
2
Ax + (Bx - Ax)i = Cx + (Dx - Cx) j
Ay + (By - Ay)i = Cy + (Dy - Cy) j

交点坐标为:
(Ax + (Bx - Ax) i, Ay + (By - Ay) i)

在三维情况下,求解与检查线段交叉时相同的方程组,则交点坐标为:
(Ax + (Bx - Ax)i, Ay + (By - Ay)i, Az + (Bz - Az)i)

检查二维多边形的凸性

为了检查二维多边形的凸性,按顺时针顺序遍历多边形的顶点。对于所有的连续三个顶点(A,B,C),计算叉积(B - A) x (C - A)。如果 得到的所有向量的z分量都是正的,则多边形是凸的。

点在非凸多边形中

为了计算某点是否在非凸多边形内,从该点沿随机方向发出一条射线,并计算它与多边形相交的次数。如果射线在顶点或沿边缘与多边形相交,则选择一个新方向。否则,当且仅当射线与多边形相交奇数次时,该点才在多边形内。

此方法也适用于三维(和更高维度),但对相交的限制是只在面上相交,而不是在顶点或边上。

计算几何方法

计算几何题引入了几种不同的技巧,可用于减少运行时间或估计解。

蒙特卡洛方法

第一种计算几何技巧基于随机性。我们不是计算某事发生的概率,而是模拟随机事件并计算它发生的次数。如果模拟了足够多的事件,则这两个值之间的差异将变得非常小。

这有助于确定图形面积大小之类内容。我们不是直接计算区域,而是确定一个边界框,然后向框中抛出“飞镖”,并估计击中图形的概率是多少。如果计算得足够准确,这可以很好地估计实际面积。

这种方法的问题是,获得良好的相对误差(误差除以实际值)需要大量成功的事件。如果事件发生的概率非常小,则该方法不会产生很好的结果。

分区

分区是一种提高计算几何算法速度的方法。这需要将平面分成多个部分(通常通过网格,但有时也会按辐射切开或其他方法),并将对象分到对应的区域中。当在某个图形中查找对象时,只需要检查与该图图形具有非零交点的那些部分,从而大大降低了算法的成本。这有助于确定到给定点的距离在某个范围内的对象集和(图形是圆)或检查交叉点(图形是一条直线)。

图论问题

有时看起来像计算几何问题的问题实际上是图论问题。仅仅因为输入是平面中的点并不意味着需要计算几何算法。

例题

移动点

给定平面中的一组线段,以及两个点A和B,能否在不跨越任何线段的情况下从A移动到B?

分析:线段将平面划分为区域。确定这些区域,并检查A和B是否位于同一区域。

问题是怎么确定这些区域,感觉有些麻烦……

自行车路线

给定一系列互不交叉建筑的以及它们的起点和终点位置,找到从A到B的不经过任何建筑物的最短路径。

分析:这实际上是一个图论问题。结点是起始位置和结束位置,以及建筑物的顶点。如果两个结点之间的线段不与任何建筑物相交,则它们之间有边,其权重等于线段的长度。构造完该图后,问题就变成了最短路。

最大化交叉点数量

给定平面中的一组线段,找到可以与一条直线相交的线段的最大数量。

分析:经过一些思考,很显然直线必须通过线段集合中的两个顶点。因此,尝试所有顶点对,并计算每条直线的交叉点数量。将其与分区相结合,可以提供一种运行速度相当快的算法。

或者说,一种最优解可以通过旋转变换成另一个一定至少通过两个顶点的最优解……

多边形分类

给定定义多边形的一组线段,确定它是否是简单多边形(没有两个非连续线段相交)和凸多边形。

Q:凸多边形一定是简单的吗?

这是几乎全部机翻的版本。几乎可以肯定的是,这个翻译需要改进。

例题:穿越栅栏

农夫约翰拥有大量围栏,他必须定期检查它们的完整性。农民约翰通过维护围栏的交叉点列表,以及在每个交叉点点结束的围栏来跟踪它们。每个围栏有两个端点,每个端点位于一个交叉点,交叉点可能只是单个围栏的终点。当然,两个以上的围栏也可能共享一个端点。

给定围栏的布局,计算农夫约翰是否有办法骑马去他所有的围栏,且不需要不止一次地穿越围栏。约翰可以在任何地方开始和结束,但不能穿过他的田地(在交叉点之间穿行的唯一方法是沿着围栏)。如果有方法,找出一种方法。

问题的抽象

给定:无向图

找到一条只使用每条边一次的路径。这样的路径称为欧拉路径。如果路径在同一顶点开始和结束,则称为欧拉回路。

算法

检查图中是否有欧拉路径或回路实际上很容易; 使用下列两条规则。

  • 图中有欧拉回路,当且仅当它是连通图(在去掉度数为0的所有结点之后),且每个结点具有“偶数度”。
  • 图中有欧拉路径,当且仅当它是连通图,且除了两个结点之外的每个结点的度数均为偶数。
  • 在第二种情况下,具有奇数度的两个结点中的一个必须是起始结点,而另一个是结束结点。

算法的基本思想是从图的某个结点开始,并确定回到同一结点的回路。现在,随着回路的添加(事实上是以逆序),算法确保从该路径上所有结点出发的所有边都已被使用。如果该路径上还存在一些具有未使用的边的结点,则算法找到从该结点开始的使用这条边的回路,并将该新回路拼接到当前回路中。这一直持续到原始回路中每个结点的所有边都被使用为止,由于图是连通的,这意味着已经使用了所有边,因此得到的回路是欧拉回路。

更正式地说,要确定一个含有欧拉回路的图中的欧拉回路,选择一个起始结点并对其进行递归。在每个递归步骤中:

  • 选择一个起始结点并对该结点进行递归。在每一步中:
  • 如果结点没有邻居,则将结点加入到回路中并返回
  • 如果结点具有邻居,则创建邻居列表并对其进行处理(包括从需要处理的结点列表中删除它们),直到该节点不再有邻居为止
  • 为了处理结点,删除当前结点与其邻居之间的边,递归邻居,然后将当前结点加入到电路中。

这是伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# circuit是一个全局数组
find_euler_circuit
circuitpos = 0
find_circuit(node 1)

# nextnode和visited是局部数组
# 将以逆序找到路径
find_circuit(node i)
if 结点i没有邻居 then
circuit(circuitpos) = 结点i
circuitpos = circuitpos + 1
else
while (结点i有邻居)
随机选择结点i的邻居结点j
delete_edges (结点j, 结点i)
find_circuit (结点j)
circuit(circuitpos) = 结点i
circuitpos = circuitpos + 1

为了找到欧拉路径,只需找到其中一个具有奇数度的结点,并对它调用find_circuit

这两种算法的时间复杂度都是O(m + n),其中m是边数,n是结点数,如果图是以邻接表形式存储的话。对于较大的图,存在运行时栈溢出的风险,因此你可能需要使用自己的栈。

执行示例

考虑下图:

假设选择随机邻居时选择的是编号最小的邻居,算法执行过程如下:

栈:
当前位置:1
回路:

栈:1
当前位置:4
回路:

栈:1 4
当前位置:2
回路:

栈:1 4 2
当前位置:5
回路:

栈:1 4 2 5
当前位置:1
回路:

栈:1 4 2
当前位置:5
回路:1

栈:1 4 2 5
当前位置:6
回路:1

栈:1 4 2 5 6
当前位置:2
回路:1

栈:1 4 2 5 6 2
当前位置:7
回路:1

栈:1 4 2 5 6 2 7
当前位置:3
回路:1

栈:1 4 2 5 6 2 7 3
当前位置:4
回路:1

栈:1 4 2 5 6 2 7 3 4
当前位置:6
回路:1

栈:1 4 2 5 6 2 7 3 4 6
当前位置:7
回路:1

栈:1 4 2 5 6 2 7 3 4 6 7
当前位置:5
回路:1

栈:1 4 2 5 6 2 7 3 4 6
当前位置:7
回路:1 5

栈:1 4 2 5 6 2 7 3 4
当前位置:6
回路:1 5 7

栈:1 4 2 5 6 2 7 3
当前位置:4
回路:1 5 7 6

栈:1 4 2 5 6 2 7
当前位置:3
回路:1 5 7 6 4

栈:1 4 2 5 6 2
当前位置:7
回路:1 5 7 6 4 3

栈:1 4 2 5 6
当前位置:2
回路:1 5 7 6 4 3 7

栈:1 4 2 5
当前位置:6
回路:1 5 7 6 4 3 7 2

栈:1 4 2
当前位置:5
回路:1 5 7 6 4 3 7 2 6

栈:1 4
当前位置:2
回路:1 5 7 6 4 3 7 2 6 5

栈:1
当前位置:4
回路:1 5 7 6 4 3 7 2 6 5 2

栈:
当前位置:1
回路:1 5 7 6 4 3 7 2 6 5 2 4

栈:
当前位置:
回路:1 5 7 6 4 3 7 2 6 5 2 4 1

扩展

重边可以通过完全相同的算法来处理。

如果认为自环会为结点度数增加2(一进一出),则自环也可以通过完全相同的算法来处理。

有向图仅当强连通且每个结点的入度等于出度时才有欧拉回路(除了入度和出度均为0的节点)。算法完全相同,只是由于此代码找到环路的方式,您必须以相反的顺序遍历边。

在有向图中找到欧拉路径更难。如果您有兴趣,请阅读Sedgewick的书。

例题

飞机跳跃

给定一系列城市,以及这些城市之间的航班,确定是否存在一个航班序列,使得你顺序搭乘每个航班一次,最后回到开始的地方。

分析:这相当于在有向图中找到欧拉回路。

行进中的奶牛

农夫约翰有两种类型的奶牛:黑色安格斯奶牛和白色泽西奶牛。前几天约翰的妻子琼安将19头奶牛赶到市场上时,注意到四只连续黑白奶牛的所有16种可能性(例如,bbbb,bbbw,bbwb,bbww,...,wwww)都存在。当然,有些组合与其他组合重叠。

给定N(2 <= N <= 15),找到最小的奶牛长度序列,使得N个连续的黑色和白色奶牛的每个组合都出现在该序列中。

分析:图的顶点是N-1头奶牛的可能颜色。位于一个结点处表示最后N-1头奶牛与该结点的颜色匹配。也就是说,对于N = 4,如果最后3头奶牛颜色是wbw,那么你就在wbw节点。每个节点的出度为2,对应于在序列末尾添加黑色或白色奶牛。另外,每个节点的入度为2,对应于最后N-1头奶牛之前的奶牛是黑色还是白色。

嗯……为啥图的顶点是N-1头奶牛的可能颜色,而不是N头呢?

图是强连通的,并且每个结点的入度等于出度,因此图中有欧拉回路。

和欧拉回路相对应的序列是回路中第一个结点对应的N-1头母牛的序列,之后再加上每条边对应的颜色。

题意

洛谷 P1472 奶牛家谱 Cow Pedigrees

求所有高度为K,结点数量为N的二叉树个数。

分析

我在这道题上花了好久!之前Leetcode上有道类似的题(Leetcode 894. All Possible Full Binary Trees),不过那道题是要生成所有完全二叉树,而不是计数。

一个很简单的思路是这样的:

  • f[n][k]记录高度为k,结点数量为n的二叉树数量
  • 固定左子树高度为k-1,枚举左子树结点个数和右子树高度(显然左子树结点数量确定后,右子树结点数量也确定了)
  • (适当地)乘2(因为只固定了左子树的高度,差不多只考虑了一半情况;但是去重还需要仔细考虑……)

但是去重就出了一点问题。最开始我直接把所有结果都乘2,结果发现显然乘多了。比如说,左右两侧高度和结点数都相同的情况就不需要乘2。但是这样仍然不对。经过了比较漫长的手算和debug过程,我发现,左右两侧高度相同的情况都不需要乘2——因为它们都会出现在枚举中。举个例子:

四个二叉树

f[5][3]f[7][3]都会作为左边的二叉树出现在枚举中。


题解里的思路就稍微好(不容易出错)一点:分别枚举左边比右边深,右边比左边深和左右一样深的三种情况。这个时候如果还需要明确地按子树的不同高度进行枚举未免太麻烦,所以就用一个辅助数组g[n][k]存所有高度<= k且结点数量为n的二叉树的数量。

不过整体复杂度仍然都是O(N^3)的。

吐槽1:我之前的确很少(如果不是没有)见到要求结果模9901的。

吐槽2:这道题的文件名是nocows,听起来和NOCOW很像啊……

代码

我的DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
ID: zhanghu15
TASK: nocows
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

ofstream fout("nocows.out");
ifstream fin("nocows.in");

const LL P = 9901;
LL f[201][101]; // f[i][j]:i个结点的高度为j的二叉树的数量
int N, K;

LL calc(int num, int height) {
if (f[num][height] != -1) return f[num][height];
if (num == 1 && height == 1) {
f[num][height] = 1;
return 1;
}
if (num < 2*height - 1) {
f[num][height] = 0;
return 0;
}
if (height <= 0) {
f[num][height] = 0;
return 0;
}
f[num][height] = 0;
// 一侧结点数为s,高度为height-1
// 另一侧结点数为num-s-1,高度<=height-1
for (int s = 1; s <= num - 2; s += 2) {
if (calc(s, height-1) == 0) continue;
for (int h = 1; h <= height - 1; h++) {
f[num][height] += calc(s, height-1) * calc(num-s-1, h);
// 去重的正确姿势好难……
if (h != height-1)
f[num][height] += calc(s, height-1) * calc(num-s-1, h);
f[num][height] %= P;
}
}
return f[num][height];
}

int main() {
fin >> N >> K;
memset(f, -1, sizeof(f));
fout << calc(N, K) << endl;
return 0;
}

题解的DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
ID: zhanghu15
TASK: nocows
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

ofstream fout("nocows.out");
ifstream fin("nocows.in");

const LL P = 9901;
LL f[201][101]; // f[i][j]:i个结点的高度为j的二叉树的数量
LL g[201][101]; // g[i][j]:i个结点的高度<=j的二叉树的数量
int N, K;

int main() {
fin >> N >> K;
f[1][1] = 1;
// 像这样要用到辅助数组的时候,就不如写bottom-up的迭代形式了
for (int i = 1; i <= N; i += 2) {
for (int j = 1; j <= K; j++) {
for (int k = 1; k <= i - 2; k++) {
// 左边深度为j-1,右边深度<=j-2
f[i][j] += f[k][j - 1] * g[i - k - 1][j - 2];
// 左边深度<=j-2,右边深度为j-1
f[i][j] += g[k][j - 2] * f[i - k - 1][j - 1];
// 两边深度都是j-1
f[i][j] += f[k][j - 1] * f[i - k - 1][j - 1];
f[i][j] %= P;
}
for (int h = j; h <= K; h++)
g[i][h] = (g[i][h] + f[i][j]) % P;
}
}
fout << f[N][K] << endl;
return 0;
}

题意

洛谷 P1470 最长前缀 Longest Prefix

给定若干个字符串和另一个字符串S,问S的能由上述字符串组成的最长的前缀的长度。

分析

普通的动态规划。刚才好像刚刚在Leetcode上做了一道很相似的题:139. Word Break

一种转移方法是从前转移:对于当前的字符串结尾,枚举所有前缀,找到能够和它匹配的,判断减去匹配部分之后的字符串能否被构成。

另一种转移方法则是向后转移:对于当前(可行的)字符串末尾,枚举所有前缀,找到能够和后面的字符串匹配的,然后记减去前缀后的字符串为可行。这种方法可以利用Trie来进行优化,比前一种更快。

代码

普通的DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
ID: zhanghu15
TASK: prefix
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

vector<string> prefix;

bool ok[200000];

int main() {
ofstream fout("prefix.out");
ifstream fin("prefix.in");

string p;
while (fin >> p) {
if (p == ".") break;
prefix.push_back(p);
}

string s;
while (fin >> p)
s += p;

int n = s.length(), m = prefix.size();
int ans = 0;
// ok[i]:以i为结尾的字符串是否可行
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (prefix[j].size() - 1 > i) continue;
if (s.substr(i - prefix[j].size() + 1, prefix[j].size()) != prefix[j])
continue;
if (i == prefix[j].size() - 1 || ok[i - prefix[j].size()]) {
ok[i] = true;
break;
}
}
ans = ok[i] ? i + 1 : ans;
}
fout << ans << endl;
return 0;
}

普通的Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
ID: zhanghu15
TASK: prefix
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

vector<string> prefix;

bool f[200005];

struct TrieNode {
TrieNode* ch[26];
bool isEnd;
TrieNode() {
memset(ch, 0, sizeof(ch));
isEnd = false;
}
};

int main() {
ofstream fout("prefix.out");
ifstream fin("prefix.in");

string pre;
TrieNode* root = new TrieNode();
while (fin >> pre) {
if (pre == ".") break;
prefix.push_back(pre);
TrieNode* p = root;
for (char c: pre) {
if (p->ch[c - 'A'] == NULL)
p->ch[c - 'A'] = new TrieNode();
p = p->ch[c - 'A'];
}
p->isEnd = true;
}

string s, t;
while (fin >> t)
s += t;

int n = s.length();
int ans = 0;
// f[i]:以i结尾的字符串是否可行
for (int i = 0; i < n; i++) {
if (i != 0 && !f[i - 1]) continue;
TrieNode* p = root;
for (int j = i; j < n; j++) {
p = p->ch[s[j] - 'A'];
if (p == NULL) break;
if (p->isEnd) f[j] = true;
}
}
for (int i = 0; i < n; i++)
if (f[i])
ans = max(ans, i + 1);
fout << ans << endl;
return 0;
}

题意

洛谷 P1468 派对灯 Party Lamps

N盏灯和4个按钮:

  • 按钮1:按下后所有灯的状态都会改变
  • 按钮2:按下后奇数编号的灯的状态会改变
  • 按钮3:按下后偶数编号的灯的状态会改变
  • 按钮4:按下后编号模3余1的灯的状态会改变

所有灯起初都是打开的,给定一些灯的终止状态和总共按下按钮的次数,问是否存在对应的终态?如果可能,输出所有可能的终态。

分析

显然一个直觉是,同一个按钮只能按0或1次,按多了就和按的次数模2次效果是一样的。所以一共只有2^4=16种可能,枚举所有的可能,判断次数模2的取值是否相符以及各个灯的终态是否相符即可。

看了题解,发现这个直觉还不够厉害。事实上每6盏灯的状态都是重复的(6是2和3的公倍数):

1
2
3
4
press 1: oooooooooooo -> xxxxxxxxxxxx
press 2: oooooooooooo -> xoxoxoxoxoxo
press 3: oooooooooooo -> oxoxoxoxoxox
press 4: oooooooooooo -> xooxooxooxoo

所以直接枚举6盏灯的状态就行了。同时可以得到一个推论,编号模6相等的灯的终态必定相同。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
ID: zhanghu15
TASK: lamps
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int N, C;
int finalState[101];
bool state[101];
vector<string> output;

int main() {
ofstream fout("lamps.out");
ifstream fin("lamps.in");
fin >> N >> C;
memset(finalState, -1, sizeof(finalState));
int x;
while (fin >> x) {
if (x == -1) break;
finalState[x] = 1;
}
while (fin >> x) {
if (x == -1) break;
finalState[x] = 0;
}
memset(state, 1, sizeof(state));
// 这里直接写了一个四层循环……
for (int b1 = 0; b1 < 2; b1++) {
if (b1 == 1) {
for (int i = 1; i <= N; i++)
state[i] = !state[i];
}
for (int b2 = 0; b2 < 2; b2++) {
if (b2 == 1) {
for (int i = 1; i <= N; i += 2)
state[i] = !state[i];
}
for (int b3 = 0; b3 < 2; b3++) {
if (b3 == 1) {
for (int i = 2; i <= N; i += 2)
state[i] = !state[i];
}
for (int b4 = 0; b4 < 2; b4++) {
if (b4 == 1) {
for (int i = 1; i <= N; i += 3)
state[i] = !state[i];
}
if (b1 + b2 + b3 + b4 <= C && (C - b1 - b2 - b3 - b4) % 2 == 0) {
bool ok = true;
for (int i = 1; i <= N; i++) {
if (finalState[i] != -1 && state[i] != finalState[i]) {
ok = false;
break;
}
}
if (ok) {
string s;
for (int i = 1; i <= N; i++)
s += (char)(state[i] + '0');
output.push_back(s);
}
}
if (b4 == 1) {
for (int i = 1; i <= N; i += 3)
state[i] = !state[i];
}
}
if (b3 == 1) {
for (int i = 2; i <= N; i += 2)
state[i] = !state[i];
}
}
if (b2 == 1) {
for (int i = 1; i <= N; i += 2)
state[i] = !state[i];
}
}
if (b1 == 1) {
for (int i = 1; i <= N; i++)
state[i] = !state[i];
}
}
// 忘了这回事,于是错了一次……
if (output.size() == 0) {
fout << "IMPOSSIBLE" << endl;
return 0;
}
sort(output.begin(), output.end());
for (int i = 0; i < output.size(); i++)
fout << output[i] << endl;
return 0;
}

题意

洛谷 P1467 循环数 Runaround Numbers

定义循环数为满足以下条件的整数:

  • 各个数位都不重复
  • 从最左边的数位开始进行如下操作:
    • 向右循环数该数位对应的数字个数
    • 然后从得到的数位开始继续数
    • 在各个数位都(不重不漏地)开始数了一遍之后,会回到最开始的数

给定正整数M,问大于M的下一个循环数是多少?

分析

按我惯常的习惯,肯定是先去OEIS上查一查,不过结果是并没有。

做题的时候,我首先写了一个暴力判断某个数是否为循环数的代码。本来应该想想怎么优化(毕竟M据说最多9位,如果直接暴力挨个判断比M大的数会超时的吧),但是那天不知道哪根神经出了毛病,直接把暴力给交上去了。结果居然就过了,还挺快……??

看了一眼测试数据,发现这范围跟说好的不一样啊,不是说M最多有9位吗,怎么这里最多只有7位?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
------- test 1 [length 3 bytes] ----
99
------- test 2 [length 7 bytes] ----
111110
------- test 3 [length 7 bytes] ----
134259
------- test 4 [length 7 bytes] ----
348761
------- test 5 [length 8 bytes] ----
1000000
------- test 6 [length 8 bytes] ----
5000000
------- test 7 [length 8 bytes] ----
9000000

仔细一想,我意识到,9位的循环数是不存在的:假设这样的循环数是存在的,因为要求各个数位不同,那么必须有一个数位为9;但是这个数位数了9位之后只会回到自己,没办法构成循环。由此还可以得到一个推论,n位的循环数中必然不存在数位n。所以,暴力代码能过这件事看起来就正常一点了。

但是为什么测试数据只有7位呢?我尝试把所有长度<=9位的循环数都打印出来,结果得到的最大的数是9682415。所以,为什么8位的循环数也不存在呢?

我又仔细想了一下,发现8位的循环数确实不应该存在(而不是我的暴力写错了之类的)。由上面的推论可以得到,8位的循环数中没有8,因此只能是1-7和9这8个数字。假设有这样一个8位的循环数,我们从左侧的第i位出发,遍历了所有数位各一次后,当前的数位应该是(i + 1 + 2 + .. + 7 + 9) % 8,且这个数位应该还是第i位。问题是,1 + 2 + .. + 7 + 9 = 37,这样根本没办法回到原来的位的!所以8位的循环数必然是不存在的。由此还可以得出另一个推论,就是n位的循环数的数位之和必然模n余0。


当然,比较正确(而不依靠随便乱交……)的做法是,枚举出所有长度为n且各个数位不相等的数,然后再判断它们是否为循环数——因为9!=362880,所以不会超时。

题解里还有一种比较神奇的做法——从M直接生成下一个各个数位都不相等的数,然后再判断它们是否为循环数。不过他到底是怎么生成下一个数的我就没细看了……

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
ID: zhanghu15
TASK: runround
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

bool test(int x) {
int digits[10];
int cnt[10];
memset(cnt, 0, sizeof(cnt));
int n = 0;
while (x > 0) {
digits[n++] = x % 10;
if (cnt[x % 10]) return false;
cnt[x % 10]++;
x /= 10;
}
bool visited[10];
memset(visited, 0, sizeof(visited));
int cur = n - 1;
for (int i = 0; i < n; i++) {
visited[cur] = true;
int next = ((cur - digits[cur]) % n + n) % n;
if (visited[next] && i != n - 1) return false;
cur = next;
}
return cur == n - 1;
}

int main() {
ofstream fout("runround.out");
ifstream fin("runround.in");
int M;
fin >> M;
for (LL i = M + 1; i <= (LL) 1e10; i++)
if (test(i)) {
fout << i << endl;
return 0;
}
return 0;
}