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