Problem A – Group II

GroupII 解题报告，点击下载。

Problem B – Build Garden

此题虽然有4个变量，但实际上只有奇偶两个，

假如开头为1，则 1 3/4 1/2 3/4。。。这样循环下去，

然后若是2开头，则是 2 4 1/2 3/4。。。就是前两项不同，这样我就把每一项看成一个奇偶的bool变量，

而3或4开头和 1或2开头是一样的。只用考虑1,2开头的情况。

然后相邻的两个不能出现2.3这种情况即可，然后对于前两项单变量的问题，就连一条opp[1]->1的边，将opp[1]屏蔽。

然后对于约束条件，一些人颜色不同，既任意两个颜色不同，拿出来单独处理，若是1/2 与3/4 则无影响，

若是两者位置相差为偶数，则不能同奇或同偶。这样就行了

Problem C – Emergency relief

枚举+记忆化搜索。时间复杂度O(N^2*2^N)。但在提交的代码中发现有复杂度O(N*2^N)，惭愧呀……

Problem D – marshmallow

一个比较简单的博弈题，必败态为(i = j && i % 3 = 0) || (abs(a – b) = 1 && (a + b) % 3 = 0)（i、j分别表示取出红色、蓝色棉花糖的个数），求出n*m总组合中必败态的个数，再与n*m约分即可。

Problem E – Projection

在平行的平面簇上AB和CD的投影是一样的，这些平面簇可以用他们的法向量表示。所以只需要看沿着哪些向量看去AB和CD是有交点的。可以发现沿着AC、AD、BC、BD看去AB和CD恰有一个交点，而且由aAC+bAD+cBC+dBD(a,b,c,d>=0)表示的向量均是沿着看去，AB和CD有交点的方向。而aAC+bAD+cBC+dBD的向量簇的集合正是以AC.AD.BC.BD为棱的四棱锥，我们不妨将此锥顶点放在原点，将其和圆心在原点的球相交，求出此锥和球相交的面积，再除以半球表面积，即可得到所求概率。

PS:上述球面四边形的面积可化为球面三角形面积，具体公式可以上网查。

Problem F – Just Another Game

初学博弈论，于是也出了一道相关类型的题目。题目看起来很虎，其实稍微分析一下，就可以得到结果：

1）一开始，如果桌子上有大小为一的石子堆的话，那二名选手首先要把这些堆取完，这时毫无策略可言。

2）取完大小为1的石子堆之后，如果桌子上还有石子堆，那么下一个取石子的选手必胜，因为可以根据是否还有石子堆分别去整一堆，或者取剩一颗石子。

本题要统计先手必败的局面有多少个，其实就是问把一个数N拆成K个数相加，且要求有奇数个1的方案数。有一点要注意的是，当全部是1时，1的个数要是偶数，这是很显然的，但也是容易忽略的一个trick

剩下的工作就是dp了，O(N^3)即可。

Problem G – Detonated mines

如果地雷A和地雷B的距离小于等于A的引爆距离，就建立一条从A到B的有向边。这是一张单位边的有向图，然后枚举手动引爆的地雷，做一次bfs得到需要最多次数引爆的地雷。然后在所有最多的次数中去最小的一个。

Problem H – Random intersection

将所有线段按起点x或y轴排序，假设是x轴，枚举每一条线段，将所有起点的x轴大于枚举线段终点x轴的线段都舍弃，试验其他线段是否相交就可以暴力出解。

Problem A – Group

【题目大意】

N个数排成一列，不改变其顺序的将其分成不超过K组，每组至少要含有L个数。现从左到右数过去第i组的值为其含有的所有数的和，与i的乘积。要求将所有分出的组的值加起来的权值最小。

【数据范围】

1<=N<=20000  1<=L<=200  1<=K<=100

【解法】

根据题意，可以很容易的想到一个朴素的动态规划转移方程

f[k][n] = min{f[k-1][i] + (s[n]-s[i])*k} (0<=i<n)

f[k][n]表示前n个数分成k段的最小权值

但这样做的时间复杂度为O(N^2*K)约400亿，必然会超时，另外空间复杂度O(N^2)也超过了限制。

下面优化时间复杂度：

首先将方程进行变形，因为s[n]和k与变量i无关，故可以提取出来，得

f[k][n] = s[n]*k + min{f[k-1][i] – k*s[i]}

观察方程我们发现，在k固定的情况下，无论在算一个什么样的n的时候，进行枚举i，只要i值是固定的那么f[k-1][i]-k*s[i]就是固定的，因为他与n的取值无关。

这样我们可以发现在算f[k][n]时需要算min{f[k-1][i]-k*[i]}(0<=i<n)，但我们在算f[k][n-1]时其实min{f[k-1][i']-k*[i']}(0<=i’<n-1)其实已经算过 设p = min{f[k-1][i']-k*[i']}(0<=i’<n-1)，那么min{f[k-1][i]-k*[i]}(0<=i<n) 其实等于 min{p, f[k-1][n-1]-k*[n-1]}，这样便成功的将min{f[k-1][i] – k*s[i]}值的求值时间降低到O(1)，因此整个方程的时间复杂度为O(N*K)

下面优化空间复杂度：

观察方程，我们f[k][n]中，k固定，其实所有f[k][n]的值只与f[k-1][*]有关，那么算出的所有f[0..k-2][*]在算完f[k-1][*]后就可以丢弃了，因此本题我们可以采取滚动数组的方法，每次只记录上一维算出的值，将空间优化到O(N)。

【最后】

比赛中，本题的测试数据发生了比较严重的问题，其中一组数据的L值为负值，导致了很多人的很多正确的程序一直无法AC，向受到影响的同学表示深深的歉意，希望博得大家的原谅。向比赛中向我提供数据错误的信息的hoopchina同学表示感谢。

Problem B – Repetitions of Substrings

我是根据受到下面两个题的启发才出的这个题，由于只跟暴力程序对拍了小数据，而且比赛中也有很多人质疑数据的正确性，我很担心是不是弄错了。
我会把标程和数据公布出来，如果真的是数据错了，我表示很抱歉。

//////////////////////////////////////////////////////

首先题目意思是：给定一个字符串S和一个K，要求统计这个字符串重复次数大于等于K的子串的个数。

每一个子串都可以用一个区间[l,r]表示，下面都将用[l,r]来表示左右边界分别为l, r的子串。

如果枚举每一个区间，然后判断它的重复次数是否不小于K，这样复杂度至少是O(N^2)的。
试着换一种思路，枚举字符串的周期长度l，然后统计有多少个区间满足重复次数大于等于K。

对于当前枚举的长度l（从小到大枚举）：
如果一个字符串的重复次数>=2，它肯定包含S[0], S[l], S[l*2]…,S[l * (n / l - 1)]这n/l个字符中相邻的两个。
于是就可以枚举这两个相邻的点S[i], S[i+1]，设它们最多向左能匹配的长度len_left, 最多向右能匹配的长度len_right。（这个可以用后缀数组实现）
然后可以得到一个区间[i - len_left + 1, i + len_right - 1 + l]，这个区间内长度为l*K, l*(K+1), l*(K+2),…的任意一个子区间都是满足条件的。

现在问题转化为对于一个区间[a,b]，求长度为l*K, l*(K+1), l*(K+2),…的子区间一共有多少个。
对于这个子问题：设len = b – a + 1, cnt = len / l, 则长度为l*x的子区间，它的可选起始位置有len – l * x + 1个。
ans[l] = sigma(len – l * x + 1) (K <= x <= cnt)
= (len + 1) * (cnt – K + 1) + l * (K + cnt) * (cnt – K + 1) / 2

上面步骤的时间复杂度为(n/1 + n/2 + n/3 + …) = O(nlogn)
为了避免重复统计，用了set。所以总复杂度大概为O(n(logn)^2)

注意：
1)不要重复统计，如abababab，对于l = 2, 和l = 4都会统计到它，但是只能算一次，可以用set来保存已经算过的区间，以免重复统计。
2)因为S长度可达100000，答案有可能超int。

Problem C – Dartboard

Problem D – Rubiks

题意是：有一些魔方，知道其价格和价值。同时在此基础上，一些魔方组成魔方系列，如果你买了整套的话总价值会在原来的基础上得到提升。在经典的0-1背包问题上做了加强。

还是使用动态规划。具体状态转移过程举例说明如下：

Input:

6 100

1   2   3   4   5   6

10  20  30  40  50  30

2

2 1 3 50 (家庭A)

2 2 4 40 (家庭B)

过程：

1、初始化：去掉家庭A、B，剩下的有 5、6 两个。将这两个的各种组合放入下面表格里。

表格1

2、依次插入各家庭到表中。例如插入家庭A：

先将家庭A的成员单独插入。插入 1

（对表格一中各个元素都加上当前成员，对于同样Price的，大价值把小的覆盖掉，如上图红色的）

插入3（注意：使用的表是插入 1 之后的表）

表格2

插入家庭A（看作是Price为4，Value为90的一个整体）。（注意：使用的表是原始的表）

表格3

然后，将新得出来的 表格2和表格3，合起来：

然后，按照上面的插入方法，继续插入剩下的各个家庭。

最后表中Value中最大的即为Output。

Problem E – Super Chorus

一列人，去掉一些，使剩下的人回文（身高和性别都要考虑），并且身高成倒V字型（中间高，两边依次严格递减），求剩下的最多人数。

Greatest Common Increasing Subsequence问题的变形，必须使用O(n^2)的算法。

用dp[i][j]表示第1个人到第i个人和最后一个人到第j个人这两个区间的最长公共上升子序列的长度，该子序列必须包含第j个人，要求i<=j

则

初看状态转移方程感觉是O(n^3)，其实不然，dp[i-1][k]的最大值是可以边DP边求解的，故复杂度为O(n^2)。答案也必须在DP过程中求解。

Problem F – Push Over

【题目大意】

从平面上S点出发,经过A点和B点，到达T点。经过A,B的方向都已给定，要求路径上任意一点曲率半径不能小于R，请规划一条最短的路径

【解法】

可以看出，若要路径最短，路径应由直线段和曲率半径为R的圆弧构成

首先枚举是先经过A还是先经过B。现假设先经过A，后经过B。计算后可交换A、B再算一次。

路径由三部分构成。S到A，A到B, B到T。第一和第三部分是一类，第二部分是一类。

1. A -> B: (两个点都确定了路径的方向)按照经过A和经过B的方向，可以过A和B分别做两个圆，使得在A、B处的切线的方向恰和经过路径经过它们的方向相同，然后尝试做内、外公切线，将这两个圆连起来。实现A路径到B路径的转移。
2. S->A, B->T: (有一个点没有确定路径的方向，而有一个则确定了。) 以S->A为例，我们过A做圆（同上一类）,如果S在圆外，则直接向该圆引切线，将S的路径引向A的路径；如果S在圆内，情况则较复杂，可以证明，按下图这种方式,由S按红线走到A路径最短。

细节上有些问题要处理，例如做圆后两圆重合怎么办。具体可以参见测试数据的路径画图示范。

Problem G – The XLPT Registration System

Problem H – Uiwurerirexb jeqvad

原文：

Substitution cipher

Description

Last few months ago, I enjoyed Challenge problems in hacker.org, in which there are many cryptography problems. Among these problems there are many using substitution cipher method. To know more about it, I went to Wikipedia:

In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the “units” may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution.

Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, the units of the plaintext are rearranged in a different and usually quite complex order, but the units themselves are left unchanged. By contrast, in a substitution cipher, the units of the plaintext are retained in the same sequence in the ciphertext, but the units themselves are altered.

There are a number of different types of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed polygraphic. A monoalphabetic cipher uses fixed substitution over the entire message, whereas a polyalphabetic cipher uses a number of substitutions at different times in the message, where a unit from the plaintext is mapped to one of several possibilities in the Ciphertext and vice-versa.

This time I give you such a problem, in which Description, Input, Output, Sample Input are all ciphertext, whereas Sample Output is using plaintext. Of course, this problem is using simple substitution cipher and monoalphabetic cipher.

To solve monoalphabetic cipher efficiently, you can refer to http://www.secretcodebreaker.com/SCBSolvr.zip

Input

The input contains multiple cases. Each case has only one line – ciphertext with no more than 100 characters.

In each ciphertext, there are only lower letters and spaces.

Output

For each case, output one line – the plaintext corresponding to the input. Remember that leave spaces alone.

Sample Input

g g g

Sample Output

q q q

    首先为本人很挫的英语向各位看题看得郁闷的大牛深表歉意。
    由于本人能力有限，比赛的筹备一直到赛前30分钟才弄好，并且没有仔细检查题面和数据出现的问题，特别是E题，数据和题面均出现较大问题是本人准备工作没有做到位，还请各位大牛海涵。
    另外，十分遗憾的是，原本所出的一道求圆和多边形面积交的计算几何题不小心和武大等校的十校联赛第10场中的某题本质一样，并且已作为训练题给大家练习，所以不得已临时换题，在此特别向补上计算几何题目空缺的Isun大牛表示感谢。
    下面简单评述本次比赛，并给出简要解题报告：
    本次比赛大部分题目不难，主要解法均为基本算法，部分题目可能需要注意细节，部分题目题面出得有点猥琐。但总体来说，算法覆盖面比较广，没有侧重考哪一方面的算法。所有题目的解法覆盖 搜索、动态规划+线段树维护单调性优化、背包、高精度（或Java大整数的应用）、基本最小生成树、字符串的细节处理、AC自动机、 简单数制转换、计算几何。
    其中E、G属于水题，D题可能题目描述没说清楚，抱歉，C题有点小麻烦（Java可能好点），B、F、H属于较难题，A题属于较巧妙题。
    在3小时40分钟的时候被电子科技大学的队伍全切了，是命题中的失误。但F、H被迅速解决，A题撑到最后是意料之外的。总得来说他们还是很强的，这里小小的赞许下，基地的队伍也要加油啊。
    下面是解题报告，其中F题由Rocket323提供，H题由Isun提供：
    A题，整场比赛中很少有人开动的一题，也是AC队伍最少的题。最初一看题，状态数无论怎么算都是一个暴大的数。仔细想想，也只能猜测要达到目标走的步数不会很多，但并不能确定上限是多少。DFSID?经验证数据最多走7步即可出解，7^7大约80万，但题目给出了10000组数据，不出意外的话，应该会TLE。另一个想法是双向广搜，首先最多7步出解这个很难证明，然后双向广搜很难写，然后10000组数据话应该会很悬。其实换种思维方式，如果我们在移动某种颜色的时候不考虑其他颜色，那么这种颜色在魔环中的状态数只有C(20,4)，只有4845种状态，这样已经没有状态压缩的必要了，当然如果会写排列数生成，用用也无妨。只要从目标状态开始BFS，把4845种状态到目标状态需要的最少步数求出来，不需要多少时间。而题目所求无非是5种颜色，分别处理取5种颜色里面的最小值就是解了，如果之前预处理了，这里的效率应该只是常数级的。
    B题，过得人很多，有些意外。之前写的时候有想过要把某些可能退化到N^2的算法卡掉，后来不记得加强数据了。这题我的做法是，设w(i,j)是从i到j的Value的最大值，那么固定j，i从1枚举到j，w(i,j)一定是单调不上升的，再使用一个队列来处理Point的情况，用线段树来处理值，可以做到NlogN。
    C题，枚举的话可能要100^4，加上这题需要高精度，就会TLE。这题我的做法是背包，再写一个高精度。这题用Java的人会比较方便，其实时限如果开小点Java也可能会TLE，这里特意放过的。
    D题，可能题面没写清楚，如果看懂了就知道是一个不需要任何优化的N^2的最小生成树问题，需要注意的是在求两个灯塔之间的距离时，如果是用int来求double，很有可能中间值越界。
    E题，出问题最多的一个题目，其实是很水的题。当时看到很多人RE,WA，后来一查数据才发现，本来要加入11750个数的一行手误多加了10000个，本题没加特别的数据来刁难人，但还是有很多人在这上面郁闷了。
    F题，原本我是想出成AC自动机＋状态dp的题的，后来有神牛用了很诡异的方法彪悍的过掉了，看了一下他的代码，貌似是枚举m个不合法的串的组合形式，然后统计？
我的做法是f[i][j]表示目前状态为i，且走到了自动机的第j个节点用多少种方法，然后枚举下一个数字转移，貌似时间不是很好，窘。。。
    G题，就是一个简单的数制转换的题目，想清楚本质应该是很简单的水题。
    H题，我的方法是:以三角形2为基准,如果
1.三角形1有两个或以上顶点落在三角形2所在平面，则输出NO
2.三角形1恰有1个顶点落在2所在平面，那么(这个顶点在三角形2内)和(这个顶点的对边穿过三角形2)两者恰有一个为真时，输出YES
2.三角形1没有顶点落在2所在平面，那么当且仅当三角形1有且仅有1条边穿过三角形2时,输出YES。
这个题提示大家3D几何的模板也要精心准备。很多AC的代码都很短，应该有更简洁的方法。

===========================
筹备这次月赛，花了不少时间，但也学会了很多东西。
细节很重要，英语也很重要。
预计时间从8月3日一直拖延到8月21日，导致本次比赛不可能在呼喊生日邀请赛，不得不说是一种遗憾。十分狼狈的是直到比赛前半个小时还在测数据是否正确也是导致了某些不应该发生的悲剧发生的原因。
校内最强的kissworld同学精准的提交和高AC率实在让人敬佩。但这次比赛我们过得最多的队伍也只有4题，跟外校比起来确实也是一种差距，大家要加油了。

另外，本次比赛得到了很多大牛的协助，特别向Rocket323、Isun、yh等同学的协助表示感谢。同时也感谢各校牛队的捧场。

在比赛的时候，最后一题死活没想清楚，虽然最后还剩下30多分钟，但还是没能弄出来，而网络同步赛不少人不到两个小时就全切了，差距啊。。继续努力吧。

A：
话说AC的程序复杂度让出题者气得吐血，N^2, N^2logN, 甚至是N^3…不说了，反正怎么搞都过，呵呵。。。

B：
最长递增子序列，经典O(NlogN)的算法。

C：
多处理器的调度问题：给你N个任务，每个任务都有一个开始时间s，结束时间t，问在每个处理器的任务时间都不冲突的前提下，至少要用多少个处理器来完成所有的任务。
贪心，先把任务排个序(先按开始时间递增，再按结束时间递增)，用一个数T[i]代表一个处理器，表示该处理器最后一个任务的结束时间，
线性扫描各个任务i，对于当前任务，在现有的处理器中选出这样一个处理器x：“T[x]是小于s[i]的数中最大的一个”。然后把T[x]替换为s[i]
如果找不到，则要新增一个处理器处理当前的任务。
以上过程我是用multiset还维护处理器的顺序的，所以比较慢。好像有的大牛是用排序就搞定了，orz.

D：
题意仿照五子棋的规则，给出一个局面，问下一步谁有可能获胜，其实就枚举一下水平，垂直，对角，反对角的几条线判断一下就行。
比赛时WA了几次，主要是被那个exactly给害的，原来要求只能有6个连成线才行，多了还不才行。。。没看清题意啊。

E：
当水的状态达到平衡时，水位分布形成若干个大块，设其分划点分别为: Pi1, Pi2…, Pir
而且各块的水位递减，即 h[Pi1] > h[Pi2] > … > h[Pir].
于是可以维护一个栈，对于当前一个位置Pi(1<=i<=n)：
1)如果水还足够，就一直从栈顶上删除元素(存的是位置Pi)，直到栈顶元素的高度比当前位置要高，这时记录一下它们之间的前驱后继关系(其实就后继就行)。
2)如果水不足够，就看水能填到哪里就是哪里，这个只要认真考虑一下，问题不大。
然后，根据记录的前驱后继关系，就可以得到之前所说的分块，而每个分块的水位是最右边的位置的高度h[i],最后一个分块有可能要特殊处理一下。

上海邀请赛来的队伍主要是上海，福建和浙江的队伍，其他地方来的就不是很多了。总共104支队伍，其中上海交大来了5支，复旦5支，同济大学6支。我们 Hust来了两支队伍，CFOP和RushTime。命题组长是复旦的杨溢。结果排名在（http://acm.dhu.edu.cn/dhuoj/rank/contest12.html）

上午的热身赛时间不多，就测了一下机器，java，还试了一下clock()，不过交的时候出现一些诡异的问题。

下午的题目小分析一下：

• A题求一个有向图去掉一些边后有根树的总数，总共8个点，wsl枚举一个点的父亲是哪个，8^8的复杂度，AC
• B题是最水的一个题，确定是半圆就行了，略。
• C题是一个计算几何题，放置一个给定三角形和圆，使相交的面积最大，这个题没有好的想法，到最后也没人交过。
• D题是一个概率题，这个题卡了我们不少时间，当时过了4个题，排名靠前，但是好多队过了的D题我们没过，我和wsl都在一起想这个题，却没有好的想法，我 们试了一些简单猜想（全修，全不修）但是都返回的Wrong Answer。后来wsl试了枚举中间点分别用不同的策略，又WA了一次后过了，这题过了，士气振了不少，赞wsl。
• E题是求所有化简后不同的式子有多少种，感觉很复杂，没有好的想法，场外同步赛有人过了，现在还不知道解法。
• F题是分解2^n-1，找到了很多小规律，是到最后快结束时才在讨论中Isun发现了一个关键规律（还不能证明），已经没有时间写了，而且我们的想法实现要用多项式除法，会比较麻烦。场内最后上交的排第一的队伍过了。
• G题是一个枚举加模拟的题，就是常见的一个游戏“对对碰”，关键是要想清楚细节，我写的，很早就开始写了，过的也算早吧，就是麻烦和细节，没有太多技术含量。
• H题我没有看，但是听他们说相当于在线段树的基础上变化一个操作，这个题感觉有难度后，就没有仔细考虑了，最后也没有人过。
• I题是求一定范围内的每个数可表示成幂的指数和。方法是先求出1~n中的值，由i^k <= n，n <= 10^18，有k <= 59，那么就可以求出对每一个k底数i的种数。但是一个数能表示成某个数的50次方，那么也就可以表示成一个数的25次方，5次方…一个指数和其约数 作指数时在统计时是重复的。那么从大到小处理时依次减去就行了，例如算指数50时，就将1，2，5，25，10对应的数量减去此时50对应的个数就行了。 本题由Isun一次AC，赞~
• J题也是Isun较早时间一次写过，求的是一个钟三根针重心随时间变化的轨迹长度。模拟的方法。

track: http://hi.baidu.com/greatadam/blog/item/11a46216f34baf4220a4e9b6.html

PKU2373 Dividing the Path / USACO 2004 December Gold

题目意思大概是
用给了上下界(A,B)的长度木板不重叠地覆盖一段区间[0，L)(木板的长度和区间的长度都是离散的),区间长度L,而且有些区间必须整块地由一个木板覆盖,这种区间有N个,每个的区间表示为［Si,Ei).
问至少需要多少快木板.
其中，数据范围为：1 <= A <= B <= 1000. 1 <= L <= 1,000,000, 1 <= N <= 1000, 0 <= S < E <= L

拿到这种最优解问题，一般最先想的思路是动态规划。在区间的每个点上，保存从起始位置到该点的一个最小覆盖个数，然后根据前面的计算结果扩展最优解。但是，每个点状态转移需要进行（B-A）次操作，一共有L个点，最快情况下，需要进行10^9数量级的计算，会超时。

我们不难发现，这个问题也可以用bfs进行搜索。因为区间中的点可以根据可达性关系建成一个有向无环图。两点p1->p2可达的定义是，两点p1,p2都不在任何一个开区间(Si,Ei)内，而且A <= p2-p1 <=B.于是可以在图中广搜，对于每个节点记录它到起点0的距离。然而，如果直接枚举所有木板的长度然后判断落点是否合法，复杂度跟上面的动态规划是同一个数量级。

现在的问题就是，如果避免走到那些已经找到最优解的节点。我的做法是使用双向链表，当然不是单纯的链式的双向链表，因为它不支持随机访问。对于每个节点，定义三个成员：next, prev, able,分别表示该节点的下一个节点、前一个节点、是否使用。未禁用的节点next,prev分别指向下一个和上一个未禁用的节点(若不存在，则为-1)。禁用的节点的next指向下一个节点，下一个节点的是否使用未知，当然，我们是希望它尽量地指向未禁用节点（因为只有未禁用的节点才有使用价值）；禁用节点的prev指针类似。通过这种数据结构，我们可以方便地进行两种操作：1、常数时间删除节点 2、线性地迭代未禁用节点 3、log n的时间内找到一个大于或者小于某个数值的未禁用节点，实现的方式类似于并查集。

初始化时，线性扫描，将未包含在区间(Si,Ei)中的点顺序存放在链表中。然后进行bfs，并维护未访问链表。先在队列中插入原点0，并从链表中删除0。然后，每次从队列出一个节点p，先找出在链表中大于等于p+A的节点，然后依次迭代链表直到位置越界。将迭代的所有点进队列并从链表中删除。这样下来，期望的时间复杂度是O(L*log(L))

编码中还有些细节需要注意，比如所有的覆盖区间的长度都必须为偶数。

若有其它方法欢迎讨论。

昨天晚上，或者说今天早上做google code jam 第二轮，题目明显提高了一个层次.
第一题是简单的dp,第二题可以构造,第三题二分答案,第四题三维的状态dp.

(1)第一题：Cheating a Boolean Tree
题目大意：在一棵满二叉树，在叶子节点定义了一个bool值,在每个非叶子节点定义了：一个操作,他的bool值等于左孩子的bool（操作）右孩子的bool。
有些节点的操作可以改变，要求改变最少的操作使得这棵二叉树满足要求根结点的bool为给定的。
按照题意,每个节点记录两个状态，从下往上DP。

(2)第二题：Triangle Areas
题目大意：在一个n*m的网格中，是否存在面积为A/2的三角形，使得三角形的所有顶点都在整点上。
构造：对于A：
如果：A>n*m 肯定不可能
否则：如果A%n==0,则构造为：(0,0),(0,n),(A/n,0);
否则 够造： (0,0),(n,1),((n*m-A)%n,1+A/n);
非常之巧妙

(3)第三题：Star Wars
题目大意：对于平面的点集，找出一点使得到所有点的“距离”(|xi – x| + |yi – y| + |zi – z|) / pi，最大值最小。
这道题当时想了很长时间都没有什么思路，比赛结束看别人的代码才知道其实二分枚举答案就可以了。
那么对于一个距离d,我们怎么判读是否存在一点使得所有的点到该点的“距离”都不大于d呢？
这就与我们的hamiton距离有关了。
(|xi – x| + |yi – y| + |zi – z|) / pi<=d
–> |xi – x| + |yi – y| + |zi – z|<=d*pi
–> xi-x+yi-y+zi-z<=d*pi
xi-x+yi-y+z-zi<=d*pi
xi-x+y-yi+zi-z<=d*pi
x-xi+yi-y+zi-z<=d*pi
xi-x+y-y1+z-zi<=d*pi
x-xi+y-yi+zi-z<=d*pi
x-xi+yi-y+z-zi<=d*pi
x-xi+y-yi+z-zi<=d*pi

–> xi+yi+zi-d*pi<=x+y+z<=xi+yi+zi+d*pi
xi+yi-zi-d*pi<=x+y-z<=xi+yi-zi+d*pi
xi-yi+zi-d*pi<=x-y+z<=xi-yi+zi+d*pi
xi-yi-zi-d*pi<=x-y-z<=xi-yi-zi+d*pi
这些平面有交集。

–> max(xi+yi+zi-d*pi) < min(xi+yi+zi+d*pi)且
max(xi+yi-zi-d*pi) < min(xi+yi-zi+d*pi)且
max(xi-yi+zi-d*pi) < min(xi-yi+zi+d*pi)且
max(xi-yi-zi-d*pi) < min(xi-yi-zi+d*pi)

(4)第四题：PermRLE
题目大意：给定一个字符串是k的整数倍长，第一个0->k-1排列的变换(如：{3,1,4,2} to the block “abcd” yields “cadb”.)，
使得最后字符串中连续相同字母的段数最少。如：aa|b|c|aaaa四段。
题目的难点在与相邻的两个k段会相互影响。
所以先考虑段内的情况见图：节点数为K，边（i,j,sum）,sum为所有k段中第i个字母和第j个字母不同的对数。求所有i-j的hamiton最短回路。
在考虑段之间的影响，对于i-j的哈密顿周游，如果前一个k段的第j个元素等于当前段的第i个元素，则总段数减1。
最后求一个最小值。
求i->j的hamiton最短回路，使用2^k*k^2的状态dp。
详情可以先思考一下题目。

当然这套题目很灵活，每道题不只一种解法，我只把我所理解的东西写下来，与大家分享，不足之处请不吝赐教。

Hoj1080  The length 解题报告
这道题的意思很简单，其本质就是求出n个点到某个点的最短距离的最小值。
这道题的大众解法是从那30个点反过来Dijkstra，然后优化一下，当给定的n个点全部退出优先队列后Dijkstra终止，这种算法在5S之内跑完是没问题的。
但我出这这道题这本意不是这样，如果把题目中的V2中的点数改成300或者更多，上面这种解法肯定是要超时的，像这类问题有一个简单并且快得多的算法，在本题中，把那300个点一开始全部入优先队列，并把他们的最短路径赋值为0，然后一遍Dijkstra就行了。
大致说明一下这种解法的正确性。Dijkstra是一种贪心算法，每次从队列中都是取出的路径估计的最小值，也就是说各点的最短路径都是按照最短路径长度递增的顺序求出来的，最开始把那300个点的路径值赋为0就相当于把这几个点的最短径已经求出来了（因为他们到V1的最短径肯定是为0的），这是不违反“各点的最短路径都是按照最短路径长度递增的顺序求出来”（因为0肯定是路径最小的）这个要求的。

首先计算两个多边形的交的面积，两个多边形的面积的和减去交的面积即为并的面积。

交的求法：
将两个多边形分割成若干三角形，对所有分属两个多边形的三角形求交，将所有交的面积加起来即为两个多边形的交的面积。（三角形的交可用半平面交计算。注意面积有正负。）复杂度为O(n1 * n2)，n1 n2都很小，求平面交的效率直接影响了整体的效率，写的痤的就有可能超时。