2020-2021:teams:alchemist:sppc_16

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:alchemist:sppc_16 [2020/05/10 22:17]
mountvoom [B.Balloon Warehouse]
+++ 2020-2021:teams:alchemist:sppc_16 [2020/05/10 22:35] (当前版本)
mountvoom [G.Graphics Design]
@@ 行 45: / 行 45: @@
 因为每次递归一定能找到一个最终序列中的气球，所以复杂度为$O(r)$，如果最终长度不够$r$，直接不断复制即可。
+by MountVoom
 ===== C.Crazy Rotations =====
 ===== D.Dendroctonus =====
@@ 行 53: / 行 55: @@
 三点外接代码见个人页面。
 ===== E.Election Frenzy =====
+**题意:**
+需要给一张无向图黑白染色，使得每个点和他相连的点中既要有黑点也要有白点。
+但是边可能会很多，有些点给出的是和它不相邻的点。
+**题解:**
+如果某一个联通块只有一个点那么无解，否则遍历每个联通块直接染色即可。
+至于边很多的处理，zzh鸽鸽曾经指导过。
+开一个并查集，如果$i$被遍历过，把它和$i + 1$合并在一起，每个并查集内的最大值表示这个并查集中唯一的一个还没有没遍历到的点。
+对于边少的点直接遍历，边多的点也是暴力枚举，不过是按照并查集来枚举，枚举后被合并后会使得并查集个数越来越少，最终复杂度仍然是线性的。
+by MountVoom
 ===== F.False Intelligence =====
@@ 行 77: / 行 97: @@
 by Hardict
 ===== G.Graphics Design =====
+**题意:**
+这个题题意看了很久qwq。
+每个学生有一个大项目，每个项目分为许多小项目，每个小项目都有一个优先级，优先级两两不同。
+每个学生的小项目必须按顺序完成，每个项目对三种物品都有某种需求，但是每种物品最多只需要一个。
+在某一时刻，如果当前的物品满足了某些项目的需求，那么选择优先级最高的项目执行，此时会借走物品。
+每个小项目有一个执行时间$t$，如果它在第$x$时间开始执行，那么会在$x + t$时间结束并把物品归还。
+求所有同学结束自己的项目的时间。
+**题解:**
+因为优先级两两不同，最终的顺序一定是确定的，直接模拟即可。
+在这里我用一个优先队列维护执行的事项，按完成时间由小到大排序。
+用8个优先队列维护待办项目，每个优先队列对应一种需求的项目，比如1维护只需要1号物品的项目，按照优先级由大到小排序。
+如果只用1个优先队列维护项目可能会出现很多项目需求不能被满足但是优先级很高，导致反复插入删除引起超时。
+by MountVoom
 ===== H.Hilbert's Hash Browns =====
 ===== I.Intuidiff II =====

2020-2021/teams/alchemist/sppc_16.1589120230.txt.gz · 最后更改: 2020/05/10 22:17 由 mountvoom