Meul

题解

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1)

/ 注册

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

NC5278 B-每日一报

Question 报送日期不一致的，则日期较近的在上，日期较久远的在下；报送日期一致体温不一致的，则体温高的在上，体温低的在下；报送日期和体温都一致的，则学号小的在上，学号大的在下。Solution 结构体+自定义排序Code #include<bits/stdc++.h> u...

2020-04-18

0 741

NC5278 A-组队比赛

Question 输入a,b,c,d四个数，分成两组求差值最小为多少。 Solution 排个序，最大的和最小的一组，中间两个一组。坑点：题意没说要输出的一定为正数但是实际上是要的，然后我脑残WA了两发。(理论上来说WA有一发就够了） Code #include<bits/stdc++.h&g...

2020-04-18

0 518

NC50940

题意输入奇数个数的时候输出此时输入的数的中位数。思路建立一个大根堆和一个小根堆。（构成一个对顶堆）序列中从小到大排在的整数存储在大根堆中。序列中从小到大排在的整数存储在小根堆中。若一个堆中元素过多，则将其堆顶元素插入到另一个堆中即可。中位数为堆中元素为奇数个数的堆的堆顶。 #inclu...

对顶堆堆数据结构

2020-04-17

0 579

NC51180

题意给定一棵个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。思路换根DP这种题往往都是先从某个点出发，求出以这个节点为根的答案，并记录与答案相关的数据到数组中。然后从节点出发，记录换根的答案，其中所有根的最大值就为所求值。难点在于该如何去找寻其中的递推关系式。数组表...

树换根dp DP

2020-04-17

0 642

NC201400

题意一棵个结点的树，令根节点的深度,其他节点的深度为，求以某个点为根节点这棵树的最小为多少？思路我们要枚举每一个结点为根节点的为多少，我们可以先求得以某片叶子为根节点的，然后再找寻相连的的关系，记录最小值。以某一片叶子为根节点，DFS遍历整棵树，算其深度，算该节点的子树结点数量为。(无根树很多...

dfs 树

2020-04-16

0 667

NC23049

题意你有段小木棍，对每段小木棍切割，要求得到段长度相等为(正整数)的小木棍，求最大为多少？思路答案具有单调性，故考虑二分，时间复杂度 #include<bits/stdc++.h> using namespace std; typedef long long ll; typede...

二分

2020-04-16

0 626

NC14731

NC14731 题意求所有长度为的01串中满足如下条件的二元组个数：设第位和第位分别位和，则答案对取模。思路题目让我们求逆序对，长度的01子串1在0的左边有多少种方案，由于题中1和0的地位是等价的，故正序对的个数和逆序对个数是一样的。表示从个数里选个1剩下的全部为0，所构成的01子序列的个数...

数学组合数学

2020-04-16

1 558

NC14248

NC14248 题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同思路 DFS 树数据结构这道题和CF1339D十分相像，有兴趣的可以做一下。把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树...

DFS 树数据结构

2020-04-14

2 774

NC14247

NC14247 题意给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。思路枚举预处理异或前缀和为了便于我们求任意区间的异或和，预处理异或前缀和。为了避免区间重叠，我们枚举两个区间的分界点，记录(包含)即左边的异或区间值。我们发现左侧区间扩大，则左边异...

前缀异或枚举

2020-04-13

0 488

NC5026E

NC5026E 题意把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？思路二分+哈希字符串时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表...

哈希字符串二分哈希

2020-04-12

1 680