Home

Keep It Simple

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Problem Description HazelFan wants to build a rooted tree. The tree has $ n$ nodes labeled $ 0$ to $ n−1$, and the father of th...

发布 0 条评论

最近学了LCA的相关问题在此总结下 在有根树中,两个节点u和v的公共祖先中距离最近的那个成为其最近公共祖先,在树上两点因为存在唯一的最短路,故其LCA为最短路上深度最小的点。通过求解LCA我们可以处理如求解树或DAG上任意两点的最短...

发布 0 条评论

人生第一场多校全程挂机QYQ太菜了 Multi-University Training Team 1-1012虚建笛卡尔树 Time Limit: 4000/2000 MS (Java/Others) As to a permutation $p_1,p_2,⋯,p_n$ from $1$ to $n$, it is uncomplicated for each $1≤i≤n$ to ca...

发布 0 条评论

完全二叉树上的朴素LCA求解 codeforces #362(Div.2)C.Lorenzo Von Matterhorn Barney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a bidirectional r...

发布 0 条评论

今天做题遇到了这个经典问题,拜读了《最小割模型在信息学竞赛中的应用》也顺便回顾下网络流的相关知识。全文当作是对论文的回顾,同时感谢作者的辛勤付出。 Introduction 最大权闭合图指的是一个有向图$G=(V,E)$的点集$V$,且该点集满...

发布 0 条评论

Time Limit: 2000/1000 MS (Java/Others) Problem Description Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between ...

发布 0 条评论

是时候学习笛卡尔树了 启示于2017 Multi—Contes Team 1 1012 笛卡尔树一种特定的二叉搜索树(Binary Search Tree) 适用于一般数列的RMQ, RtopkQ(区间第k大/小查询) 每个节点存有[key,value],从key来看的话每个节点的key大于其左...

发布 0 条评论

求$\displaystyle \sum_{i=1}^{n}\sum_{j=1 \land i \not = j}^{m}(n\ mod\ i)(m\ mod\ j) $ Input 第一行两个数 $n,m$。 Output 一个整数表示答案 mod 19940417的值 Sample Input ...

发布 0 条评论

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) 我们称一个有向图$G$是传递的,当且仅当对任意三个不同的顶点$a$,若$G$中有 一条边从$a$到$b$且有一条边从$b$到$c$ ,则$G$中同样有一条边从$a...

发布 0 条评论

筛法真是数论中的好东西,可以预处理方便大规模查询,比如今天做的第K大公因子 Problem Description 友谊度$friend(a,b)$是这么计算的:令$a, b$ 两个整数分别是两个同学的属性,两个同学的友谊度取决于 $a,b$ 第$k$ 大的公约数。如果...

发布 0 条评论