CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== codeforces round 661 ======
=====A Remove Smallest=====
题意：给一串序列，每次取出两个数，如果这两个数满足相差不超过1，则取走较小的那个数，否则不做操作，问是否能够取到只剩下一个数。

题解：排序判断是否两两相差$1$即可

=====B Gifts Fixing=====
题意：给两串长度相同的数a,b,每次选中i，可以做三种操作中的一种，$a_i$减一，$b_i$减一，$a_i$和$b_i$同时减一,问多少次操作后能使两串序列中的数各自全部相同。

题解：明显只要求出两串序列中的各自的最小值，作为最终变化的目标，对于任意一个$j$，计算出$a_j$,$b_j$与各自目标的差距$d_{1j}$,$d_{2j}$,$\min(d_{1j},d_{2j})+|d_{1j}-d_{2j}|$即$j$对答案的贡献。

=====C Boats Competition=====
题意：給一串数，需要两两分组，目标是分出的每组的和必须全部相同，问最多能分多少组？

题解：排序之后，枚举分组之后的值，暴力查找符合的对数即可。

=====D Binary String To Subsequences=====
题意：难以描述，直接看题：[[https://codeforces.com/contest/1399/problem/D]]

题解：开出两个队列，一个存目前1结尾的队的编号，另一个存目前0结尾的队的编号，每次为根据当今遍历到的数，找队列是否为空，为空，则答案加1，将新编号插入另一个队列，处理完后答案可得。

=====E Weights Division (easy version)=====
题意：还是难以描述，直接看题：[[https://codeforces.com/contest/1399/problem/E1]]

题解：首先它是边权，可以将边权转化为点权，首先dfs算出目前的值，然后发现没对一个点进行操作后，对整体答案做出的贡献是可以量化的，具体表现为，节点i的子节点中有$sz_i$个叶节点，目前权值为$d_i$，则一次操作队整体的贡献为$sz_i*(d_i-\lfloor\frac{d_i}{2}\rfloor)$,这样先预处理出每个点的贡献权值，之后用一个优先队列维护即可。

=====F Weights Division (hard version)=====
题意：上一题的条件下，增加一个对每个节点经行操作的代价，规定代价只能为$1$或者$0$，问达到上述目的的最小代价。

题解：按照上一题得方法，将耗费为$1$和耗费为$2$时操作$i$次的最优情况分别全部计算出来，然后枚举二分计算答案即可。

=====G Yet Another Segments Subset======
题意：给出一些区间，问总最多能有多少个区间满足互不相交或者相互嵌套？

题意：首先离散化，按照区间大小从小到大排序，从小的开始到大的开始线性$dp$，开一个数组记录每个区间最多能够嵌套多少个小区间。预先设定一个包含了所有范围的大区间，然后大区间的答案即为最终答案。
CVBB ACM Team

用户工具

站点工具

页面工具
