程序员进阶之算法练习（十一）有感而发

前言

经过这几年的观察，我发现，国内本科高校的ACM集训队，往往汇聚着该校相对靠谱的那一批人。 拿本校举例，队内的众学长学姐毕业之后，有去国内top2的高校继续读研读phd的，有留学cmu的，也有从G社离职自主创业的，剩下的也基本能去BAT等大公司。。。。不管怎么说，是要比本校的平均毕业生质量好上不少了吧。 我相信对于绝大部分综合智能和自控力没有达到爆表程度的人来说，环境才是影响个人阶段性成就的主要因素。 换句话说，一般人的个人成就，往往是在身边的这批人的平均水平附近上下浮动。 而在这个集体中生活，几年下来所累积的收获，绝不仅仅是和道友们在算法训练上的相互交流、扶持。（更何况大家都是靠自学，一起训练的意义主要还是为了制造竞争的氛围） 更多的是在三观上的互相影响，价值取向上的彼此升华。 和这样一群有趣的人在一起，也并不会觉得万般皆下品，唯有ACM最高。相反，作为一群平日里更喜欢安静地独立思考，反思总结的人，更不容易局限于眼前的某些小格局。 从他们身上，你看见了一个精彩的新世界。 并且因为这群人的存在，你还会不由自主地想要去见识更广大的世界。 相处几年后，也许你会变得志向更加远大，对自己的人生更有信心和抱负。 链接：https://www.zhihu.com/question/31887920/answer/53952912 来源：知乎

一句话，whatever you do, what you do. 不管你是做android、iOS、java、web... 深度能到多深很关键。 如果坚持不下来，先别埋怨自己，看看身边有哪些因素在作祟；找一些志同道合的小伙伴，相互鼓励，寻找更大的生活格局。

正文

hdu 5813

题目链接 题目大意： 构造题。n个点，给出n个点能到达点的数量a[i]，构造一个有向图，满足条件。N (1 <= N <= 1000)

样例解释： 3 2 1 0 表示点1，2，3能到达的点的数量2，1，0； 构造1->2->3 满足条件。

要求，构造的图不能有重边，不能有环。

代码实现 题目解析： 把a[i]从大到小排序，对于第i个节点，能指向所有大于i的节点，最多能到达(n-i)个节点。

hdu 5811

题目链接 题目大意： 有n只monster； 输入一个矩阵mat，表示monster之间的关系； mat[i][j]=1表示i怪物能打败j怪物； mat[j][i]=0表示i怪物打不过j怪物； 注意，mat[j][i]=0 <=> mat[i][j]=1 可以互推，但是没有传递性，A能打败B、B能打败C => C能打败A 是不满足的。

输入m，再输入m个数字，表示挑选出m只monster组成T1队，剩下n-m只monster组成T2队，询问T1队与T2队是否合法 （合法是指存在某种排列，排列中任意一只monster都能打败他右边所有monster）？ 如果合法，最多从T2队中能选出几只monster插入到T1中，并保证T1合法？ 代码实现 题目解析：

要求1，可以用拓扑排序；（O（n^2）） 要求2，先按照T2队从大到小的顺序，求出T2队中每个monster对应在T1队的位置pos[i]，这样就转换成求pos数组的最长不下降子序列；（O（n^2）的dp） 注意1、2、2、3这种序列是合法的，因为原来T2本来就满足顺序要求（排列中任意一只monster都能打败他右边所有monster)；

hdu 5815

题目链接 题目大意： 有一个n个节点的树，根节点为1； m个人从节点1出发，每个人的预算为b[i]，目标点为p[i]； 从节点1到节点i的费用为经过的路径的边的权值； 如果路上总费用超过预算就不去； 现在要求给每条边赋值，要求赚的钱最多。

代码实现 题目解析：

dp[i][j] 表示从root到点i的路径cost为j的最大收益； 那么遍历i所有的孩子k，dp[i][j] += dp[k][t]; t为j到maxCost的值中，最优解； 最后在加上i自己的节点上的cost。

ansDFS是为了输出边的权值。

hdu 5816

题目链接 题目大意： 有n张卡片A，m张卡片B。卡片A的效果是再摸2张牌，卡片B的效果是造成a[i]点伤害； 现在将n+m张牌混合随机打乱。 抽一张牌，当出完抽的所有牌的时候，能造成>=P点伤害的概率。 P (P<=1000), N and M (N+M<=20) 样例 3 1 2 1 2

1/3 解释：三张牌，分别是"抽2张牌"、"造成1点伤害"、"造成2点伤害"; 只有第一张为卡片A的时候，才能造成3点伤害；其他两种可能因为无法抽后续卡牌，无法造成3点伤害；

代码实现 题目解析：

d[j] 表示状态为j的合法数量；(j化为01010，1表示当前牌已经选了） d[j]，枚举i个伤害牌，放入j中，得到新状态jj d[jj] = d[jj] + d[j];

状态j是否合法，取决于当前已选卡片A的数量与卡片B的数量，当A+1>=B的时候，有意义的；(A>=B 表示还能抽一张）

hdu 5818

题目链接 题目大意：给出两个栈A、B，n个操作 三种操作： push A/B x (将x放入A/B) pop A/B (A/B出栈) merge A B (将A、B栈的元素按照入栈时间顺序放入A中)或merge B A， 要求 每次pop时，输出pop的值。 (n<=50000)

代码实现 题目解析：

想法1，每个点存两个指针，comNext一个指向离自己下一个节点，stackNext指向同栈的下一个节点，pop遍历时需要路径压缩； 想法2，两个优先队列，存入<时间，value>的值，合并时选择小的队列合并到大的队列；

这里使用的想法2.

hdu 5921

题目链接 题目大意：有n个数排成一列，对于一个区间[l, r]内的数都增加t，相当于对区间[1, r] 增加t，对区间[1, l -1]减去t（脑补树状数组）。 现在，假设区间按照树状数组的结构存在了a[i]。 为了在区间[6, 6] 增加1，首先是在区间[1,6]增加1 (a[6] 和 a[4] 会加 1), 然后在区间[1, 5] 增加 -1 (a[5] 和 a[4] 会增加 -1)。 结果a[6] 会增加 1, a[5] 会减去 -1, a[4] 不变（一加一减），a[6] 和 a[5] 就是 “really changed point”, 表示区间的修改代价是2。 现在询问在[1, n] 中，所有的合法区间（l<=r)的修改代价之和是多少。 n (1≤n≤1e18).

Sample Input

3 1 2 3

Sample Output

Case #1: 1 Case #2: 4 Case #3: 10

代码实现 题目解析：

首先，1到n的所有区间共有(n * n)/2个。 假如对每个区间[l, r]计算 cost(l-1) + cost(r); 那么1~n每个数字刚好会出现n次。

1到n的所有cost，很容易用数位dp求出来。（枚举第i位从1变成0之后，产生的数字的1的数量，记得加上数字n本身的1）

这中间会出现重复的部分，比如说cost(5)=5+4和cost(6)=6+4, 4的代价是应该消除的； 用repeat[i][j] 表示前i个出现j个1的pair数量； 这样，repeat[i+1][j] 可以用 repeat[k][j]来表示，k在区间[1,i+1]；两个数，我们一个在第k位置0，一个在第k位置1；这样第k位后面可以任意取数字，总共会产生2(i+1-k)位数字，pair数量为2(i+1-k) * 2^(i+1-k) * 2，最后乘以2是因为区间可以反过来； 前面的部分有k位，任取j位为1，其余的为0，总共有c[k][j]种可能。

repeat的数位dp： 枚举第i位，cur表示第i位后面所有数字表示的值，表示能取到的范围； 把第i位从1重置为0，那么会产生2^(length - i)个数字，这部分数字与第i位为1的时候，可以组成pair，且公共前缀为[1, i]，这部分的pair数量为cur * 2^(length-1) * 2； 然后枚举第i位后面可能有共同的1，与[1, i]练成公共的前缀，这部分用到了之前预处理出来的repeat[i][j]；

注意n很大，乘以n的时候要先mod再乘以n。

总结

有时候自己也会思考，日子过一天少一天，天天学习累不累？一直不满足于现状只会让自己不断的追寻，不断在渴求，疲于奔波。 对于自己的疑问，我的回答是：

我的目标，做一个对生活有思考、有热情、有好奇心，对世界有思索、有认知的人。

然后反问自己，日子过一天少一天，天天萎靡不振，一直满足于现状，难道就会让自己不累，不渴求新生活？

虽然我也很菜，但是不妨碍我接着学习。