前言
趁着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入门题。
最近是越来越忙，工作之余的时间，要学习工作相关的技术，要储备行业相关的知识，要探究自己想思考的领域，要娱乐放松自己，还要留出时间陪伴家人。
看起来比较优化最好的选择是，把技术学习和行业知识储备结合，把陪伴家人当做娱乐，最后空余的时间用来思考和总结。
哇，这个太难了。
网友评论