Link ： ACdream
2014年7月4日，ACdream群赛简单题解。 5道是本弱出的，5道是适牛出的。 写个简单的题解。 具体题解见适牛的详细版！
A：
喵喵的数字
我的做法就是数位DP 数位DP可以求， <=n 里面，二进制1的个数有num个的有多少个，以及他们的和。 然后num从小到大去变化。 然后二分就可以找出第M个数是什么，和也知道了。
1 | /* *************** |
B：
Rankings
DP。 填坑法DP。 用dp[i][j] 表示 前i个里面，出来j个， 但是坑的数量不是j的，需要差值去算。 有明确位置的点，要去除，被占的也去除。 DP直接转移就可以了。 dp[n][0]就是答案。
1 | /* *************** |
C：
喵喵去寻宝
董壕的神几何。 我是用求积分的方法算的，精度误差比较大，我要1e-3的误差才能过。 我就是吧五角星变成10条有向线段。 线段和抛物线求面积。 求交点，然后解析法求积分。 图就不画了，画起来麻烦。
1 | /* *************** |
D：
Maze
最后保留的箱子数肯定是 lcm(n,m)的倍数。 枚举最后的箱子数。 然后使用最小费用最大流去求最小费用。
1 |
|
E：
喵喵的遗憾
就是求斐波那契数列数列取模的循环节。 经典问题。 对于斐波那契数列数列，求其模n的循环节 对于一个正整数n，我们求Fib数模n的循环节的长度的方法如下： （1）把 \(n\)素因子分解，即 \(n = p_{1}^{a_1}p_{2}^{a_2}…….p_{k}^{a_k}\) （2）分别计算Fib数模每个\(p_{i}^{a_i}\)的循环节长度，假设长度分别是\(x_{1},x_{2},……x_{k}\) （3）那么Fib模n的循环节长度\( lcm(x_{1},x_{2},….x_{k}) \) 从上面三个步骤看来，关键就是求Fib数模每个\(p^{m}\)的循环节长度 这里有一个优美的定理：Fib数模的最小循环节长度等于\( G(p)*p^{m-1} \)，其中\(G(p)\)表示Fib数模素数的最小循环节长度。可以看出我们现在最重要的就是求\(G(p)\) 对于求我们利用如下定理： 如果5是模的二次剩余，那么循环节的的长度\(p-1\)是的因子，否则，循环节的长度\(2(p+1)\)是的因子。 顺便说一句，对于小于等于5的素数，我们直接特殊判断，loop(2)=3,loop(3)=8,loop(5)=20。 那么我们可以先求出所有的因子，然后用矩阵快速幂来一个一个判断，这样时间复杂度不会很大。 
这样这个问题就解决了。
1 | /* *************** |
F：
飞行棋
解方程。 并不需要高斯消元一样去解，直接消就可以了。
1 | /* *************** |
G:
喵喵的 Query On Tree
数据是随机的。 就是暴力搞吧。 但是DS太不人道了，数据有很大的概率出现了1. 所以要对树根，就是点1的查询，进行特殊处理。 胡搞下。
1 | /* *************** |
H:
Driving
二分速度。 判断是否可行，然后求时间。
1 | /* *************** |
I：
喵喵的IDE
字典树搞。 很水很暴力。 这需要对每个字典树中的点，维护最近的点在哪。
1 | /* *************** |
J:
Base Station
简单数据结构。 到两个基站的距离，其实就构成了二维坐标。 其中一个按照顺序加入，另外一维用一维树状数组就可以查询了。 不多说了，很水很暴力。
1 | /* *************** |
