差别

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

--- 2020-2021:teams:alchemist:sppc_16 [2020/05/10 22:06]
mountvoom [A.Anticlockwise Motion]
+++ 2020-2021:teams:alchemist:sppc_16 [2020/05/10 22:35] (当前版本)
mountvoom [G.Graphics Design]
@@ 行 23: / 行 23: @@
 有一个很大的螺旋矩阵，给出两个数值，求他们在矩阵中的坐标的曼哈顿距离。
-可以先暴力枚举找到
+**题解:**
+可以先暴力枚举找到它在第几圈，然后找它在下边还是右边还是上边还是左边。
+by MountVoom
 ===== B.Balloon Warehouse =====
+**题意:**
+最开始有无限个0号气球，给出$n$个操作，每个操作是在所有$x$号气球后面插入一个$y$号气球，最后询问$[l, r)$这一段的气球编号。
+其中$ l < r \leq 10^6, r - l \leq 10^5$
+**题解:**
+如果当前这个$x$号气球是在第$i$个操作加入的，考虑插入到它后面的气球。
+可以发现是第$i$个操作之后的在$x$后插入的气球的倒序排列。
+也就是说我们可以很容易的找到最终序列中，当前气球下一个位置的气球是什么，只需要倒序枚举插入在它后面的气球即可，用递归容易实现。
+因为每次递归一定能找到一个最终序列中的气球，所以复杂度为$O(r)$，如果最终长度不够$r$，直接不断复制即可。
+by MountVoom
 ===== C.Crazy Rotations =====
 ===== D.Dendroctonus =====
@@ 行 33: / 行 55: @@
 三点外接代码见个人页面。
 ===== E.Election Frenzy =====
+**题意:**
+需要给一张无向图黑白染色，使得每个点和他相连的点中既要有黑点也要有白点。
+但是边可能会很多，有些点给出的是和它不相邻的点。
+**题解:**
+如果某一个联通块只有一个点那么无解，否则遍历每个联通块直接染色即可。
+至于边很多的处理，zzh鸽鸽曾经指导过。
+开一个并查集，如果$i$被遍历过，把它和$i + 1$合并在一起，每个并查集内的最大值表示这个并查集中唯一的一个还没有没遍历到的点。
+对于边少的点直接遍历，边多的点也是暴力枚举，不过是按照并查集来枚举，枚举后被合并后会使得并查集个数越来越少，最终复杂度仍然是线性的。
+by MountVoom
 ===== F.False Intelligence =====
@@ 行 57: / 行 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 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具