CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020/07/12 -- 2020/07/18 周报 ======

===== 本周推荐 =====

==== airbust ====

AIsing Programming Contest 2020 E Camel Train

分类：贪心，数据结构

题意：有$n$只骆驼。对于第$i$只骆驼，给出三个正整数$K_i,L_i,R_i$，表示如果把这只骆驼放在前$K_i$的位置，就会有收益$L_i$，否则会有收益$R_i$。问最大收益。

思路：

这题比赛时没有做出来，后来发现用优先队列可以解决。每个骆驼有两个快乐值，用pair保存，然后用两个vector $L$和$R$存放各个骆驼，分三种情况：

1.$l>r$，此时要把骆驼放在前$k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在前$k$个位置，所以总答案先加上$r$，在$L$里存入$\{k,l-r\}$

2.$l<r$，此时要把骆驼放在后$n-k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在后$n-k$个位置，所以总答案先加上$l$，在$R$里存入$\{n-k,r-l\}$

3.$l=r$，随便放

下面考虑$L,R$内快乐值的计算：

我们将vector按位置先后排序，然后创建一个从小到大的优先队列，每取一个元素就向队列中存一个快乐值，答案也加上该快乐值。此时队内元素的个数也代表排好的队形，如果元素个数大于当前元素的位置，就相当于已经排满了，就必须减去队首的快乐值，直到可以插入元素为止，最后返回答案即可。



==== kazamori ====

CF 1382D Unmerge

  * 分类：dp 背包
  * 简要题意： 询问是否可以将原序列分成两个长度相等的序列（相对顺序不变），使得按照归并排序里的merge操作过后，还是原序列。 
  * 解法：  依次寻找当先序列中的最大数，记录其到结尾的长度，并截断。最后转换成背包问题，判断是否存在一些长度的和恰好为n。
==== Ket98 ====
   
Boundary

分类：计算几何

题目大意：考虑所有经过原点的圆，在所给$n$个点中，找出在同一个圆上最多的点的数量。

思路：一开始因为测试用例，我错以为是以所给的点中选择一个点作为圆心，之后就一直错。其实圆心不局限在所给点中，只要圆经过所给点即可。利用圆周角的思路。先枚举所有的点$A$，然后在每一次枚举中在枚举一遍所有的点$B$，计算圆周角$ABO$的cos值，寻找出众数的数量。在每一次枚举的众数的数量，寻找最大的那一个即可。

在寻找众数的时候，我是利用了sort()来找。同时本题在计算圆周角的时候，需要注意$B$点可能会在$AO$的任意一边，所以要用叉积判断一下，然后利用内接四边形对角互补来处理一下，即把cos值取负。最后，还需要注意共线点的处理，例如(0,1)，(0,2)的答案应该为1。
===== 个人 =====


==== airbust ====

=== 比赛 ===

  * [[https://atcoder.jp/contests/aising2020|AIsing Programming Contest 2020]]

==== kazamori ====

=== 比赛 ===

 * [[https://codeforces.com/contest/1382|CF 658]]
==== Ket98 ====

=== 比赛 ===

  * [[https://atcoder.jp/contests/aising2020|AIsing Programming Contest 2020]]
CVBB ACM Team

用户工具

站点工具

页面工具
