Phecda_

未归档

/ 注册

全部文章 / 未归档（共4篇）

CodeForces1204C

CodeForces1204C 其实我觉得这是一道比较综合的题吧... 这个题可供挖掘的性质很多,比如最短路最长是\(n\)啊,答案序列中的两点之间的距离肯定是\(p\)数组上这两个点的距离啊等等. 其实是在\(p\)数组上进行了一次另类的最短子序列.图的条件其实就是限制了转移,然后再有一个有点意...

最短路 DP CodeForces

2019-08-23

0 418

[NOI2018]归程

[NOI2018]归程这题我只会离线做法..在线做法的克鲁斯卡尔重构树我虽然会但是...我不会倍增...所以就比较困难,于是暂时先只写了离线做法. 这个题其实是一个动态的图上的最短路问题. 从\(1\)号点开始跑一遍 Dijkstra,求出到每个节点的最短路然后问题就转化成了在开车能到达的点里选...

Kruskal重构树并查集最短路单调性倍增

2019-08-23

0 538

ZROI#961

ZROI#961 很诡异地一道题,你看他问的是是否存在距离\(d\in [dist,1.1dist]\)的路径. 你想一下这个\(1.1\)是个啥.好像不知道,先考虑暴力叭. 暴力你就\(bfs\),让点重复入队就好了,每个点维护一个\(set\),查询直接\(lower\_bound\)即可. ...

nature bfs 最短路归并排序二分查找

2019-09-17

0 434

ZROI#1005

ZROI#1005 非常令人迷惑的一个题... 首先,我们发现,那个$M$并没有什么卵用. 于是我们直接不鸟它. 然后我们发现我们需要找一个最小的糖浆的集合$S$. 使得下式成立: \(\sum_{i\in S}{k_i*v_i}=N\) 其中$k_i$表示第$i$种糖浆选了几份,$v_i$表示糖...

DP 最短路背包

2019-09-23

0 383