2020-2021:teams:the_great_wave_off_kanagawa:week_summary_6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_6 [2020/07/17 16:25] kazamori |
2020-2021:teams:the_great_wave_off_kanagawa:week_summary_6 [2020/07/24 14:38] (当前版本) kazamori [kazamori] |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| AIsing Programming Contest 2020 E Camel Train | 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$存放各个骆驼，分三种情况： | 这题比赛时没有做出来，后来发现用优先队列可以解决。每个骆驼有两个快乐值，用pair保存，然后用两个vector $L$和$R$存放各个骆驼，分三种情况： | ||
| 行 11: | 行 17: | ||
| 1.$l>r$，此时要把骆驼放在前$k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在前$k$个位置，所以总答案先加上$r$，在$L$里存入$\{k,l-r\}$ | 1.$l>r$，此时要把骆驼放在前$k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在前$k$个位置，所以总答案先加上$r$，在$L$里存入$\{k,l-r\}$ | ||
| - | 2.$l<r$，此时要把骆驼放在后$n-k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在后$n-k$个位置，所以总答案先加上$l$，在$L$里存入$\{n-k,r-l\}$ | + | 2.$l<r$，此时要把骆驼放在后$n-k$个位置才能获得最大快乐值，但不能确定最终队伍里这个骆驼是否在后$n-k$个位置，所以总答案先加上$l$，在$R$里存入$\{n-k,r-l\}$ |
| 3.$l=r$，随便放 | 3.$l=r$，随便放 | ||
| 行 23: | 行 29: | ||
| ==== kazamori ==== | ==== kazamori ==== | ||
| - | CF 1374E2 Reading Books | + | CF 1382D Unmerge |
| - | * 分类：贪心 | + | * 分类：dp 背包 |
| - | * 简要题意： 有两个人以及n本书，每本书有3个属性：t：表示读完这本书要的时间，a：第一个人是否喜欢这本书，b：第二个人是否喜欢这本书。让你构造一种方案使得他们读的书正好是m本，并且这些书中第一个人喜欢的书有>=k本，第二个人喜欢的书有>=k本，并且读书总时间最少。 | + | * 简要题意： 询问是否可以将原序列分成两个长度相等的序列（相对顺序不变），使得按照归并排序里的merge操作过后，还是原序列。 |
| - | * 解法： 先将每本书按a,b属性分类(00,01,10,11)按时间从小到大放入各自的优先队列，然后贪心选择数量最少且时间和尽量小的x本书，满足a，b属性此时的和均>=k(先尽量选择属性为11的书，若不够则从队首选择属性为01，10的两本书)。若此时x>m，则不存在满足条件的方案。否则记录此时未选中的所有的书，并放入优先队列。若此时选中的属性为11的书中时间最大的加上未选中的书中时间最小的时间和小于未选中的属性为10的书中时间最小以及未选中的属性为01的书中时间最小的时间和，则进行替换并x++，并更新未选中的书的优先队列。否则选择未选中的书中的队首，并x++。当x==m时，输出方案。 | + | * 解法： 依次寻找当先序列中的最大数，记录其到结尾的长度，并截断。最后转换成背包问题，判断是否存在一些长度的和恰好为n。 |
| ==== Ket98 ==== | ==== Ket98 ==== | ||
| - | ABC E - Colorful Blocks | + | Boundary |
| - | * 分类：统计/组合数 | + | 分类：计算几何 |
| - | * 题目大意：现有$M$种颜色，$N$个块。问有多少种上色方式，使得两两之间相邻且颜色相同的块不超过$K$组，对$998244353$取模。 | + | |
| - | * 思路：两两之间相邻且颜色相同的块为$i$组时，可以在$N-1$个空隙中插入$N-1-i$个隔板，这样分出来的$N-i$个组，只有第一组颜色有$M$种选择，后边的组都只有$M-1$中选择。将$0\le i \le K$之间的情况求和即可。 | + | |
| + | 题目大意：考虑所有经过原点的圆，在所给$n$个点中，找出在同一个圆上最多的点的数量。 | ||
| + | |||
| + | 思路：一开始因为测试用例，我错以为是以所给的点中选择一个点作为圆心，之后就一直错。其实圆心不局限在所给点中，只要圆经过所给点即可。利用圆周角的思路。先枚举所有的点$A$，然后在每一次枚举中在枚举一遍所有的点$B$，计算圆周角$ABO$的cos值，寻找出众数的数量。在每一次枚举的众数的数量，寻找最大的那一个即可。 | ||
| + | |||
| + | 在寻找众数的时候，我是利用了sort()来找。同时本题在计算圆周角的时候，需要注意$B$点可能会在$AO$的任意一边，所以要用叉积判断一下，然后利用内接四边形对角互补来处理一下，即把cos值取负。最后，还需要注意共线点的处理，例如(0,1)，(0,2)的答案应该为1。 | ||
| ===== 个人 ===== | ===== 个人 ===== | ||
| 行 49: | 行 58: | ||
| === 比赛 === | === 比赛 === | ||
| - | * 无 | + | * [[https://codeforces.com/contest/1382|CF 658]] |
| ==== Ket98 ==== | ==== Ket98 ==== | ||
| === 比赛 === | === 比赛 === | ||
| - | * [[https://atcoder.jp/contests/abc167|AtCoder Beginner Contest 167]] | + | * [[https://atcoder.jp/contests/aising2020|AIsing Programming Contest 2020]] |
| - | * [[https://codeforces.ml/contests/1353|Codeforces Round #642 (Div. 3)]] | + | |
2020-2021/teams/the_great_wave_off_kanagawa/week_summary_6.1594974339.txt.gz · 最后更改: 2020/07/17 16:25 由 kazamori
