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

前言

趁着8月还没结束，更新一篇算法练习。

正文

1. Alyona and mex

题目链接 题目大意： mex()定义：mex(arr)是 数组arr的最小且不属于S的整数，比如说 mex([0,1])=2； 现在需要构造一个长度为n的数组，元素为非负整数； 给出的m个区间(l[i], r[i])，所有的mex([l[i], r[i])的最小值最大； n and m (1 ≤ n, m ≤ 10^5)。 先输出f(i)最小值的最大值，再输出n个元素； 输出的值在0~1e9之间，如果有多个答案输出，输出任意一个；

Examples input 5 3 1 3 2 5 4 5 output 2 1 0 2 1 0 样例解释：在[1,0,2,1,0]中，mex(1, 3)=3, mex(2, 5)=3, mex(4, 5)=2，最小值是2。

题目解析： 题目要求是所有mex(l, r)中的最小值 最大，我们知道对于mex(l, r)， r-l+1是最大的值。 那么是否存在一种可能，使得r-l+1一定是可以的？

有的，如下： 0、1、2、3、0、1、2、3... 这种构造，只要len>=4，必然是5。

同样，我们找到长度最小的(l, r)，得到len=(r-l+1)，按照上诉的方法构造，必然能得满足条件。

2. Alyona and a tree

题目链接 题目大意： 有一棵树有n个点，根为1，每个点有权值a[i]，每条边有权值e[i]; 两个点u, v, dist(u, v)是u到v的路径距离； 如果u,v 满足两个条件： 1、v是u子树上的点； 2、dist(u, v) <= a[v]； 我们认为u控制了v节点； 求出每个点控制的节点数。(n=20w, a[i]=1e9)

Examples input 5 2 5 1 4 6 1 7 1 1 3 5 3 6 output 1 0 1 0 0

题目解析： 先简化问题： 先看在一个链上的情况，a->b->c->d; 容易知道，a能控制d 可以推出 b、c能控制d； 同时容易知道一个性质：dist(u,v) < dist(f[u],v) f[u]是u的父节点； 并且如果一个点v，在当前u无法控制的时候，在f[u]也无法控制； 于是可以按照(dist(v, 0) - a[v])的值排序，保证一个单调的有效区间，并在dfs的过程中，维护回溯时路径的边长距离的合法。

一句话：点u通过子节点已控制的点，来快速计算u能控制的点，并且结果被用于计算f[u]能控制的点。

3、Arpa's loud Owf and Mehrdad's evil plan

题目链接 题目大意： 输入n个数字a[i]，设定一个操作x=a[x]; 找到一个最小的k，要求： 执行k次，x=a[x]之后，x的最终值是y； 如果对y也执行k次，y=a[y]，y的最终值是x； n (1 ≤ n ≤ 100)

举例： n = 3 a[i] = 2 3 1 那么有，k = 3 （2->3->1->2, 3->1->2->3, 1->2->3->1)

Examples input 4 2 3 1 4 output 3

题目解析： 因为n个数，每个数只有一个出去的选择； 那么对于a[i]，可以连一条边i->a[i]，表示选择； 题目要求就是从i出去的边，能最后指向自己；

那么按照边遍历，如果n个数字能划分成若干个圈即可； 每个圈按照各自的k求出最小公倍数；（因为可以x、y互换，所以如果k%2==0，要除以2）

4.Arpa's weak amphitheater and Mehrdad's valuable Hoses

题目链接 题目大意： n个物品，每个物品有选中代价cost[i]和价值value[i]; 同时有m个关系，每个关系由u和v组成，表示u和v是同一组内； 限制：每一组只能选一个，或者全部选； 现在有一个容量为w的背包，希望选出最大价值的物品组合放入； (1  ≤  n  ≤  1000, , 1 ≤ w ≤ 1000)

Examples input （先输入n、m、w，接下来一行n个cost[i]，接下来一行是n个value[i]，接下来是m行(u, v)的关系 ） 3 1 5 3 2 5 2 4 2 1 2 output 6

题目解析： 如果不考虑限制，就是普通的背包； 加上限制，就是一个分组背包，背包是默认都懂的。（搜一下“背包九讲”，有讲得很好的文章） 同一个组的可以用vector存起来，减少遍历的时间。

5. Arpa’s overnight party and Mehrdad’s silent entering

题目链接 题目大意： n对情侣坐成一圈（座位编号1和2n相邻），现在有两种食物（1和2），要求： 1、情侣不吃相同的食物； 2、连续的3个人必须包括2种食物； 输出一种可行的方案。 (1  ≤  n  ≤  105)

Example input 3 1 4 2 5 3 6 output 1 2 2 1 1 2 样例解释： 3表示3对情侣； 接下来是3行，分别表示情侣的两个座位； 输出： n行，每行表示情侣的食物； 如果无解，输出-1；

题目解析： 假定我们制定一个规则，先满足情侣不同的条件，当填入情侣中一人时，必然在另外一个位置填入相反的食物。 我们采用这样的一种构造方式： 座位从小到大分配食物，优先满足情侣的要求； 其次，相邻的位置填入相反的食物；（贪心） 最后如果出现111的情况，就选择中间的位置对调。（事实没有出现的111的情况，这里如果有人愿意证明下，非常感谢）

总结

背包作为CF-div1的第二题，只是几年前中国的dp入门题。

最近是越来越忙，工作之余的时间，要学习工作相关的技术，要储备行业相关的知识，要探究自己想思考的领域，要娱乐放松自己，还要留出时间陪伴家人。 看起来比较优化最好的选择是，把技术学习和行业知识储备结合，把陪伴家人当做娱乐，最后空余的时间用来思考和总结。 哇，这个太难了。