Luogu 1288 – 博弈论
PROBLEM https://www.luogu.org/problemnew/show/P1288 ANALYSIS 因为一定有一个零权边,所以可以将环拉成链。 不考虑零权边,当链长度为 1 时,先手必胜;相应,为 2 时先手必败。 易证,若设起始点往左和往右走到零权边的距离为分别为x, y,则若x,y中有一个奇数,先手必胜。 这题的数据是真t…
Luogu P1199 – 贪心/博弈论
PROBLEM https://www.luogu.org/problemnew/show/P1199 ANALYSIS 题意就不描述了。 此题中,人是必胜的,只需要做到 每次取所有行中第二大元素最大的那个行。 证明: 计算机和人都永远都拿不到第一大的元素。 计算机永远都拿不到第二大的元素,但是人可以。 SOLUTION [crayon-600c1…
Luogu P1983 – 拓扑排序
PROBLEM https://www.luogu.org/problemnew/show/P1983 ANALYSIS STL真的降智 做题之前被周围的人乱说一通更降智 题目大意: 构建低优先级车站指向高优先级车站的单向边,找关键路径。 跑一边拓扑排序就可以了。 使用set的时间约为不使用set时间的13-14倍,空间为5.5倍。也可能是我用的方…
scanf & printf 补充
scanf & printf 常用操作的补充。cin和cout过于繁琐,一般不考虑。暂时想到这些,以后想到了其他的再加进去。
Luogu P1339 – 单源最短路
PROBLEM https://www.luogu.org/problemnew/show/P1339 ANALYSIS 裸题 ,保存模板 时间复杂度: SPFA O(k*E)  , k 为每个节点进入队列的次数,一般小于等于2,最坏情况为O(V*E) Dijkstra(Heap) O(2*E+V*lgV) Dijkstra(Ordinary) O…
Luogu P2921 – 图的遍历
PROBLEM https://www.luogu.org/problemnew/show/P2921 ANALYSIS 寻找从每个点出发到访问到已访问节点(将环封闭)用的时间。 起初自己的想到解法应该和 [lip id=893] 差不多,然而在原先题目的思路去思考这个问题有点受限。   一种正确的做法: 从所有点开始,尝试对节点染色。 …