Cities
CF864F Cities Excursions
题意:给定一张有向图,询问 \(s, t\) 两点间字典序最小路径上的第 \(k\) 个结点。 首先要验证 \(s, t\) 间是否连通,所以建反图,枚举 \(1 \sim n\),跑 dfs。这部分时间复杂度 \(\mathcal O(n^2)\)。 确定了哪些点跟 \(t\) 连通后,\(s\) ......
CF613D Kingdom and its Cities
题意 给定一棵树,每次询问给出 \(k\) 个点。 问最少删除多少个 节点 (不能删这 \(k\) 个点) 使得这 \(k\) 个点两两不连通。 Sol 无解的情况是 \(trivial\) 的。 判断是否有相邻的两个关键点就行了。 但是 \(dp\) 是不太 \(trivial\) 的。 设 \( ......
Ways China’s Cities Can Drive Equitable and Sustainable Urbanization
The five-year plan represents an opportunity not just to advance climate goals, but to create better cities as urbanization continues. Here are five w ......
PAT 甲级【1013 Battle Over Cities】
本题就是dfs.连通图个数-2; 但是java慢,最后一个case 超时 import java.io.*; import java.util.HashSet; import java.util.Set; public class Main { @SuppressWarnings("uncheck" ......
《CF1062F Upgrading Cities》 解题报告
拓扑排序好题。 首先需要一个比较显然但从来没用过的性质,任何时刻,队列中的点都不可能相互之间有你到我,或者我到你的关系。 所以当枚举到一个点,出现队列中除了他还有两个及以上的数,那么这个点就一定不可能被统计到答案中。 考虑没有点的情况,也就是说剩下的点都只能由他拓展出来,所以他可以到达剩下的所有点。 ......
CodeForces 1062F Upgrading Cities
洛谷传送门 CF 传送门 考虑一个子问题:求从某个点 \(u\) 能到达的点数。 如果要精确地计算出来,最优解法只能是 \(O(\frac{n^2}{w})\) 的 bitset。但是我们还没有利用到题目的性质,我们只需要判断一个点是否至多有一个点互不可达。 考虑拓扑排序的过程,队列里面的点两两互不 ......
CF1101F Trucks and Cities
### 题目大意 有 $n$ 个城市坐落在一条数轴上,第 $i$ 个城市位于位置 $a_i$。 城市之间有 $m$ 辆卡车穿行。每辆卡车有四个参数:$s_i$ 为起点编号,$f_i$ 为终点编号,$c_i$ 表示每行驶 $1$ 个单位长度需要消耗的油量,$r_i$ 表示可以在路途中加油的次数。 当卡 ......
ICPC2020昆明 Cities
原题链接 题目简述 $\qquad$给定一串数字,对于一串连续的数字,可以将它们染色成任意数字,问最少要多少次才能把这串数字全部染成同种颜色。 思路解析 $\qquad$我们可以对题目进行一下转化:所有数字全部染成同种颜色意味着相邻异色数对的数量为 $0$,那我们每次对整段的区间染色,只有以下两种情 ......