C++信奥教学PPT：CSP_J_算法之回溯算法

一、卫星信号（Ping! North America-Mid-Atlantic USA 2013, LA6484）你正在跟踪一些卫星，每个都会以固定的间隔发出Ping信号，每种信号的信号间隔都是唯一的。但是Ping信号会互相抵消：如果在一个时间点同时收到偶数个信号，那么你什么也听不到。如果是奇数个，你会收到一个Ping信号。在第0时间点，所有卫星都会发信号，之后以各自的间隔来发送。给出一个长度在[2,1000]区间内的Ping信号序列，从中确定能听到的那些卫星的信号间隔。给出的信号序列，有可能不够长，导致某些卫星除了0时间点之外收不到第二个信号。这些卫星的信号间隔不需要计算。

二、稳定关系（A Stable Relationship, North America-Mid-Atlantic USA 2014,LA7118）3D打印机从顶端到低端一层层的布置原料来堆出一个物体。每一层都是要堆积体积和质量相同的打印原材料方块，每个都对应3D网格中的一个格子。同时假设打印机在打印过程中给物体施加的压力可以忽略。在打印过程中，记当前底面为P，已打印部分的质心在P上的投影为C。物体不会倾倒的充要条件是，C必须被一个3个顶点都位于已打印物体的最底面的形状内的三角形包含。3个顶点可能被底面不同的区域所包含。如果在一层打印完了之后物体不会倾倒，那么这一层打印的过程中也不会倾倒。给出物体的3D形状：宽度w，长度l，高度h（l,w,h≤200），以及每一层的平面形状：用l行w列的字符方阵来表示，“.”表示空格子，“#”表示实心。计算这个物体在打印完成之前是否会倾倒，只考虑物体在打印过程中和结束时是否会倾倒。

三、难对付的骑士（Tight Knight, North America-Mid-Atlantic USA 2014,LA7122）骑士在棋盘上的每步移动可以是两种情况：（1）水平两步加上垂直一步。（2）水平一步加上垂直两步。只要目标位置没被占用，就可以移动，不管中间经过的位置是否被占用。给出一个n×m（1≤n≤1000，1≤m≤1000）的棋盘。骑士一开始在(i,j)，行列都从1开始编号。有c（0≤c≤5000）个障碍物。骑士不能落到障碍物上。计算能不能最多增加一个障碍物就阻止骑士到达位置(k,l)（1≤k≤n，1≤l≤m）。(i,j)，(k,l)一开始都没有障碍物，并且这两个位置也不能放障碍物。