2020-2021:teams:tle233:swerc2019

差别

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

到此差别页面的链接

--- 2020-2021:teams:tle233:swerc2019 [2020/05/21 16:33]
marvolo 创建
+++ 2020-2021:teams:tle233:swerc2019 [2020/05/21 16:37] (当前版本)
marvolo
@@ 行 6: / 行 6: @@
 Pro: 5/7/12
+===== [A] Environment-Friendly Travel =====
+==== 题意 ====
+给出一个图,求起点到终点的所有路径中,不超过距离$b$的花费最小的路径是多少.每条路的花费和路径长度并不相同.
+==== 题解 ====
+考虑对Dijkstra进行一下改进,用$dis[i][j]$表示从起点到点$i$的长度恰好为$j$的路径中,最少的花费是多少.然后堆里的元素同时维护点的编号,花费,以及起点到该点的路径长度.用改进后的Dijkstra跑一遍就行了.
+===== [B] Biodiversity =====
+==== 题意&题解 ====
+签到题
+===== [C] Ants =====
+==== 题意&题解 ====
+签到题
+===== [F] Icebergs =====
+==== 题意&题解 ====
+签到题
+===== [G] Swapping Places =====
+==== 题意 ====
+有$s$种动物,每一个动物有一个名字,同时这些动物之间有$l$对朋友关系(没有传递性).然后给出一个长度为$n$的动物序列,要求通过任意次数的交换相邻两个动物位置的操作,使得这个序列的字典序最小.交换的条件是被交换的两个动物必须有朋友关系.求最后的交换结果是什么.
+==== 题解 ====
+首先将每种动物的位置单独存起来,维护一个类似于链表的东西.同时预处理一下每一种动物的表头(也就是排在最前面的那个动物),它的前面有几个动物和它有朋友关系,这个值记为$s[i]$.之后开始枚举最终结果的每一位,按照字典序从小到大枚举动物.假如说一种动物的表头和在它之前的所有动物都有朋友关系,说明它可以通过交换操作换到最前面.记录答案,然后去维护剩下动物的表头的信息.
+假如说该动物的位置是$i$,其他动物的表头的位置是$j$.如果$i<j$,那么$++s[j]$.如果$i>j$,就把原序列第$i$个位置的动物替换为和所有动物都有朋友关系的一个特殊的动物.同时,一个链表的表头发生了变化,再根据原序列暴力维护.这样整个序列至多被扫描$s$次.总的时间复杂度为$O(ns)$
+===== [I] Rats =====
+==== 题意&题解 ====
+签到题
+===== [K] Birdwatching =====
+==== 题意 ====
+给出一个有向图和一个点$t$.求$t$直接相连的点中有多少个满足以下条件:把$t$到该点的边去掉,则$t$无法再到达这个点.
+==== 题解 ====
+删掉所有和$t$相连的边,然后其他所有边反向.每一个点开一个set用来记录能被哪些和$t$直接相连的点访问过.然后依次从和$t$相邻的点开始DFS.假如说$a$能够从$b$经过一些点访问到,那么在原图中,一定有一条从$t$到$a$,再从$a$到$b$的路径,所以$b$就不符合题意.在DFS完成后据此就可以得到答案.
+===== 总结 =====
+这场中第一次碰到了无榜可跟的情况,导致中间产生了一段空档期.中期多线开题感觉精力有些分散.除了硬开了一道G题之外(居然还拿了一血),后面都只写了一些残篇,尤其在打表找规律上浪费了过多的时间.然后喂题的时候一定要再确认下核心题意,最近两场比赛都栽在这上面了.
+最后吐槽一下政治正确害人不浅,欧洲赛区的题目居然非要套上一个环保的题目背景,有的还套的很生硬,导致题面又臭又长.下次不拿欧洲的题来练了.

2020-2021/teams/tle233/swerc2019.1590050032.txt.gz · 最后更改: 2020/05/21 16:33 由 marvolo