A simple problem again

这个题目数据出水了，导致比赛时一堆人迅速秒杀，其实这题标准做法是，先将要处理的数扩大100倍，当然表达式中的参数也要扩大100倍，然后再利用关系式进行计算，但是要注意的是，最好用记忆化搜索的方式，因为有可能会超时，还有要注意数据有可能含高精度数据，要用字符串读入，另外一个trick是有-000000.000000000000之类的数据，只要注意到这些，AC没问题。

Boys and Girls

这个题主要考察最小割算法，具体构图如下：

先假设一个源点S和一个汇点T，S分别连接到每个男孩，容量为Bi，每个女孩连接到汇点T，容量为Gi，然后男孩和女孩之间有亲密关系的，之间连接一条容量为INF的边，然后对这个图利用Dinic算法求最小割(最大流)，然后再用总和减去这个最小割值即为答案。

Calculate the Sum

用一个数组count记录第一个数的某个数Mod第二行所有数之和。count[i]表示数字i分别Mod第二行每个数再相加的和。后面如果发现已经计算过的数据就不用再一个个Mod，可以直接读数组里储存的值。

据说有人用table[i][j]记录i%j的结果读数组代替Mod运算暴力过了的。

Divide Tree

这个题很综合，首先对图进行一次DFS，生成该图的欧拉序列，然后对该序列构建最普通的线段树，然后再处理两个子问题，一个问题是求一个数的约束个数，一个问题是3N+1问题，只要会了这四点，AC这个题没有问题。

Especial 0-1 String

这个题，主要考察利用AC自动机和矩阵快速幂算法，利用AC自动机构造一个初始化矩阵，这个用AC自动机很容易构造，不懂AC自动机得google之，然后对该矩阵利用快速幂计算即可。

Fake Problem

本题是一个典型的数论题，主要考察了3个数学定理和分治算法时间复杂度的求法。

 首先，对于分治算法，根据主定理：若分治算法的时间复杂度递推式为

T(n)=a*T(n/b)+f(n)（n为问题的规模，f(n)的时间复杂度为Θ（n^d）），则可得：

1. 当a<b^d时，T(n) ∈Θ（n^d）；
2. 当a=b^d时，T(n) ∈Θ(（n^d）*?S(n))；
3. 当a>b^d时，T(n) ∈Θ(n^(?Sb(a))).

三个数学定理式如下（后面两个定理的证明过程较复杂，请查询相关资料）：

1. 若(2^m)+1为素数，则一定有m=2^i，i为非负整数；

证明（反证法）：假设m有一个奇数因子q(q>1)，令m=q*r，则(2^m)+1=((2^r)^q)+1,

令n=2^r，则(2^m)+1=(n^q)+1。注意这儿q为奇数，根据相关定理可得(2^m)+1 (n^q)+1=(n+1)*(n^(q-1)-……+1)),又1<n+1<(n^q)+1=(2^m)+1,故得出(2^m)+1存在一个大于1子且小于自身的因子（n+1），这和(2^m)+1为素数相矛盾。故假设不成立，得证。

1. 偶完全数定理：若p*（p+1）/2为偶数，且为完全数，则p一定为素数，并且有p=(2^i)-1，i为非负整数。倒过来推也成立.
2. 费马小定理：若p为素数，则对任何整数a，有(a^p)%p=a%p。

有了上面这些定理，我想这道题就很水了。

 Gift

推数学公式题。先要把数字里面重复的去掉剩下数字的个数才是我们要的n值。

推出的公式为  2^(n-1) * (n - 2) + 1

计算时可以用数学方法计算，也可以直接连乘，要注意取模。

HELP

从起点到终点的图搜索，并且求最小回合数，就很容易想到bfs。在向有怪物的格子走的时候，需要2个回合。这样，在BFS的时候就需要用优先队列，每次出队列的是离起点回合数最小的位置，用一般队列会出现更新到终点后不是最小的回合数，或者用另外一种更新方式：进队列的时候，不用标记数组标记，在每次有到从起点到该点更小的回合数的时候，进队列。在没有剑或者船的图里，直接从起点搜到终点把蛇和河作为不可达的点。如果有剑，就搜索2次，第一次从起点搜到终点，第二次从起点到剑的位置，再从剑的位置到终点位置，在第二次搜索的从剑到终点的时候就把蛇当作史莱姆处理，看哪次结果更小。有船的图中一个道理，不同的只是把河当成空地处理。在有船和剑的图中，就搜索5次（直接到终点，先拿剑再到终点，先拿船再到终点，先拿剑再拿船再到终点，先拿船再拿剑再到终点），把比较每次结果取最小的情况。

Identify the text

略

 Jump

最短路径问题，先用abs(a[i]-a[j])*abs(i-j)作为I到j的长度。用一个二维数组保存每个柱子到其他柱子需要的体力，再用floyd算法，降每个柱子到其他柱子的体力值更新成最小。对于每个输入的s,e,m判断c[s][e]是否小于等于m就行了。

 KO

不要打错字，就能过了。最好直接复制题目里的原话。