题号 NC14247名称 Xorto来源 Wannafly挑战赛1戳我进入往期每日一题汇总贴~注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题目描述 给定一个长度为 的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为 。 输入描述 第一行一个数 表示数组长度；第二行 个整数表示数组； ,。 输出描述 一行一个整数表示答案。 示例1 输入  30 0 0  输出  5  说明  ([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])    题解 暴力是枚举两个区间左...

比赛名称：JOI 2019-Final比赛真题（重现赛）   赛后补题可以让自己变的更强      活动具体内容    4月12日18:00-4月17日中午12:00，写JOI 2019-Final比赛真题（重现赛） 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月17日下午审核，并给参与活动的同学发放10-100牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少获得其获得的牛币  如果题解...

题号 NC51180名称 Accumulation Degree来源 《算法竞赛进阶指南》0x54如果不会做的话可以先去学习另外一个题：201400 树学写这两道题目中的任意题目，都可以获得牛币，写两篇题解可能获得更多牛币~ 戳我进入往期每日一题汇总贴~  感谢@Alan233 同学推荐题目如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 先看201400树学这个题 本题是要你任选一个点为根使得树上的所有点深度之和最小。 首先考虑如果是指定根节点你会不会做：已知根节点的话，我们只需要一遍dfs（或者bfs）就可以求出每个点的深度，然后求和就可以了。 然后我们考虑如果我们知道...

比赛名称： 牛客练习赛61   出题人：米咔   戳我进入官方题解， 有问题可以回帖询问出题人~    赛后补题可以让自己变的更强      活动具体内容    4月10日22:00-4月17日12:00，写牛客练习赛61 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量      小建议：比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月17日下午审核，并给参与活动的同学发放10-100牛币        PS:     如果题解写...

题号 NC13229名称 二分图染色来源 美团2017年CodeM大赛-初赛A轮 戳我进入往期每日一题汇总贴~  注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 今天这个题看来是偏难了…… 这个题的第一个难点也是它设计得最巧妙的一个点，在于要把找个二分完全图的染色问题向二维棋盘格子上的行列覆盖转化。（如果你学过二分图匹配并做过一些相关的练习，其实你是应该能想到的——二分图匹配相关的问题往往是：棋盘格子上的行列覆盖转化成二分完全图匹配，1*2的小骨牌覆盖转化为棋盘格子黑白染色之后的二分图匹配，这个题只是反过来转换了。） 原题是左右两边各有n个点的完全二分图每条边选一个颜...

题号 NC50940名称 Running Median来源 《算法竞赛进阶指南》0x05戳我进入往期每日一题汇总贴~  注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐~ 点击查看详情 这算是个经（套）典（路）题了，也存在不少高端做法，比如说你想练练平衡树写法什么的都可以，这里讲解一种简单的做法——堆。 我们在之前的每日一题中给大家讲过堆这种数据结构（https://ac.nowcoder.com/discuss/390428 ），这里不再介绍。 我们可以建一个大根堆，一个小根堆，大根堆存目前数列中较小的那一半数字，小根堆存目前数列中较大的一半数字，那么中位数不是在小根堆的堆顶就是在大根堆的堆...

比赛名称：牛客算法周周练1   赛后补题可以让自己变的更强      活动具体内容    4月7日21:30-4月13日中午12:00，写牛客算法周周练1 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月13日下午审核，并给参与活动的同学发放10-80牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少获得其获得的牛币  如果题解有抄袭行为，@王清楚 将会取消其获得牛币的资格   如何开通牛客...

题号 NC13249名称 黑白树来源 美团2017年CodeM大赛-初赛B轮戳我进入往期每日一题汇总贴~注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐~ 点击查看详情 看到树想一边搜一边处理大概率都是可以的（也有例外，比如昨天那个题就根本和这棵树的样子没什么关系。）首先，我们可以很容易的知道：由于每个点都是向上覆盖的，所以凡是不能被下面的点覆盖上的点都必须要选，而能被子孙节点覆盖的点就一定不选了吗？不一定，反例如图1叶子节点6一定得选，这个时候5和4都在他的覆盖范围内，如果都不选，3没被覆盖，要选，2要选1要选，一共选了4个点，但是事实上我们选6和5就行了。 （知道了这个贪心策略不对之后我们...

题号 NC13611名称 树来源 牛客练习赛1戳我进入往期每日一题汇总贴~  这个题表面上看起来像是个树上dp，但是你会发现，当xy同色的时候要求x到y的路径上所有点颜色一样这个事情非常难办——如果我们考虑颜色一个一个的涂，同色这个条件父亲节点有三个子树为例，可能其中两个子树和这个父亲节点是同样的颜色，而另外一个子树是另一个颜色，这就非常难办了。 我们考虑把树上的东西转化到线性结构上——这样的操作当然是使用dfs序啦。 ----------------------以下是介绍dfs序的分割线----------------------- dfs序：每个节点在dfs深度优先遍历中的进出栈的时间序列...

比赛名称：牛客OI周赛15-提高组   出题人：wxyww   戳我进入官方题解~ 有问题可以回帖询问出题人   赛后补题可以让自己变的更强      活动具体内容    4月4日21:30-4月11日中午12:00，写牛客OI周赛15-提高组 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月10日下午审核，并给参与活动的同学发放10-100牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少...

题号 NC13221名称 数码来源 美团2017年CodeM大赛-资格赛戳我进入往期每日一题汇总贴~  一切的解题其实都是从最暴力开始的，本题最暴力的方法：先枚举x，然后枚举x的因子，将它们最高位的情况进行统计。 eg:l=3 r=6:x=3 因子有1 3x=4 因子有1 2 4x=5 因子有1 5x=6 因子有1 2 3 6 为了简化问题，我们可以先求区间[1,r]的答案然后求区间[1,l-1]的答案（这样子不用过于纠结左界的问题，不容易出错）。 观察枚举的过程你可以发现以下几点： 第一，x其实只是一个中间的渠道，我们实际上也并不关心x的值和不同的x对应的因子都有谁，我们要的只有最后的统计结...

比赛名称：牛客OI周赛15-普及组   出题人：Evenifeverything   戳我进入官方题解~ 有问题可以回帖询问出题人   赛后补题可以让自己变的更强       活动具体内容     4月3日21:00-4月10日中午12:00，写牛客OI周赛15-普及组 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量    活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月10日下午审核，并给参与活动的同学发放10-80牛币      PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解...

题号 NC13886名称 Shortest Path来源 西南交通大学第十三届ACM决赛戳我进入往期每日一题汇总贴~  简单说一下汉语题意： 给你一棵 个节点的树（保证 是偶数），你需要将 个节点分为 个点对，使得每个点对的两个点的距离的和最小。 首先我们可以通过观察得到以下几点： 首先，在最短的距离和之中一条边一定不会被覆盖两次，如图，我们一定可以找到一种方法来交换配对，把重复的边去掉（其他的边是不会变的）。也就是说对于一条边来说，其实只有选和不选两种可能。   第二，对于一个点x，它子树中的点一定会尽量在子树中找到匹配的点内部消化掉（要么连父亲要么连兄弟），只有根是有可能会往上找一个点来匹...

题号 NC23053名称 月月查华华的手机来源 牛客小白月赛12戳我进入往期每日一题汇总贴~  暴力的话是但是这样也太暴力了。 这就是个简单的枚举优化，不要认为有多么的复杂高深（学算法最忌讳自己吓唬自己，你怕了就已经输了）。 我们可以观察，比如主串（华华的昵称）是，子串（小姐姐的昵称）是 ，那么当 匹配上了之后，再去枚举主串中的 其实是没有意义的，如果我们能做到在 之后跳到 后面第一个 然后在 之后跳到后面的第一个 （如果有的话），直到子串遍历完或者跳不动了，就能出结果了。（如果主串中有两个一样的字母，我们肯定会选前一个，因为是子序列，如果选前一个不可以，那么选后面的同一个字母肯定就更不可以了...