一只橘橘猫

题解

coderforces(20) dp动态规划(3) icpc(8) KMP算法(3) leetcode(1) STL(1) 人工智能(2) 优先队列(1) 图论(3) 字符串(5) 搜索(2) 数学(4) 日记(1) 最短路(3) 未归档(29) 杭电多校(7) 牛客多校(11) 牛客寒假训练营2020(6) 牛客练习赛(8) 线段树树状数组(2) 贪心(4)

/ 注册

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

剑指offer——数组中重复的数字来自专栏

solution： std： class Solution { public: // Parameters: // numbers: an array of integers // length: the length of a...

2020-04-19

2 888

剑指offer——构建乘积数组来自专栏

solution： std： class Solution { public: vector<int> multiply(const vector<int>& A) { int n = A.size(); vector<...

2020-04-19

1 796

[每日一题]4.17 华华给月月准备礼物来自专栏

题意：解法：：POJ 3273-Monthly Expense ：POJ 3122-Pie 时间复杂度： std: #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn...

2020-04-16

4 809

[每日一题]4.15 逆序对来自专栏

题意：解法：时间复杂度： std: #include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9 + 7; ll pow_mod(ll a,ll b){ ll ...

2020-04-15

6 1003

[每日一题]4.15 Treepath

题意：给出一棵树，求树上所有长度为偶数的路径个数涉及知识点：树上思路：以任意一个节点（默认以号节点），因为树上任意两点之间的距离是固定的，所以我们可以得到所有距离号节点的长度，存在两个结论（证明看下图）：①长度为偶数的任意两个节点之间的距离一定是偶数②长度为奇数的任意两个节点之间的距离也一定是偶...

2020-04-14

2 733

[每日一题] 4.13 Xorto

题意：可以简单理解成，存在多少对不重叠的非空区间，且区间异或值相等思路：根据前缀异或和的性质，设表示的区间异或和，那么的区间异或值就等于，因为只有，双重循环遍历，枚举端点，先记录以为右端点的所有区间异或值，存到数组，然后再记录以为左端点的值，保证区间不重叠，更新答案时间复杂度：代码： #...

2020-04-13

3 892

[每日一题]4.7 树来自专栏

题意：给出一颗树，有个节点，用种不同的颜色给每个节点染色，要求保证所有相同颜色的节点都相邻设计知识点：排列组合解法：首先，题意可以理解为将其分成个联通分量的染色方案数之和，将一棵树拆分成 i 个联通分量需要砍掉条边，就相当于从条边选择条边，那么方案数就是,接下来就可以从个颜色中选择种颜色，...

2020-04-06

3 1107

[每日一题]4.2 Shortest Path 来自专栏

题意：给出一棵有偶数的节点的树，将其分成n/2对点，并且要求n/2对点的路径之和最小涉及知识点：思维/树上dfs 思路：树上任意两点间的距离是唯一的，题目又要求路径之和最小，所以选择两个节点，要么是父节点和其孩子节点，要么是父节点的两个孩子节点，还有一种情况是多了一个孩子节点，那么肯定要先加上...

2020-04-02

1 873

[每日一题]4.1 月月查华华的手机来自专栏

涉及知识点：字符串匹配题意：给出母串 s，给出 m 次询问，每次询问给出的子串 si 是否是 s 的子序列思路：如果直接考虑双重for循环比较会超时，看着是道字典树的题，但是没写过字典树，就写了个递推思路的代码，设 nex[ i ][ j ] 表示第 i 个位置的字母后第一个 j + 'a'...

2020-04-01

5 1056

[每日一题] 3.30滑动窗口来自专栏

涉及知识点：队列/双指针做法：我看大佬们都是写的优先队列，我这里讲一下deque（双端队列）的解法吧，原理都是一样，首先先看一下deque的写法： deque<int> q;//定义双端队列 q.push_front(x);//队列头部插入元素x q.push_back(x);//队...

2020-03-29

0 749