原题链接题目描述在一个平面上有n个点,并且这n个点在某一时刻都在同一条直线y=ax+b上,要我们求最终所有点的相遇次数(a和b相遇,b和a相遇,不属于同一情况,相遇次数都要加一)。题目上还说时间的范围是(负无穷到正无穷)既时间可以随意倒流。思路分析如果说...
阅读全文...
AcWing 1238. 日志统计【枚举时间】
原题链接双指针 + 枚举时间 + 离散化去重本来看题面觉得这题复杂,结果一遍敲完没有调试直接就ac了(运气爆棚)。我来说说我的思路吧,其实这道题双指针循环的顺序特别像这道题 799. 最长连续不重复子序列我们首先开一个二维数组point存一下每个时刻会出...
阅读全文...
阅读全文...
AcWing 903. 昂贵的聘礼【样例建图图示】
原题链接前置知识Dijkstra链式前向星虚拟源点分析本题的难点在于如何建图将原问题抽象成一个最短路问题以及如何处理等级限制。以下为样例建图示意 最后只需要枚举允许的等级区间,在每一个区间以超级源点为起点跑一遍Dijkstra取所有答案的min,便是最终...
阅读全文...
阅读全文...
AcWing 848. 有向图的拓扑序列【个人笔记】
原题链接什么是top序列?简单来说一个有向无环图的top序列指的是,对于图中每个节点,存在一个序列使得前面的点总是可以指向后面的点,而后面的点不能指向前面的点,这个序列就称为top序列例子该有向无环图的Top序列为:A B C DPS:只有有向无环图才存...
阅读全文...
阅读全文...
AcWing 891. Nim游戏【附完整证明】
原题链接Nim游戏设n堆石子的个数分别为:$[a_1,a_2,a_3,...,a_n]$,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。问如果两人都采用最优策略,先手是否必胜。结论...
阅读全文...
阅读全文...