ProApe

OJ题

数据结构(7) 算法(4)

/ 注册

全部文章 / OJ题（共25篇）

HDU Wave

我们发现这道题的C很小，所以得从这方面下手，把这些数依据奇偶性划分成两个集合，并且把每一个数在序列中出现的位置记录下来，我们暴力尝试每一个奇数和偶数构成的Wave，最后取一个最大值就行了，每一次尝试过程是这样的的比如：N<mark>8 C</mark>2 2 1 1 2 2 ...

2020-01-02

0 500

HDU Traffic

题意是这样的：在一个十字路口，有N辆车是东西通行的，有M辆车是南北通行的，并且给你每辆车通过的十字路口的时刻表，当东西通行的车和南北同行的车同时通过十字路口的话就会发生碰撞，现在要求东西通行的时刻表不变，南北通行的车辆要集体最少等待多少时间才能不发生碰撞一开始题读错了，忽略了集体等待，好吧，其实是我...

2020-01-02

0 451

Minimum Spanning Tree

题意：有一棵边带有权值的树，定义线图：将这颗树的每一条边缩成一个点，这个点的点权为原先的边权，当原先树中两条边有公用的节点时，则线图中缩成的两个点有边相连，且边的权值为这两个点的点权之和。求形成的线图的最小生成树。解题思路：你会发现在原先的树中，父节点和他紧邻的所有子节点形成的线图是一个完全图，...

2020-01-02

0 524

Line-line Intersection

题意：给了N条线（注意这些线有可能重合），问两条直线有交点的对数，1 3和3 1 属于同一对，两条直线重合也算有交点解题思路：这道题有些细节是很恶心的因为怕卡精度，所以直接用了pair存，用map套一个pair存储斜率，但是只存储斜率是不行的，因为直线有重合的情况，所以还得用map套两个pai...

2020-01-02

0 552

洛谷P2921

刚看到这道题的时候，没有在意复杂度，就直接暴力了，我也真是憨了，这可是提高省选组的题……后来看看算法标签说是记忆化搜索，再仔细看看题，这不就是每个顶点出度只有一的有向图嘛，包括自环，且是多个连通块，然后，每一个顶点停止遍历的时候一定是进入了一个环内或者自身是某个环的一部分，否则遍历是不会停止的，那么...

2020-01-02

0 590