**以下解答主要来自出题者提供的解题报告（可能略有改动）。由于本人能力的限制，可能对于很多数据结构和算法的理解存在偏差（如果发现什么问题，十之八九不是出题者的问题，而是我自己的理解有问题，因此写得不对），欢迎大家指正。:)

Logs Stacking

很容易推出f(i) = [3 * f(i - 1) - f(i - 2)] mod 100000。通过程序测试一下，可以发现f(i)以750000为循环节，因此f(i) = f(i mod 750000)。

Building roads

标程用的算法是二分查找，给定一个答案后，用2-SAT判断是否可行。下面主要说一下2-SAT问题的建模。用布尔变量Xi表示第i个牛栏连到第一个中转站，即Xi为真时连到第一个，为假时连到第二个。那么~Xi表示第i个牛栏连到第二个中转站，~表示布尔取反。 检查每一个约束条件，构造2-SAT的和取范式。

1）i和j不连到同一个中转站，就增加和取范式(Xi + Xj)(~Xi + ~Xj)。

2）i和j必须连到同一个中转站，就增加和取范式(Xi + ~Xj)(~Xi + Xj)。

设现在二分的答案是S。那么检查每一对牛栏i和j（假设D1i，D1j表示i和j到第一个中转站的距离，D2i，D2j表示i和j到第二个中转站的距离，DD表示两个中转站之间的距离）。如果

3）D1i + D1j 〉S，就增加和取范式（~Xi + ~Xj）

4）D2i + D2j 〉S，就增加和取范式（Xi + Xj）

5）D1i + D2j + DD 〉S，就增加和取范式（~Xi + Xj）

6）D2i + D1j + DD 〉S，就增加和取范式（Xi + ~Xj）

剩下的只是用2-SAT的现成算法去判断是否有解。

Potted Flower

问题描述：给定一个环形序列，进行在线操作，每次修改一个元素，输出环上的最大连续子列的和。

算法：把环从一个地方，切断拉成一条直线，用线段树记录当前区间的非空最大子列和当前区间的非空最小子列。

如果环上的数都是正整数，答案是：环上数的总和－根结点的非空最小子列；否则，答案是：max{根结点的非空最大子列, 环上数的总和－根结点的非空最小子列}

每次问答的复杂度是O(logN)。

Saving Endeavour

问题就是2台机器，n件任务，必须先在S1上做，再在S2上做。任务之间先做后做任意。求最早的完工时间。

这是一个经典问题：2台机器的情况下有多项式算法（Johnson算法），3台或以上的机器是NP-hard的。思想就是贪心，时间复杂度是O(nlogn) 。

Johnson算法

(1)    把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。

(2)    对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。

Seek the name, Seek the fame

问题描述：给定一个字符串，要求找到同时是它前缀也是后缀的字符串的个数，并且输出他们的长度。

算法：KMP算出next数组，然后n, next[n], next[next[n]] ....就是答案了。只要知道KMP算法的实质含义，这个算法不难想到。

Similarity of necklaces

考虑费用Table/Cost的上三角
****
 ***
  **
   *
为了让Table总合为0（定值），我将其中非对角线的6个位置的费用乘以2。

因为最终求的是：“Sigma 出现次数*费用”的最大值。为了让每项都扩大一倍，不得不把对角线部分的出现次数也乘以2，保持稳定。之后，就是这样一个问题，一共n*(n-1)/2个数，每个数出现的次数告诉你了。每个数的费用由一个上下限组成，对角线是上的范围是low~up，非对角线上是2*low ~ 2*up，总合为0。（***注意，非对角线费用必须是偶数！这是贪心的最大难点）让你求“Sigma 出现次数*费用”的最大值。

贪心的想法是：先对出现的次数排序，可以找到一个位置，对排在这个位置前面的都取下界，对排在这个位置后面的都取上界。这个位置的取值在上界和下界之间。这样就可以达到最优解。

但是当这个位置不在对角线上而且为奇数的时候，我们需要特殊调整一下。

Similarity of necklaces 2

这个问题是一个012背包问题。我们知道01背包只要逆向线性检索，无限背包只要正向检索。012背包就是说，每个物品有一个数量上限。这个问题可以用log方法，也存在线性方法，需要维护一个递增/递减序列。

我们先把所有的Table都放成下限，接下来我们可以算出它距离总和为0还需要增加多少。对于1<=i<=M，它可以看成这样一个物品：体积为Multi[i]，费用为Pairs[i]，数量为Up[i]-Low[i]。然后就得到一个012背包问题了。

复杂度约为：O(M*背包大小)。其中背包大小不超过M*20*25=200*20*25=100000。

Dominoes

算法是搜索，因为只有有限组问题，可以先在本地得到答案再提交。