BestCoder Round #5 题解
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1001 Poor Hanamichi</span>
做数位dp是没有必要的，直接从l扫描到r，发现的第一个不满足性质，却满足X mod 11 = 3的数（比如80就是这样的数）就是我们的答案。可以证明扫描的距离不超过10000必然会有答案。O(1)
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1002 Poor Mitsui</span>
按接水的时间，从后往前考虑考虑，两个木桶应该谁前谁后，列出时间的式子，我们需要取使得世间更小的那个，比较后发现应该按 bi/ai排序，而不是贪心按ai排序。（但是貌似第一感觉很可能就是这个。）这题的数据范围出了问题表示十分抱歉，出大数据的时候已经意识到答案会很大了，但是自己疏忽，以为控制好了大数据的答案范围，就不会有问题了。但是，hack的数据是完全不受控制的，题目中的数据范围下，极限数据的范围是非常大，double的精度是不够的。所以标程也是错的了。（标程用的就是double。）
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1003 Poor Rukaw</span>
首先原来的数字是什么并不重要，只关心奇偶性就行了，然后我们发现，每次操作奇数的个数不变或者减2，所以如果当前这轮游戏开始时，有奇数个奇数，那么剩下的肯定是奇数，否则是偶数，所以我们知道，对于一轮数字已经确定的游戏，选手的操作实际上是无意义的。当前这轮的赢家是确定的。所以如果Hanamichi输了，他一定会去掉一个奇数（否则不能改变下一轮的胜负关系，下一轮还是他输，得不到分数，而且轮数越前面，分数越高），然后胜负关系改变。所以我们可以做dp，dp[i][j]表示有i个数，其中有j个奇数的时候Hanamichi的得分期望，dp的转移是固定的。由于组数很多，我们可以记忆化搜索。保证每个状态只算一遍。O(N^2).
Ps：神奇的是这题的答案，期望貌似小数部分永远是 .3333 或者 .66667 或者 .0000。所以我采取了题目中的那种方法避免SPJ。但是我并没有意料到结果具有这样的性质。望大神能给个解释。
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1004 Poor Akagi</span>
注意这题和Mod 1000000009的题目是不一样的。这题5不是1000000007的二次剩余，所以你找不到一个数来替代sqrt(5)，但是我们可以直接在二次域上进行操作，而不是在整数域上。（理论基础这里就默认成立了）我们定义一个pair<a, b>，表示的是mod p意义下的 a+b*sqrt(5)，那么pair之间的乘法，加法什么的都是可以定义的(类似高中学过的复数啊。)然后Lucas序列的通项公式，十分简单，我们只需要把它的K次方用二项式定理展开，然后就可以转化成等比数列来求和了（这个思路和ZOJ上的Power of Fibonacci这题是一样的）。注意公比是1的情况就好了。我们需要预处理阶乘，以及他们的逆元来快速计算组合数。具体实现见标程代码。O(KlogN)
这样应该就能应对很多这类题目了，不管有没有二次剩余。
[title]1001 Happy Three Friends[/title]
Dong-Hao 肯定让 Grandpa Shawn 拿最大的两个。
Beautiful-leg Mzry 肯定会拿剩下的最大三个。
两个比较一下就行了。
当然 6! * 6 * T 枚举全排列也是可以通过的。
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1002 Miaomiao's Geometry</span>
注意首先这个题目有两个 Trick。
1. 二分是不对的，如0 1 4 5 。答案是3 的时候是可以的，但是 2 的时候是不可以的。
2. 答案可能包含 .5 ， 如1 2 5 6 8. 但是答案不可能别的小数。
注意答案只可能有两种情况——要么是已知点的距离，要么是已知点距离的一半。那么我们枚举每个点之间的距离，和距离的一半。先把所有点按照升序排序，然后用枚举的值 X 贪心：
对于点 A[i] ， 如果能放 [ A[i] - now , A[i] ] 就放， 否则就放 [ A[i] , A[i] + now ] .
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1003 Miaomiao's Function</span>
注意到 f(0) = 0 ， 其余的 f(x) = x % 9 ， 如果f(x) = 0 那么 f(x) = 9.
于是 f(0) 肯定是一个 Trick。
那么就需要判定是否 Answer = 0 。 挑选 500 个大质数进行计算，如果答案 Mod 质数 都为 0 。那么就可以认为是 0.
否则对于 9 取摸， 得到 f(Answer) 然后再次进行计算即可。
这里注意一下，题目的第一个版本是求 g(0)+...+g(N)。但是我用Microsoft Azure的话也就能跑出 6 组 f(Answer)=0的情况(N = 0,2755,7243,275608,724390)
并且毫无规律，所以只能改成 L ~ R 的计算。
明显这个数位 DP 满足减法，那么我们计算 L~R 的答案就可以直接 R的答案 - (L-1) 的答案
计算的方式为 dp[N][3] 的数位 dp , N 为位数枚举， 3 为状态：
0.前面都是前导 0
1.下一位应该+
2.下一位应该-
那么状态转移
0 如果当前位是0 转移到 0
0 如果当前位不是0 转移到 2
1 -> 2
2 -> 1
dpnum[N][3] 为此状态下后面有多少个数字，诸位累加即可。
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1004 Protocol Buffers</span>
简单模拟。
首先，我们将message definition中的field definition提取出来，最为简单的方法是，将message definition中的标点符号（{};=）替换成空格，整个definition就变成了message message_name field_rule field_type field_name field_tag ...的形式，去掉开头的message message_name后，剩下的就是每个field的definition了，随便搞搞就可以得到。
之后，对于每一个查询，按照规则模拟将信息获取出来。由于数据保证格式正确且合法，伪代码可以简化至如下：
while 没有结束
读取一个varint
分离field_tag和wire_type
得到field_tag对应的field
if wire_type为varint
读取一个varint
else wire_type为length-delimit
if field_rule为repeated
读取一个int array
else
读取一个string
end
endwhile
剩下的工作就是先判断所有的required field是否都出现，然后再输出结果。
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1001 Task schedule</span>
先排下序，然后记录每个数字出现的位置。
对于询问q，如果q不存在直接输出q
如果q存在。 假设q所在位置为pos，那么二分[pos, n]这个区间，二分判断的依据是如果mid - p == num[mid] - num[p] 那么left = mid+1， 否则right = mid-1
时间复杂度O(m * lgn)
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1002 BestCoder Sequence</span>
将大于M的数标记为1，小于M的数标记为-1，M本身标记为0，则题目就是要求和为0并且包括M的连续序列的个数；用sum_i表示从第一个数到第i个数的标记的和，对于所有大于等于M的位置的i，我们要求小于M的位置的sum_j == sum_i的个数的和即为答案。
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1003 Problem about String</span>
There're 26 letters in English. We need to use bitmasking for the letters. We need one 26 bit number.
If a letter is encountered, we need to toggle the corresponding bit. Then if we achieve the state which we encountered before, that means number of letters in between these states are even. So it might increase our solution by the number of encounters with this state (of course we shouldn't count the same result twice).
'?' character can be nothing or any other letter. So we need to do above operation 27 times. The time complexity per test becomes O(27 * 20000).
Also, memory is a problem. If we use a map structure, time limit will be exceeded. But when array is used, we clear all the state 2^26 a hundered times. This too will will exceeded the time limit. But if we observe that only 20000 states will be used out of 2^26, we can keep track of the saved states and clear only the states which we used.
<span style="font-size: 1.4em; font-weight: bold; margin: 0;">1004 Problem about GCD</span>
If m <= 2 answer is m-1.
Let's assume that m > 2.
Let's split all coprimes in 2 bags:
1) a: a != inv(a, m)
2) a: a = inv(a, m)
b = inv(a, m) <=> a * b = 1 (mod m)
Since all numbers are coprime with m inv(a, m) always exists.
Problem answer is multiplication of answer for both bags.
For the first bag:
If a is in first bag inv(a, m) is coprime with m too.
And inv(int(a, m), m) = a. So inv(a, m) != a is in the first bag too.
So we can split guys in the 1-st bag into pairs (a, inv(a, m)).
Since a * inv(a, m) = 1, by definition, multiplication in the 1-st bag in 1.
For the second bag:
a = inv(a, m) means that a * a = 1 (mod m)
m > 2, so if a * a = 1 we have this: -a = (m - a) != a (mod m), otherwise -1 = -a * a = a * a = 1 (mod m), it's only possible when m = 2.
(m - a) * (m - a) = -a * -a = 1 (mod m), a != (m - a)
Let's denote Q(m) as number of solutions in equation x * x = 1 (mod m).
Again we can split 2-nd bag into pairs:
(a, m - a).
a * (m - a) = -1 (mod m)
So multiplication in the 2-nd bag equals (-1)^(Q(m)/2), we showed that Q(m) is even.
Let's calculate Q(m).
\(m = 2^s * p_1^{r_1} * p_2^{r_2} * ... p_k^{r_k}\), where all p_i are different primes > 2.
Using http://en.wikipedia.org/wiki/Chinese_remainder_theorem we can easily get that:
\(Q(m) = Q(2^s) * Q(p_1, r_1) * Q(p_2, r_2) * ... * Q(p_k, r_k)\).
Using this https://en.wikipedia.org/wiki/Quadratic_residue we can get:
Q(2^s) =
1, if s = 0, 1
2, if s = 2
4, if s > 2
Q(p^r) = 2, where p > 2 is prime.
Q(m) != 1 (since Q(m) is even), m > 2.
So Q(m) is power of 2, so if Q(m) >= 4: (-1)^(Q(m)/2) = 1 and multiplication is 1.
If Q(m) = 2 we have m = 4, m = p^k or m = 2 * p^k.
Since p > 2, m >= p ^ k, k <= ln(p). We can to through all k from 1 to ln(p) check if p is prime.
Complexity is O(log (m) * Q(m)), where Q(m) is prime testing complexity.
It can be Miller-Rabin test with Q(r * log(m)), where r is number of tries).
Total author complexity is O(log^2(m)).
[title]1001. TIANKENG’s restaurant[/title]
按时间从早到晚排序后，遇到到达加上人数，遇到离开减去人数，遍历求出最大值即可。
[title]1002. TIANKENG’s rice shop[/title]
模拟题。当顾客来的时候，天坑如果不在炒饭，那么就给这个顾客炒饭。如果没有顾客到来，那么天坑会一直等待顾客到来，空闲的时候不会炒饭。如果在做的时候来客人需要相同的炒饭那么不会帮这人炒。
[title]1003. TIANKENG’s travel[/title]
若两点之间的距离小于等于l，并且没有其他加油站与这两个点共线并且在这两个点的中间，那么这两个点建立一条权值为1的边。最后求出最短路径即可。判断三点共线的时间复杂度O(n^2log(n))。
[title]1004. TIANKENG’s restaurant(II)[/title]
假设结果长度为L，那么当8^L >= Length(S)时必有结果，可以确定L的最大值。暴力枚举长度为1，长度为2...长度为L。先对S中所有长度为L的子串求hash值,复杂度O(Length(S))。枚举长度为L的字符串，复杂度O(8^L),并用O(1)判断枚举的结果。O(8^L)<=O(Length(S))，总的复杂度O(Length(S))。
