程序员进阶之算法练习（二十一）

前言

转眼已经到5月，可是我还没订17年的计划，真是悲伤的故事。 今年还是想花点时间，玩玩题目。 题目不会太简单，也不会太难，简单的如1、2题，难的如3、4题。 *Never enough time, neither the thing. *

正文

1、Efim and Strange Grade 题目链接 题目大意： 输入一个长度为n的字符串表示一个浮点数； 每次可以对浮点部分进行一次四舍五入，10.45 => 10.5； 最多可以进行t次，输出t次进位后，最大的数。 n and t (1 ≤ n ≤ 200 000, 1 ≤ t ≤ 1e9)

** Examples** ** input** 6 2 10.245 ** output** 10.3

样例解释：10.245第一次四舍五入变成10.25，再次四舍五入变成10.3；

** 题目解析：** 首先可以确定，如果小数第一位x[1]>=5，那么直接进位即可； x[1] < 4, 肯定不会进位，因为即使后面进位上来最多x[1]+1=4，达不到进位的条件； x[1] == 4的情况，如果x[1 + 1] >= 5，则可能发生x[1+1]进位后导致x[1]进位；

那么对于第i位： x[i]>=5的时候，第i位之后的数字无意义； x[i]==4的时候，有可能从后面传递过来； x[i]<4的时候，进位停止；

最后在考虑一种特殊情况：进位导致进位的情况，比如说99.9949进位2次，会变成100.00。

2、Destroying Array 题目链接 题目大意：给出n个数字a[i]的数组。(1 ≤ a[i] ≤ 1e9) 给出一个位置p[i]（1<=p[i]<=n），把p[i]对应的数字destroy，数字所在的数组分为两部分。 现在给出n个位置（不重复），输出每次destroy后，最大的数组段数字和。 (1<=n<=10w)

Example ** input** 4 1 3 2 5 3 4 1 2 ** output** 5 4 3 0

样例解释：1325的数组，在destroy第三个数字后，变成13和5，最大的值为5；

** 题目解析：** 每次destroy的操作会去掉一个数字，同时产生两个数字； 先看看暴力的做法： 每次从位置p[i]开始，计算和p[i]在同个数组的左边数组之和sumLeft，右边数组之和sumRight，再把sumLeft和sumRight与其他数组和进行比较； 时间的复杂度是O(N)，总得复杂度是O(N^2);

优化方案： 反着计算！ f[i] 表示 数字i所在序列最左边的数字，sum[i]表示第i个数字所在序列的数字和。 反着来看这个操作，每次插入一个数字，合并数字所在左右区间，然后询问最大的区间和。（并查集）

3、Generating Sets 题目链接 ** 题目大意：**给出一个set，是setY，由n个不同的正整数y[i]组成； setX由n个不同的正整数x[i]组成，现在可以对任意x[i]进行多个以下操作： 1、x[i] = 2 * x[i]; 2、x[i] = 2 * x[i] + 1; 如果经过操作后的setX和setY是相同的，认为setX能生成setY。（按照从大到小的排序后，一一对应） 现在给出n个数字y[i]，求出set X，要求setX的最大数字最小；（如果有多个答案，输出任意一个） (1 ≤ y[i] ≤ 1e9) (n = 5w)

** Examples** input 5 1 2 3 4 5 output 4 5 2 3 1

** 题目解析：** 题目给出的操作意思是：如果x的二进制表示，是y的前缀（y的二进制表示的左边部分），那么x可以转换成y。 现在给出y[i]，在题目的要求中，必然存在一个解，就是x[i]=y[i]； 容易看出，最大的数字最小这个限制满足二分。 现在的问题是，如何迅速判断，在最大的数字不超过mid的情况下，是否存在合适的解？ 这里需要用到一个贪心的性质，如果a>b，那么优先匹配a，并且要在a<=mid的情况下，a匹配的数字尽可能大； 于是可以把数组y[i]排序，从最大的开始匹配，如果y[i]>mid，则y[i] >>= 1，直到出现一个合法的解，添加标记； 如果一个数字y[i]变到0，则无解，因为题目要求是正整数； 每次求解的过程为O(NlogM)，总得的复杂度是O(N*logM*logM)，M是数字y[i]的范围；

4、Research Rover 题目链接 ** 题目大意：** 一个网格，总共有n*m的cell，cell可以上下左右走，一个人带着一个电量为x的电池，从(1,1)出发到(n,m)，随机选择一条最短路径； 有k个特殊的cell，经过这个cell时，电池的电量会减半；（向上取整） 输入n、m、k和k个cell的位置，求到达终点时，电池电量的期望值。（P/Q mod 1e9+7)。 (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 2000, 1 ≤ x ≤ 1 000 000)

Example ** input** 3 3 2 11 2 1 2 3 ** output** 333333342

** 题目解析：** 根据题目的限制--电池的电量会减半，我们知道： 最多有logS个选择。 那么，把障碍点排序（起点和终点也要加入） f[i][j] 表示前j个，经过i个障碍的可能数； g[i][j] 表示前j个，至少经过i个障碍物的可能数； 那么有 g[i][j]=∑f[i−1][k]∗Ways[k][j] f[i][j]=g[i][j]−∑f[i][k]∗Ways[k][j] Ways[i][j]表示i到j的方案数

这里需要用到组合数公式： C(n,m) = A(n,m)/A(n,n)=m! / ((m-n)! * n!) = m! * (m-n)!^(-1) * n!^(-1); 还需要用到乘法逆元的知识：逆元详解

5、Road to Home 题目链接 ** 题目大意：** 在一条数轴上，Bob要学校（点0）走到家（点L），其中有n个路灯，路灯照耀的范围是(l[i], r[i])（路灯的范围不会重叠）； Bob会在灯亮的的范围内唱歌，每次唱的距离为p；（必须唱完，中间必须全部是在路灯照耀范围内） 当Bob唱完一次的时候，下一次唱的地点必须满足以下其中一点： 1、开始唱的地点和上一次唱结束的地点重合； 2、开始唱的地点和上一次唱结束的地点距离>=t;

问最多，能唱几次。 (1 ≤ L ≤ 1e9, 0 ≤ n ≤ 100 000, 1 ≤ p ≤ 1e9, 1 ≤ t ≤ 1e9)

样例的解释

Examples ** input** 17 2 2 6 0 9 13 17 output 5

** 题目解析：** 先看清题目条件的重点：路灯(l[i], r[i])不会重叠，并且唱歌必须在路灯照耀范围内，两次唱歌的距离间隔要么为0，要么>=t； 那么对于bob来说，每到一个路灯的范围内，他需要作出的是否唱歌的抉择： 1、唱歌。需要看当前是否满足唱歌的条件：剩下的路灯距离是否足够p，当前位置和上次唱歌的位置是否满足唱歌的距离条件； 2、不唱歌。对前面没有要求。

那么这里就有一个典型的最优子结构： 假设dp[i]为到距离i能唱的最多次数（并且要求是以唱歌结尾），且区间[i-p, i]是在路灯范围内，那么有： dp[i] 可以由 dp[i-p]转移过来； dp[i] 可以由 max(dp[0 ~ (i-t-p)]) + 1； 这样的状态数为L，L是距离的范围，状态转移的复杂度同样为O(L);

再回归到题目的数据范围，进行数据优化： 其中的max(dp[0 ~ (i-t-p)])，可以采取dmax[i]来表示前i个位置的最优解，这样max(dp[0 ~ (i-t-p)])就等于dmax[i-t-p]; 这样状态转移的复杂度就将为O(1)，但是状态数仍有O(L)，而L非常大；

考虑到路灯的区间性，dp[i]改为到距离r[i]能唱的最多次数，需要注意的是，这里不能要求到r[i]以唱歌结尾，因为以唱歌结尾不满足最优解，比如说(1, 3)的区间，唱歌p=2，此时最优解应该是1次，距离为(1, 2)，而不是唱歌结尾的(2, 3)； 我们引入一个新的变量g[i]，表示dp[i]取到最优解的最左边距离； 这样在状态转移的时候，假设是从dp[k]转移到dp[i]，那么从g[k]开始，连续t的距离不唱歌，然后剩下min(r[i]-l[i], r[i]-g[k]-t)的距离用于唱歌，这里我们用count(L)表示距离L能唱的次数，最后得到dp[i]取最优解的时候g[i]=max(l[i], g[k]+t) + count(L)p*;

对于所有g[k] + t <= r[i]的k，都可以进行状态转移： dp[i] = max(dp[i], dp[k] + count(L)); g[i] = g[k]+count(L)*p+t, L=min(r[i]-l[i], r[i]-g[k]-t) 这样的状态数为O(N), 转移的复杂度为O(N)，总的复杂度仍为O(N^2);

仍然需要进行优化，观察转移的过程，对于dp[k]是固定值，count(L)中的L会随着i的增加而增加，而当L很大之后，dp[k]较小的状态再进行最优化转移是无效的过程，因为dp[k+1]等会是更合适的解； 状态的决策因素有两个,dp[k]和g[k]； 对于dp[k]小，g[k]小的解，不能舍弃，因为g[k]小存在转移的可能； 对于dp[k]大，g[k]大的解，不能舍弃，因为dp[k]大存在转移的可能； 对于dp[k]小，g[k]大的解，舍弃； 对于dp[k]大，g[k]小的解，不能舍弃，因为g[k]小和dp[k]大均存在转移的可能； 以上这四种情况，就是dp[k]+count(L)在转移可能遇到的情况；

count(L)函数是关于L单调递增的函数； 因为对于i < j, 有 r[i] < l[j], 必然有 g[i] <= g[j]，对于i<j, 有count(L[i]) < count(L[j]); 可以看出dp[k]+count(L)是具有决策单调性 ，同时每个决策有一个有效区间r[i]-g[k]-t>=0开始；

那么维护一个决策的队列，根据dp[k]+count(L)可以算出当前所有的有效决策中的最优解； 并且随着r[i]的的增加，从r[i]-g[k]-t>=的队列备选方案中，不断更新决策队列的dp[k]+count(L)；

详见代码：

    deque<int> q;
    q.push_back(0);
    g[0] = -t;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int k = -1;
        while (!q.empty() && g[q.front()] + t <= r[i]) { //每次检测是否进入下一个值的有效区间
            int nl = max(l[i], g[q.front()] + t), nr = r[i];
            if (dp[q.front()] + (nr - nl) / p > dp[i]) {
                dp[i] = dp[q.front()] + (nr - nl) / p;
                g[i] = nl + (nr - nl) / p * p;
            }
            else if (dp[q.front()] + (nr - nl) / p == dp[i]) {
                g[i] = min(g[i], nl + (nr - nl) / p * p); // 同样的dp值，只保留最小的g[i]值
            }
            k = q.front();
            q.pop_front();
        }
        if (k != -1) {
            q.push_front(k);
        }
        if (dp[i] > ans) {
            ans = dp[i];
            q.push_back(i);
        }
        
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;

总结

这几道题比较难，需要花费点时间进行思考。 时间永远是不够的，人生是那么短暂，尽量做自己觉得开心的事情。 做任何事，少带一些利益之心，过程就是最大的收获。