2020-2021:teams:the_great_wave_off_kanagawa:week_summary_7
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_7 [2020/07/24 15:38] airbust |
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_7 [2020/07/24 17:38] (当前版本) lkw981105 [Ket98] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ==== airbust ==== | ==== airbust ==== | ||
| - | AIsing Programming Contest 2020 E Camel Train | + | CF 1381A1 Prefix Flip (Easy Version) |
| - | + | ||
| - | 分类：贪心，数据结构 | + | |
| - | + | ||
| - | 题意：有$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按位置先后排序，然后创建一个从小到大的优先队列，每取一个元素就向队列中存一个快乐值，答案也加上该快乐值。此时队内元素的个数也代表排好的队形，如果元素个数大于当前元素的位置，就相当于已经排满了，就必须减去队首的快乐值，直到可以插入元素为止，最后返回答案即可。 | + | |
| + | * 分类：思维 | ||
| + | * 题意：给定一个01字符串，每次可以选择一个$x$，然后操作。操作方法为把该字符串的$x$前缀全部反转（0变成1, 1变成0），然后翻转（首尾交换）。目标是使该字符串变成另外一个01字符串。要求给出翻转方案。字符串的长度为$n（n \leq 1000）$，操作次数不超过$3n$。 | ||
| + | * 思路：很明显是要从后往前满足。考虑第$i$个位置，如果已经一样了就可以不用管，如果不一样那么它将会由第一个位置得到。所以如果第一个位置和当前一样，首先要操作前缀1使得第一个和点前$i$的不一样，然后再操作前缀$i$就可以满足$i$了。 | ||
| ==== kazamori ==== | ==== kazamori ==== | ||
| 行 36: | 行 20: | ||
| ==== Ket98 ==== | ==== Ket98 ==== | ||
| - | Boundary | + | Clam and Fish |
| - | 分类：计算几何 | + | 分类：思维 |
| - | 题目大意：考虑所有经过原点的圆，在所给$n$个点中，找出在同一个圆上最多的点的数量。 | + | 题目大意：有$n$个笼子，里面可能有（1）空（2）蛤蜊*1（3）鱼*1（4）鱼*1和蛤蜊*1。有四种操作：（1）把蛤蜊做成饲料供后边的笼子来使用（2）用饲料捕捉鱼（3）如果笼子有鱼，可直接捕捉鱼（4）什么都不做。问最多可以捕捉多少鱼？ |
| - | 思路：一开始因为测试用例，我错以为是以所给的点中选择一个点作为圆心，之后就一直错。其实圆心不局限在所给点中，只要圆经过所给点即可。利用圆周角的思路。先枚举所有的点$A$，然后在每一次枚举中在枚举一遍所有的点$B$，计算圆周角$ABO$的cos值，寻找出众数的数量。在每一次枚举的众数的数量，寻找最大的那一个即可。 | + | 思路：题目可能比较长，但其实矛盾点就是在蛤蜊*1的笼子应该是拿去作饲料还是拿去捕捉鱼。这里有两种解法。 |
| - | 在寻找众数的时候，我是利用了sort()来找。同时本题在计算圆周角的时候，需要注意$B$点可能会在$AO$的任意一边，所以要用叉积判断一下，然后利用内接四边形对角互补来处理一下，即把cos值取负。最后，还需要注意共线点的处理，例如(0,1)，(0,2)的答案应该为1。 | + | 比赛的时候我使用倒序读取，need记录目前所需的饲料。碰到空笼子则need++，碰到有蛤蜊的笼子分两种情况（1）need==0时用于捕捉鱼（2）need!=0时用于做饲料。有鱼的笼子全部捉鱼即可。 |
| + | |||
| + | 第二种是顺序读取，贪心把所有的蛤蜊做成饲料，最后把剩下的饲料/2，一半用于做饲料，一半用于捉鱼。 | ||
| ===== 个人 ===== | ===== 个人 ===== | ||
| 行 52: | 行 38: | ||
| === 比赛 === | === 比赛 === | ||
| - | * [[https://atcoder.jp/contests/aising2020|AIsing Programming Contest 2020]] | + | 无 |
| ==== kazamori ==== | ==== kazamori ==== | ||
| 行 63: | 行 49: | ||
| === 比赛 === | === 比赛 === | ||
| - | * [[https://atcoder.jp/contests/aising2020|AIsing Programming Contest 2020]] | + | 无 |
2020-2021/teams/the_great_wave_off_kanagawa/week_summary_7.1595576306.txt.gz · 最后更改: 2020/07/24 15:38 由 airbust
