WuliWuliiii

题解

/ 注册

全部文章 / 题解（共12篇）

桥【2021牛客寒假算法基础集训营5 J】【点分治】

题目链接显然，一棵树有条割边（也指桥），于是如果要使最后只有至条桥，那么当时候，实际上我们要将长度为的链给“取消割边”，而取消割边的方法就是通过连边。一条长度为的边，会产生的贡献。所以，我们假设现在找到的一个点举例目前的根节点距离为，要找一个根节点的另一个方向的距离为，那么此时产生的贡献是。...

点分治

2021-03-09

1 506

[HAOI2006]旅行COMF【并查集】

因为边的数目很少，只有5000，那么我们不妨对边的权值排序，然后5000*5000的进行枚举即可，判断连通性就可以了。 #include <iostream> #include <cstdio> #include <cmath> #include <stri...

并查集

2021-01-17

0 653

最长树链【米勒罗宾+树的直径的简单树形DP】

很容易想到正确的解法，首先，我们可以知道（2 * 3 * 5 * 7 * 11 * 13 * ……）最多19个质数相乘就会达到1e9级别的。于是，我们可以考虑质数，我们可以知道一个数最多就是分成20个质数，所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢？于是就有了米勒罗宾检验素数。...

数论 DP

2021-01-16

1 878

Hacker, pack your bags!

题意：有N条线段，每天线段有左右端点l、r，并且线段的长度是r-l+1，且线段有价值c，现在我们想要找两条线段，使得两条线段的长度和为X，并且两线段不相交。如果没有这样的答案输出-1，否则输出最小价值。那么，很简单的，我们可以对l进行生序排序，于是直接查r在“l”之前的线段，我们用map去记录一下对...

stl

2020-12-23

1 919

The XOR-longest Path【字典树】

经典的字典树问题，我们知道查询任意两点的路径异或值为所以，我们求出从根节点到每个节点的异或值，然后将这些值放到字典树上去进行查询就可以求得每个点的与其余点的最大路径异或权值了。 #include <iostream> #include <cstdio> #include &l...

字典树

2020-09-16

1 792

储物点的距离【前缀和】

我采取了分别考虑的方式来解该问题，也就是将x和l、r的位置进行考虑了进去。于是，我定义了如下几个数组，分别表示： pre[x]包括x的前面的所有的货物都运送到x所需的花费suff[x]包括x的后面的所有的货都运送到x所需的花费ans[x]所有点的货物都运送到x所需的花费dis[x]表示x点到1...

前缀和

2020-05-14

1 1035

maze【BFS】

链接：https://ac.nowcoder.com/acm/problem/15665?&headNav=acm来源：牛客网题目描述小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'...

bfs

2020-05-14

0 779

子序列【DP】

链接：https://ac.nowcoder.com/acm/problem/17065来源：牛客网有N个权值，a[1]……a[N]，现在要求一个子序列，满足对于所有的i<j，有。求解这样的子序列的个数。那么，我假设dp[i]表示以第i位为结尾的符合要求的子序列的个数，那么 ...

DP

2020-04-24

1 918

相似的子串【后缀数组+二分答案】

求K个不相交字符子串的最大相同前缀长度x。很容易往后缀数组上靠，但是这还不够，因为很容易就想偏了，这里，我们想处理一个是不重叠，一个是最大的前缀相同，于是，不妨设最长前缀为x，然后二分这个x，这是因为height的关系具有连续性，所以这样就能很清晰的划分出来我们需要进行处理的sa的区间了。 ...

后缀数组二分答案

2020-04-11

3 1783

Rinne Loves Edges

树形DP首先，中文题，就不再阐述题意了。然后，具体怎么dp呢？首先不考虑树上，如果是一条序列上的话，肯定就是这条序列上的最小值了，现在其实实则变成了多条序列。我们动态规划的主要思想就是在于，是割下面的点的代价要小，还是割目前的边要更好些，所以用dp[u]记录，u结点为子树的根结点的时候，断开它到它的...

DP

2020-04-01

1 1293